Red-Black Trees

There exists a special kind of binary search tree called a red-black tree that implements certain extra rules to ensure it stays balanced. Balancing is the process of repositioning nodes to decrease the height of a tree, thereby preventing it from degenerating into a list. Red-black trees, because they impose these conditions to self-balance, perform better, and it takes longer for their performance to degrade. 

Normal binary trees have 4 important relations:

• You: wherever you are
• Your parent: whoever you are connected to, which is one level closer to the root than you
• Your child(ren): whoever you are connected to, which are one level further from the root than you
• Your sibling(s): whoever may or may not have, as the nearest common ancestor with you, as a parent, the same node that is your parent

Red-black tree rules force us to care about 2  more relations:

• Your uncle: The sibling of your parent
• Your grandparent: the parent of your parent

The following coloring rules apply:

• The root is black
• Null nodes are black by default
• Red nodes’ children are not red
• Every path from the root to a particular node (or, equivalently, up from that node to the root) passes through equal numbers of red and black nodes

Both inserting and deleting nodes might cause violations of these rules to occur. Here are possible violations and how to fix them:

If you insert as red:

• And your parent is black
• You’re fine!
• And your parent is red
• Keep reading and check on your uncle
• And your uncle is red
• Color your parent black
• Color your uncle black
• Color your grandparent red
• Make sure that doesn’t cause any problems, and if there are any, fix them
• And your uncle is black
• If you’re a right child
• Rotate left, i.e., counter-clockwise, about your parent
• If you’re a left child
• Rotate right, i.e., clockwise, about your grandparent and recolor

A left rotation looks like:

Before Rotation:

    x                                              

     \                                             

      y                                                         

     / \                                                     

    a   b                                                     

After Left Rotation:

      y

     / \

    x   b

     \

      a

And has these steps:

• Set y to be the right child of x.
• Move y’s left subtree to x’s right subtree.
• Update the parent of x and y.
• Update x’s parent to point to y instead of x.
• Set y’s left child to x.
• Update x’s parent to y.

And a right rotation looks like this:

Befor Right Rotation:    

      x

     /

    y

   / \

  a   b

After Right Rotation:

    y

   / \

  a   x

     /

b

and has these steps:

• Set y to be the left child of x.
• Move y’s right subtree to x’s left subtree.
• Update the parent of x and y.
• Update x’s parent to point to y instead of x.
• Set y’s right child to x.
• Update x’s parent to y.

After inserting as red, you might need to recolor:

• If your parent and uncle are red, make them black and your grandparent red
• If the new node’s uncle is black (and the new node is the right child of a left or left child of a right—but not left of a left or right of a right) rotate appropriately
• If the new node’s uncle is black and this time the new node is a right child of a right child or left child of a left, rotate and recolor the parent and grandparent

After deleting:

• If you have a black-black parent-child, this can cause problems
• If you have a black sibling
• Recolor your parent and sibling, and rotate
• If your black sibling has black children
• Recolor the sibling red, and now your parent has a problem. Fix it appropriately.
• If your black sibling has any red children
• Rotate and recolor