(5270 Views)

A red-black tree is similar to the AVL-tree in its self-balancing nature. Each node of the binary tree has an extra bit, and that bit is often interpreted as the color (red or black) of the node. These color bits are used to keep the tree balanced during the insertions and deletions.

The recoloring of the nodes are done efficiently and doesn't slow down the tree itself.

Like most of the data structures, it guarantees to operate on O(log n) in most of the cases. The reordering and recoloring are also done in O(log n).

The red-black tree is defined by the following rules:

- Every node is either red or black.
- The root of the tree is always black.
- There can't be two adjacent red nodes. (A red parent can't have a red child or vice-versa)
- Every path from the root to the Null child node has the same number of black nodes.
- All the Null leaves are black.

It is very similar to the standard binary search tree where we add a node. We should also color it red. In the binary search tree a new node is added as a leaf, whereas leaves contain no information in the red-black tree, so instead, the new node replaces an existing leaf and then has two black leaves of its own added.

It is similar to the standard binary search tree node removal. If the node to be deleted was red, just delete it as in the BST. If the node to be deleted is black, we erase its value and associate the still colored node with whatever node comes to take its place (which could be a terminal node). If we allow the empty but colored node to be counted when measuring the black-node-length of a simple path, we will have retained the original black height of the tree. Our goal is to remove this empty black node from the tree.

1 UpvotesUpvote |
1 DownvotesDownvote |

- Insertion Sort Algorithm in Python [1000 Views]
- Algorithm for Sequential Search or Linear Search [5044 Views]
- C program to Search element using Binary Search Algorithm [2354 Views]
- AVL Tree Algorithm in Java [1684 Views]
- Bubble Sort Algorithm in C [772 Views]

- How To Win Ludo King Game Every Time [25314 Views]
- Knuth-Morris-Pratt (KMP) Substring Search Algorithm with Java Example [23802 Views]
- Algorithm to find whether number is Armstrong Number or Not [23348 Views]
- Jio Phone hang on LOGO problem Solution - Hard Reset Jio Phone [16522 Views]
- FlowChart and Algorithm to find Whether a Number is Even or Odd [12702 Views]