(454 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.

0 UpvotesUpvote |
0 DownvotesDownvote |

- AVL Tree Algorithm in Java [200 Views]
- Selection Sort Pseudocode and Flowchart in Java with Example [937 Views]
- Linked List for Beginners [541 Views]
- Depth First Search (DFS) Pseudocode and Program in Java [124 Views]
- Heap Sort Algorithm in C++ [246 Views]

- Knuth-Morris-Pratt (KMP) Substring Search Algorithm with Java Example [9211 Views]
- Pseudocode and Algorithm to find whether number is Armstrong Number or Not [7539 Views]
- How To Win Ludo King Game Every Time [7340 Views]
- error: Multiple commands produce error in Xcode 10 [5048 Views]
- FlowChart and Pseudocode to find Whether a Number is Even or Odd [3990 Views]