[Data Structure] Red-Black Tree - 2: Insertion & Balance

Insertion Algorithm

Given a new node, a red-black tree insert operation inserts the new node in the proper location such that all red-lack tree requirements still hold after the insertion completes. 

It begins by calling BSTInsert to insert the node using the orginary BST insert rules. 

The newly inserted node is red colored and then a balance operation is performed on this node. 

RBTreeInsert(tree, node) {
    BSTInsert(tree, node)
    node→color = red
    RBTreeBalance(tree, node)
}

 

The red-black balance operation consists of the steps below.

1. Assign parent with node's parent, uncle with node's uncle, which is a sibling of parent, and grandparent with node's grandparent.
2. If node is the tree's root, then color node black and return.
3. If parent is black, then return without any alterations.
4. If parent and uncle are both red, then color parent and uncle black, color grandparent red, recursively balance grandparent, then return.
5. If node is parent's right child and parent is grandparent's left child, then rotate left at parent, assign node with parent, assign parent with node's parent, and go to step 7.
6. If node is parent's left child and parent is grandparent's right child, then rotate right at parent, assign node with parent, assign parent with node's parent, and go to step 7.
7. Color parent black and grandparent red.
8. If node is parent's left child, then rotate right at grandparent, otherwise rotate left at grandparent.

The rules are quite complex. 

 

RBTreeBalance(tree, node) {
   if (node⇢parent == null) {
      node⇢color = black
      return
   }
   if (node⇢parent⇢color == black)
      return
   parent = node⇢parent
   grandparent = RBTreeGetGrandparent(node)
   uncle = RBTreeGetUncle(node)
   if (uncle != null && uncle⇢color == red) {
      parent⇢color = uncle⇢color = black
      grandparent⇢color = red
      RBTreeBalance(tree, grandparent)
      return
   }
   if (node == parent⇢right &&
       parent == grandparent⇢left) {
      RBTreeRotateLeft(tree, parent)
      node = parent
      parent = node⇢parent
   }
   else if (node == parent⇢left &&
            parent == grandparent⇢right) {
      RBTreeRotateRight(tree, parent)
      node = parent
      parent = node⇢parent
   }
   parent⇢color = black
   grandparent⇢color = red
   if (node == parent⇢left)
      RBTreeRotateRight(tree, grandparent)
   else
      RBTreeRotateLeft(tree, grandparent)
}