Insert Algorithm for RBT tree

The insert algorithm for RBT tree is very simple but easy to make a mistake. The basic steps are as follows:

Steps to Insert a Node

  1. Insert the new node as you would in a regular Binary Search Tree (BST). This means you will traverse the tree to find the correct position for the new node based on its key.
  2. Color the new node RED. This is important because it helps maintain the properties of the RBT.
  3. Check for any violations of the RBT properties. This is where the balancing comes into play.

Red Uncle Node

  1. If it is a ziz-zag case, perform a correct rotation to make it a straight line.
  2. Recolor the uncle node, parent node, and grandparent node.
  3. If the grandparent node is root and red, recolor it to black.
  4. Else, check any violation above.

Final tree should look like this.

Black or Null Uncle Node

  1. If it is a zig-zag case, perform a correct rotation to make it a straight line.
  2. Perform parent and grandparent node rotation.
  3. Recolor the parent node and the grandparent node.
  4. If the parent node is red and root, change it to black.
  5. Else, check any violation above.

Final tree should look like this.