(328 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 |

- Java Program to Calculate Area Of Triangle with 3 Sides Given [128 Views]
- Check if A Number is a Composite number or Not in C++ [19 Views]
- What is the difference between Stack and Queue in java? [203 Views]
- Java Factory Design Pattern with Example [884 Views]
- Bubble Sort Algorithm in Python [109 Views]

- Knuth-Morris-Pratt (KMP) Substring Search Algorithm with Java Example [6566 Views]
- Pseudocode and Algorithm to find whether number is Armstrong Number or Not [5374 Views]
- How To Win Ludo King Game Every Time [5135 Views]
- error: Multiple commands produce error in Xcode 10 [4104 Views]
- Create Dynamic Pagination using Java Spring Boot, Hibernate and MySQL [3315 Views]