Left-Leaning Red-Black Trees

Table of contents

1. Tree rotation
2. Rotation
3. Left-leaning BST
4. LLRB trees
5. LLRB tree invariants
6. LLRB tree demos
7. 1-1 correspondence
8. What would a 2-3 tree do?
9. LLRB tree height
10. LLRB tree insertion

Tree rotation

2-3 trees are complicated to implement because overstuffing and splitting requires frequently constructing new 2-nodes and 3-nodes. In practice, creating new nodes so often can slow down the data structure even though it is (generally) an asymptotic improvement over binary search trees. In this lesson, we will learn about a self-balancing binary search tree that has a one-to-one correspondence with 2-3 trees.

Depending on the order items are inserted into the tree, there are many different ways to construct a binary search tree containing the same set of items. However, insertion order is not the only way to build different configurations of the same set of items. We can change the structure of a binary tree through rotation.

Each rotation makes a local adjustment to the tree, sometimes increasing and sometimes decreasing the height of the tree but always respecting the binary search tree invariant. Items that are ordered between B and D in the example below stay ordered after a rotation.

Given a particular node in a tree, we can either rotate it to the left or to the right by making it the child of one of its parents. In these definitions, G and P correspond to their labels in the tree shown below.

rotateLeft(G)

Let x be the right child of G. Make G the new left child of x. We can think of this as temporarily merging G and P, then sending G down and left.

rotateRight(P)

Let x be the left child of P. Make P the new right child of x. We can think of this as temporarily merging G and P, then sending P down and right.

Question 1

Give a sequence of rotation operations that balances the tree on the left.

Question 2

After performing a rotation, which of the following can occur?

• If the tree had the search tree property, it may lose it.
• If the tree did not have the search tree property, it may gain it.
• The height can stay the same.
• The height can increase.
• The height can decrease.
• The number of nodes can change.
• The root can change.

Rotation

Left-leaning BST

Goal

Develop a self-balancing binary search tree using the self-balancing property of 2-3 trees.

Note that 2-3 trees that only contain 2-nodes are already regular binary search trees! The challenge for us is to develop a binary tree representation for 3-nodes: nodes with left, middle, and right children.

Using an idea from rotation, we can separate a 3-node with the keys B and D into two nodes exactly as shown during the node rotation process. Each 3-node can be converted into two 2-nodes connected with a left-leaning “glue” edge. (In an alternate universe, we could have picked a right-leaning “glue” edge.)

Left-leaning binary search tree

A binary search tree representation of a 2-3 tree where 3-nodes are represented as two 2-nodes connected with a left-leaning “glue” edge.

LLRB trees

LLRB tree invariants

Converting from the left-leaning BST back to a 2-3 tree is somewhat tricky since it’s hard to tell which nodes represent 3-nodes rather than 2-nodes. This is also hard to do in code too, so left-leaning red-black trees introduce a little bit of extra information to the “glue” edge.

Left-leaning red-black (LLRB) trees color “glue” edges (representing 3-nodes) red. Red edges connect separated 3-nodes and help us to maintain correspondence with 2-3 trees but otherwise don’t have any special functionality. In code, the red edge is represented in code as an extra color field stored in the left-leaning node. Remember that edges in a binary search tree are just references, so they don’t have fields. Only nodes are objects, so any extra information such as red/black coloring needs to be stored in a node.

1-1 correspondence

Every 2-3 tree has a unique left-leaning red-black tree associated with it.

LLRB tree invariants follow entirely from 1-1 correspondence with 2-3 trees.

• Red edges lean left—all 3-nodes are represented as two nodes connected with left-leaning “glue” edges.
• No node has two red edges connected to it—2-3 trees only allow up to 3-nodes with 2 keys and 3 children.
• Every root-to-null path has the same number of black edges—all 2-3 tree leaf nodes are the same depth from the root.

Question 1

Which of the following are valid LLRB trees?

Question 2

What is the height of the 2-3 tree corresponding to this LLRB tree?

LLRB tree demos

1-1 correspondence

What would a 2-3 tree do?

The implementation for an LLRB tree relies on the invariants and 1-1 correspondence with 2-3 trees. 2-3 tree operations like overstuffing leaves and splitting nodes can be implemented with rotations and recoloring in an LLRB tree. In any situation, we can always ask: What would a 2-3 tree do?

The following simplified snippet from the implementation of RedBlackBST.java first performs the standard recursive BST insertion (new leaves are colored red) and then performs some maintenance when returning from each recursive call.

private Node add(Node h, Key key) {
    // New leaves are colored red
    if (h == null)
        return new Node(key, RED);

    // Recursive BST insertion
    int cmp = key.compareTo(h.key);
    if (cmp < 0)
        h.left  = add(h.left,  key);
    else if (cmp > 0)
        h.right = add(h.right, key);
    else
        return h; // do not add duplicates

    // Maintain LLRB tree invariants
    if (isRed(h.right) && !isRed(h.left))
        h = rotateLeft(h);
    if (isRed(h.left) && isRed(h.left.left))
        h = rotateRight(h);
    if (isRed(h.left) && isRed(h.right))
        flip(h);

    return h;
}

When returning from each recursive call to add, the code addresses each of these conditions as necessary.

1. If the right child is red and the left child is black, rotate left.
2. If the left child and its left grandchild are red, rotate right.
3. If both children are red, flip colors.

Each rotation or color flip is a constant-time operation, so the overall order of growth for the runtime of add is in O(log N).

LLRB tree height

Given a 2-3 tree, the height of the corresponding left-leaning red-black tree depends on the number of 3-nodes.

Question 1

Give the exact height of the corresponding LLRB tree.

Question 2

Given a 2-3 tree of height H, give the exact worst-case height of the corresponding LLRB tree as a (simple) function of H.

LLRB tree insertion

In an LLRB tree, elements are inserted as red leaf nodes. When returning from each recursive call to add, the code addresses each of these conditions as necessary.

1. If the right child is red and the left child is black, rotate left.
2. If the left child and its left grandchild are red, rotate right.
3. If both children are red, flip colors.

Question 1

If we add 15 to this LLRB tree, what operation will we need to perform to maintain LLRB invariants? Give a method call to either rotateLeft(n), rotateRight(n), or flip(n) where n is replaced with the value of the node.

Question 2

Which of the following values requires an immediate rotateRight operation when inserted into this LLRB tree?

• 0
• 15
• 19
• 24
• 36
• 40
• 45

Question 3

What is the value of the overall root for the LLRB tree that results from inserting these items in the given order: 1, 2, 3, 7, 8, 9, 5?

Question 4

If we add 15 to this LLRB tree, what operation(s) will we need to perform to maintain LLRB invariants? Give a list of method calls to rotateLeft(n), rotateRight(n), or flip(n) where n is replaced with the value of the node.