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.

struct RBNode {             int data ;             enum { red, black} color ;             struct RBNode *left, *right ;             struct RBNode *parent ; };

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.