(1706 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 |
0 DownvotesDownvote |

- Simple Bubble Sort Algorithm in Java [445 Views]
- Binary Tree Program implementation in Java [615 Views]
- Algorithm for Merge Sort in Java [1079 Views]
- Breadth First Search (BFS) Pseudocode and Program in Java [201 Views]
- Algorithm for Binary Search [1638 Views]

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