Red-Black Trees: Insertion

• Red-Black Trees are an alternative to AVL trees, invented in 1978.
• A red-black tree is a binary search tree (BST) with nodes colored red and black.
• Paths from the root to any null reference have the same number of black nodes.
• There cannot be two consecutive red nodes on a path.
• If a node is red, both its children are black.
• The root of a red-black tree is always black.
• Every time a node is inserted or deleted, it must be ensured that every path from root to null has the same number of black nodes, maintaining the balance of the tree.

Red-Black Trees: Insertion

• When inserting a value into a red-black tree, the color must be picked as either red or black.
• A new node cannot be black because it would violate the black path length property.
• The new node MUST be RED.
• After insertion, the "no consecutive red nodes" property might be violated.
• The tree is rebalanced through re-coloring and rotations.
• Easiest insertion case: Do nothing if the parent of the newly inserted node (X) is black.

Special Insertion Cases

• Case 0: If X is the root, simply color it black.
• Case 1: If both the parent (P) and uncle (U) of X are red, re-color and if the grandparent is now in trouble repeat the algorithm recursively, from the grandparent upwards.
• Cases 2 and 3: If P is red and U is black, rotations and re-colouring are needed.
• Null nodes are considered to be BLACK.
• If P has no siblings, it counts as having a black U.
• Case 2 (zig-zag): When P is red, but U is black, P is a left child, and Z is a right child: G and Z swap colours and Z becomes black
  • Perform a double rotation: Z around P, then Z around G
• Case 3 (zig-zig): When P is red, but U is black, and P is a left child, Z is also a left child
  • Re-colour P and G swap colours
  • Perform a single rotation: P around G.

Bottom-Up vs Top-Down Insertion

• Bottom-up: Insert into BST, then percolate upwards (backtrack) to fix up the tree.
  • Recursion is required, which can be expensive.
• Top-down: Corrections are made while traversing down the tree to the insertion point.
  • No further corrections are needed once the insertion is done, so no need to backtrack.
  • Top-down insertion is iterative.

Top-Down Insertion Details

• Insertion occurs at a leaf.
• In Bottom-Up insertion, if the Uncle of the newly inserted node Z is black, the Red-Black tree properties are restored by one or two local rotations and recoloring.
  • Backtracking is only needed if both P and U are red.
• In Top-Down insertion, the traversal from the root to the insertion point maintains Red-Black properties, and at the insertion point, the uncle is Black.
• Rotation and recoloring may be necessary, but there is no need to propagate back up the tree.

Insertion Configurations

• If a new node is inserted as a child of Y or Z, there is no problem if the new node's parent is black.
• If a new node is a child of Z, there is no problem since Z is black.
• If a new node is a child of Y, with uncle (Z) is black, perform a few rotations and recolor.
• The Case to avoid: When a new node is inserted as a child of Y or Z, its uncle will be red, requiring a return up the tree.

Top-Down Traversal

• Before inserting, recolor and rotate to avoid backtracking.
• Consider these Cases:
  • Remember the goal: to create an insertion point at which the parent P of the new node is Black, or the uncle U of the new node is Black.

Conditions for Insertion

• Case 1: X's Parent is Black:
  • Recolor X (current node) to red, and its children to black, then insert.
  • If X is the root, recolor it black.
• Case 2: zig-zig
  • X's Parent is Red (so Grandparent is Black), and X and P are both left/right children
    • Rotate P around G, Color P black, color G red and X, Y, Z adhere to Case 1: recolor!
• Case 3: zig-zag
  • X's Parent is Red (so Grandparent is Black), and X and P are opposite children
    • Recolor X, Y, Z, Rotate X around P, Rotate X around G and Recolor X and G
• If inserting with a red parent and black uncle, the cases are addressed as in bottom-up insertion.

Top-Down Insert Example

• Start at the top.
• Identify the insertion point using cases 1-3 if both parent P and uncle U are red. If P is red and U is black, use bottom-up cases 2-3.
• Case 1: If G is black, recolor X, Y, Z and insert.

Summary of Red-Black Trees

• BST where each node is red or black.
• Paths from the root to any null reference have the same number of black nodes.
• There cannot be two consecutive red nodes.
• The root is black.
• Insertion involves inserting at the leaf and percolating upwards (bottom-up) or performing recoloring and rotations on the way to the leaf (top-down).
• The next lecture focuses on deletion from red-black trees.