Archives of Data Structures and Algorithms

Just another archive with dsa

Trees

Red-Black Tree

A red-black tree is a kind of self-balancing binary search tree. Each node stores an extra bit, which we will call the color, red or black. The color ensures that the tree remains approximately balanced during insertions and deletions.

When the tree is modified, the new tree is rearranged and repainted to restore the coloring properties that constrain how unbalanced the tree can become in the worst case.

Properties

In addition to all the properties of a Binary Search Tree, a red-black tree must have the following:

1. Each node is either red or black

2. The root is black. This rule is sometimes omitted. Since the root can always be changed from red to black, but not necessarily vice versa, this rule has little effect on analysis.

3. All Nil leaf nodes are black.

4. If a node is red, then both its children are black.

5. All paths from a single node go through the same number of black nodes to reach any of its descendant NIL nodes.

RB trees are not perfectly balanced

The re-balancing of a red-black tree does not result in a perfectly balanced tree. However, its insertion and deletion operations, along with the tree rearrangement and recoloring, are always performed in O(log(n)) time.