Introduction + Properties of RBTs

A Red-Black tree is a type of self-balancing binary search tree where each node is either red or black.

A Red-Black tree garuntees that searching, inserting, and deleting nodes can be performed in O(log n) time.

Here are the properties of Red Black Trees.

• Every node is either red or black (nulls are considered black).
• The root is always black.
• The children of red nodes are black (no two red nodes can be adjacent).
• Every path from a given node to any of its descendant null nodes must have the same number of black nodes.

Red-Black Tree Insertion Repair Algorithms (Click to find out more)

Steps for Basic Insertion:

1. Insert the new node as a red node.
2. If the parent of the new node is black, then the tree is still valid. No further action is needed.
3. If the parent of the new node is red, then there is a RBT violation. Use one of the two repair algorithms.

Black Aunt Repair Algorithm

Here we will discuss the steps of the BLACK Aunt RBT insertion repair algorithm. It can be a bit tricky so here are the steps laid out.

1. Identify the aunt of the new node (the sibling of its parent).
2. If the aunt is black (or null), we need to perform 1 or 2 rotations with recoloring to fix the tree.
   1. If the new node is a right child and its parent is a left child (zig-zag), perform a left rotation on the parent.
   2. If the new node is a left child and its parent is a right child (zig-zag), perform a right rotation on the parent.
   3. When the grandparent, parent, and child are in a line (aligned), perform a single rotation between the parent and grandparent.
   4. After the rotation, recolor the parent to black and the grandparent to red.

Red Aunt Repair Algorithm

Here we will discuss the steps of the RED Aunt RBT insertion repair algorithm. This is more straightforward than the previous repair.

1. Identify the aunt of the new node (the sibling of its parent).
2. If the aunt is red, we need to perform a recolor operation to fix the tree.
3. Recolor the parent and aunt to black.
4. Recolor the grandparent to red.
5. There is a potential for a RBT property violation so double check them using the grandparent as the new node