How Insertion Works in Red-Black Trees

INTRODUCTION

Red Black Tree is a self balancing binary search tree. Each node in RB tree is colored using either red or black. AVL tree requires for rotations during insertion and deletion because it is more balanced than RB tree. RB tree is used for applications which require more frequent insertion and deletion.

Red Property: A Red node cannot have red children.

Black Property: Each path from a node to its leaves should have equal number of black nodes.

Therefore, in this example from root node to its descendant null nodes there are 2 black nodes in every
path.

INSERTION

1. New Node is red in color.
2. Root nodes are always black.

1. If the node to be inserted is not a root node, then check color of parent, I) if parent is black, then simply insert the node.

II) if parent is red, then check parent’s sibling
a. if parent’s sibling is red, change the color of parent and parent’s sibling to black, and grandparent
to red. If grandparent is root don’t change to red. If its not root repeat the same for grandparent.

b. if parents sibling is black,

i) Left Left case

• When a node is inserted in the left sub tree of the left child.
• Perform right rotation on grandparent, then swap colors of grandparent and parent.

In the above example, the new node =8, Parent node=20, grand parent=25, parent’s Sibling=30.

• In RB tree red node cannot have red children. Inserting 8 violates this property.
• Parent 20 is red and parent’s sibling 30 is black so perform rotations.
• In this case perform right rotation on grandparent 25. and swap colors of 25 and 28

ii) Left Right case

• When a node is inserted in the right subtree of the left child.
• Left rotate parent p and apply LL rotation case.

In this example, new node=21, parent=20, grandparent=25, parent’s sibling=30.

• If we insert new node 21, RB property violates because red node can never have red children.
• As the parent 20 is red and parent sibling 30 is black perform rotations.
• In this case perform left rotation on parent. Then right rotate 25 and swap colors of grand parent 25 and new node 21.

iii) Right Right Case

• when a node is inserted in the right subtree of the right child.
• Left rotate grandparent and swap colors of grand parent and parent.

In the above example, the new node =30, Parent node=28, grand parent=25, parent’s Sibling=21

• In RB tree red node cannot have red children. Inserting 30 violates this property.
• Parent(28) is red and parent’s sibling(21) is black so perform rotations.

• In this case perform left rotation on grandparent 25. and swap colors of 25 and 28.
  iv) Right Left Case

• When a node is inserted in the left sub tree of the right child.

• Right rotate parent and apply RR rotation.

In this example, new node=30, parent= 32, grandparent=28, parent sibling=21

• when we insert 30, it violates RB property of no red node can have red children.
• The parent 32 is red and sibling of parent 21 is black. So perform rotations.
• In this case right rotate parent 32. Then Left rotate grandparent 28, then swap colors of inserted node 30 and grandparent 28.

Conclusion
In RB tree rules are always consistent. It maintains no consecutive red nodes and ensure that every path has the same number of black nodes. By applying recoloring and rotations , the tree rebalances itself automatically.