# DS – Red Black Trees

Red Black Trees

• A red black tree is a binary search tree.
• It is not completely balanced.
• We can balance the maximum; using RB Tree rotations.
• Every Node in Red Black Tree with an extra attribute: the color either Red or Black.

We need to follow some of the rules to construct RB tree.

Rule-1:

• It is called BST rule.
• Red Black Tree must be a Binary Search Tree (least value goes left to parent and higher value goes right to parent).

Rule-2:

• Also called Rule property.
• The Root Node is always Black

Rule-3:

• It is also called Red node property.
• The Children of Red color node must be colored Black (Two consecutive Red color nodes not allowed).

Rule-4:

• It is called Depth property.
• In all the paths of the tree, there must be same number of Black nodes.
• Also called black height of the tree

Rule-6:

• It is new node property.
• Every new node must insert with RED color.
• We can repaint to black after insertion for balancing.

Rule-6:

• It is leaf node property.
• Every leaf node (NULL node) must consider as Black.

Re-Painting:

• We must insert a new node with red color.
• Two consecutive red nodes not allowed. Hence balancing is required.
• When uncle(also called neighbor) node is red color, no rotations required.
• Paint Parent and Uncle to Black color.
• Paint Grandparent to Red color(make it black if it is root).
• If the uncle node is colored black. We need to repaint and rotate to balance the tree.
• Rotation are like AVL Tree
• L-L Rotation
• R-R Rotation
• L-R Rotation
• R-L Rotation
• If there is no right child, we consider the NULL child node.
• NULL is always black in Red-Black Tree.
• When Uncle(NULL) is black color, we re-paint and rotate for balancing.

Double rotation:

• In the following example, The tree is not balance and the left child is right heavy.
• Hence double rotation with re-painting is required to balance the tree.
• Single left rotation
• After that, paint child to black and grandparent to red.
• Then single right rotation.

Scroll to Top