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.


  • 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).


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


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


  • 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


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


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


  • 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