AVL Tree Height Invariants, Left-Right Rotations & Red-Black Balancing Mechanics

Binary search trees represent one of the foundational abstractions in computer science, organizing ordered data to support logarithmic search, insertion, and deletion. However, an unconstrained binary search tree is fundamentally vulnerable to structural degeneration: when keys are inserted in sorted or near-sorted order, the tree collapses into a linear linked list with disastrous O(N) performance. Self-balancing binary search trees solve this vulnerability by enforcing structural and color invariants through local pointer transformations called tree rotations. Mastering the mechanics of AVL height bounds, balance factor restoration, and Red-Black black-height invariants is vital for systems programming, compiler optimization, and high-performance database design.

1. Binary Search Tree Degeneration & The Need for Self-Balancing#

A Binary Search Tree (BST) is a hierarchical node-based data structure where each node stores a key and maintains at most two children:

• The Left Subtree contains only nodes with keys strictly less than the node's key.
• The Right Subtree contains only nodes with keys strictly greater than the node's key.
• Both left and right subtrees must themselves be valid binary search trees.

The Search Cost Bound#

The time complexity of search, insertion, and deletion operations in any binary search tree is directly proportional to the maximum length of a simple path from the root node to a leaf:

Time = O(h),

where h is the tree height.

The Degeneration Catastrophe#

In an ideal, perfectly balanced binary tree containing N nodes:

h = ceil(log2(N + 1)).

For N = 1,000,000 nodes, the ideal height is approximately 20 pointer hops.

However, the topological shape of a naive BST depends entirely on the chronological arrival order of its inputs:

• If keys are inserted in random order, expected height is O(log N).
• If keys are inserted in monotonically sorted order (e.g., [10, 20, 30, 40, 50]):

Every new node is inserted as the right child of the previous node.

The tree degenerates into a single linear chain of height h = N!

+----------------------------------------------------------------------------------------------------+
|                               DEGENERATE vs SELF-BALANCED BINARY TREES                             |
+----------------------------------------------------------------------------------------------------+
  Degenerate BST (Sorted Insert: 10, 20, 30, 40, 50):   Self-Balanced Tree (Rotated):
          10                                                    30
           \                                                  /    \
            20                                              20      40
             \                                             /          \
              30                                          10           50
               \
                40
                 \
                  50
  Height = 5 (O(N) Search Latency)                      Height = 3 (O(log N) Search Latency)
+----------------------------------------------------------------------------------------------------+

In this degenerate state, searching for an element requires traversing every node sequentially, collapsing the BST into an inefficient linked list with O(N) worst-case time complexity.

Self-Balancing Binary Search Trees eliminate this vulnerability by monitoring structural properties during mutations and executing local restructurings to guarantee that tree height remains strictly bounded by O(log N) under all possible input sequences.

2. Tree Rotations: The Universal Topological Primitive#

Tree rotations are the universal, constant-time pointer transformations used by self-balancing trees to alter tree height without violating the Binary Search Tree ordering invariant.

The Binary Search Tree Invariant Preservation#

Let X and Y be two nodes in a binary tree where X is the left child of Y.

Let A, B, and C be arbitrary subtrees satisfying the binary search tree property:

All elements in A < X < All elements in B < Y < All elements in C.

       Right Rotation (on Y)
       -------------------->
            Y                      X
           / \                    / \
          X   C   <----------    A   Y
         / \      Left Rotation     / \
        A   B        (on X)        B   C

Notice the key mathematical property:

• In the left tree: In-order traversal visits A -> X -> B -> Y -> C.
• In the right tree: In-order traversal visits A -> X -> B -> Y -> C.

Because the in-order traversal sequence is completely identical in both configurations, a rotation restructures the tree height while preserving the BST ordering property 100%!

The Four Rotational Configurations#

Imbalances fall into four geometric configurations:

1. Single Right Rotation (Right-Right / LL Imbalance):

Occurs when a node becomes left-heavy due to an insertion in its left child's left subtree.

Algorithm:

```cpp

Node rotate_right(Node y) {

Node* x = y->left;

Node* B = x->right;

x->right = y;

y->left = B;

// Update heights

y->height = 1 + max(height(y->left), height(y->right));

x->height = 1 + max(height(x->left), height(x->right));

return x; // New subtree root

}

```

Requires updating exactly 3 pointers: x->right, y->left, and the parent's pointer to x. Cost = O(1).

1. Single Left Rotation (Left-Left / RR Imbalance):

Occurs when a node becomes right-heavy due to an insertion in its right child's right subtree.

Algorithm:

```cpp

Node rotate_left(Node x) {

Node* y = x->right;

Node* B = y->left;

y->left = x;

x->right = B;

// Update heights

x->height = 1 + max(height(x->left), height(x->right));

y->height = 1 + max(height(y->left), height(y->right));

return y; // New subtree root

}

```

1. Double Left-Right (LR) Rotation:

Occurs when a node becomes left-heavy, but its left child is right-heavy (forming a zigzag "elbow" shape).

A single rotation cannot fix a zigzag. The solution requires a two-step rotation:

- Step 1: Perform a Single Left Rotation on the left child, transforming the zigzag into a straight line.

- Step 2: Perform a Single Right Rotation on the parent node.

1. Double Right-Left (RL) Rotation:

Occurs when a node becomes right-heavy, but its right child is left-heavy.

- Step 1: Perform a Single Right Rotation on the right child.

- Step 2: Perform a Single Left Rotation on the parent node.

3. AVL Trees: Strict Balance Factors & Mathematical Height Bounds#

Invented in 1962 by Soviet mathematicians Georgy Adelson-Velsky and Evgenii Landis, the AVL Tree was the first self-balancing binary search tree ever discovered.

The AVL Balance Factor Invariant#

An AVL tree enforces a strict height balance invariant on every node:

For every node v in the tree, the heights of its left and right subtrees may differ by at most 1.

Define the Balance Factor (BF) of node v:

BF(v) = height(v.left) - height(v.right).

The AVL Invariant mandates:

BF(v) in { -1, 0, +1 } for all nodes v.

If an insertion or deletion causes BF(v) to evaluate to +2 or -2, an imbalance has occurred, and the tree must immediately be restored via rotations.

The Four AVL Insertion Rebalancing Rules#

After a standard recursive BST insertion, the algorithm walks back up the recursion stack toward the root, updating node heights and checking balance factors.

Let z be the first ancestor node where BF(z) in { +2, -2 }:

1. Case LL (Left-Left):

Condition: BF(z) = +2 and key was inserted into the left subtree of z's left child (BF(z.left) >= 0).

Resolution: Execute a Single Right Rotation on z.

1. Case RR (Right-Right):

Condition: BF(z) = -2 and key was inserted into the right subtree of z's right child (BF(z.right) <= 0).

Resolution: Execute a Single Left Rotation on z.

1. Case LR (Left-Right):

Condition: BF(z) = +2 and key was inserted into the right subtree of z's left child (BF(z.left) = -1).

Resolution: Execute a Double Rotation: Left Rotation on z.left, followed by Right Rotation on z.

1. Case RL (Right-Left):

Condition: BF(z) = -2 and key was inserted into the left subtree of z's right child (BF(z.right) = +1).

Resolution: Execute a Double Rotation: Right Rotation on z.right, followed by Left Rotation on z.

Crucial Property of AVL Insertions:

A single rebalancing operation (either one single rotation or one double rotation) restores the balance factor of node z to 0 and restores the original subtree height before the insertion. Therefore, an insertion requires at most O(1) rotations (at most 2 single rotations) to rebalance the entire tree!

AVL Deletion Rebalancing#

When a node is deleted from an AVL tree:

• Rebalancing is more complex: fixing an imbalance at node z may shorten the subtree, causing an imbalance at z's parent.
• Rotations can propagate all the way up to the root, requiring up to O(log N) rotations in the worst case.

Rigorous Mathematical Proof of AVL Tree Maximum Height#

How tall can an AVL tree grow in the worst possible case? To find the maximum height for N nodes, we invert the question: what is the minimum number of nodes N(h) required to build an AVL tree of height h?

Let N(h) denote the minimum node count for an AVL tree of height h.

Base cases:

• Height 0: N(0) = 1 (a single root node).
• Height 1: N(1) = 2 (a root with one child).

To minimize the number of nodes for height h, one child subtree must have height h - 1 (the minimum possible height to achieve total height h), while the other child subtree must have the smallest legal height allowed by the AVL invariant, which is (h - 1) - 1 = h - 2:

N(h) = 1 + N(h - 1) + N(h - 2).

Trace the minimum node values:

• N(0) = 1
• N(1) = 2
• N(2) = 1 + 2 + 1 = 4
• N(3) = 1 + 4 + 2 = 7
• N(4) = 1 + 7 + 4 = 12
• N(5) = 1 + 12 + 7 = 20

Notice the relationship to Fibonacci numbers F_k (where F_1 = 1, F_2 = 1, F_3 = 2, F_4 = 3, F_5 = 5, F_6 = 8, F_7 = 13, F_8 = 21):

Add 1 to both sides:

N(h) + 1 = (N(h - 1) + 1) + (N(h - 2) + 1).

Let G(h) = N(h) + 1. Then G(h) satisfies the exact Fibonacci recurrence:

G(h) = G(h - 1) + G(h - 2).

Base cases: G(0) = 2 = F_3, G(1) = 3 = F_4.

By mathematical induction:

N(h) + 1 = F_{h + 3}.

Therefore:

N(h) = F_{h + 3} - 1.

Using Binet's formula for Fibonacci numbers with Golden Ratio φ = (1 + √5) / 2 ≈ 1.618034:

F_k ≈ (φ^k) / √5.

Substituting into the node bound:

N >= (φ^{h + 3} / √5) - 1

N + 1 >= φ^{h + 3} / √5

√5 · (N + 1) >= φ^{h + 3}.

Taking log base φ of both sides:

h + 3 <= log_φ(√5 · (N + 1)) = log_φ(√5) + log_φ(N + 1).

Convert log_φ to log_2 using change of base:

log_φ(x) = log_2(x) / log_2(φ) = log_2(x) / log_2(1.618034) ≈ 1.44042 · log_2(x).

Evaluating constants:

h <= 1.44042 · log_2(N + 1) - 0.3277.

Conclusion:

The maximum height of an AVL tree containing N nodes is strictly bounded by:

h < 1.4404 · log_2(N + 2).

For 1,000,000 nodes, the maximum possible height of an AVL tree is at most 1.44 · 20 ≈ 28.8 levels! This guarantees blazing fast search times under all adversarial conditions.

4. Red-Black Trees: Invariants, Amortized Rebalancing & Black-Height Proof#

While AVL trees provide exceptionally tight height bounds, their strict balance invariant requires frequent rotations during write operations (up to O(log N) rotations on deletion).

Introduced by Rudolf Bayer in 1972 (under the name Symmetric Binary B-Trees) and formalized by Leo Guibas and Robert Sedgewick in 1978, the Red-Black Tree relaxes the height balance constraint slightly. It allows tree height to reach up to 2 · log2(N + 1), which dramatically reduces rebalancing overhead during insertions and deletions.

The Five Red-Black Tree Invariants#

A Red-Black tree is a binary search tree where every node carries a 1-bit color attribute (Red or Black), satisfying five structural invariants:

1. Node Color Property: Every node is colored either Red or Black.
2. Root Property: The root node of the tree is always Black.
3. Leaf Property: Every leaf (the sentinel NIL node representing absent children) is Black.
4. Red Child Property: If a node is Red, both of its children must be Black. (Equivalently: no two Red nodes may appear consecutively along any simple path).
5. Black-Height Property: For every node v, all simple paths from v to descendant NIL leaves contain the exact same number of Black nodes.

+----------------------------------------------------------------------------------------------------+
|                                    RED-BLACK TREE INVARIANT TOPOLOGY                               |
+----------------------------------------------------------------------------------------------------+
                                      [ 13 (Black) ]  <-- Root is Black
                                     /              \
                        [ 8 (Red) ]                    [ 17 (Red) ]  <-- Red parent has Black children
                       /           \                  /            \
               [ 1 (Black) ]   [ 11 (Black) ]   [ 15 (Black) ]   [ 25 (Black) ]
                 /       \       /        \       /        \       /        \
               NIL      NIL    NIL       NIL    NIL       NIL    NIL       NIL
  All paths from Root to any NIL leaf pass through exactly 2 Black nodes! (Black-Height = 2).
+----------------------------------------------------------------------------------------------------+

The Concept of Black-Height#

The Black-Height of a node x, denoted by bh(x), is the number of black nodes on any simple path from x down to a NIL leaf, excluding x itself (but including the NIL leaf).

Because of Invariant 5, bh(x) is well-defined and identical along every possible descendant path.

Rigorous Mathematical Proof of Red-Black Tree Height Bound#

We now prove that a Red-Black tree with N internal nodes has a maximum height:

h <= 2 · log2(N + 1).

Lemma: The subtree rooted at any node x contains at least 2^{bh(x)} - 1 internal nodes.

Proof by Induction on the height of x:

• Base Case: height(x) = 0.

Then x must be a NIL leaf.

bh(x) = 0.

The number of internal nodes in an empty tree is 0.

Evaluate bound: 2^{bh(x)} - 1 = 2^0 - 1 = 1 - 1 = 0.

The base case holds with equality!

• Inductive Step: Assume the lemma holds for all nodes with height < h. Consider an internal node x of height h >= 1 with two children, left and right.

What is the black-height of x's children?

- If a child is Black, its black-height is bh(x) - 1.

- If a child is Red, its black-height is bh(x) (since bh does not count red nodes).

In either case, each child has a black-height of at least bh(x) - 1.

By the induction hypothesis, each child's subtree contains at least 2^{bh(x) - 1} - 1 internal nodes.

Summing the nodes in x's subtree:

Total_Nodes(x) = 1 (node x itself) + Total_Nodes(left) + Total_Nodes(right)

Total_Nodes(x) >= 1 + [ 2^{bh(x) - 1} - 1 ] + [ 2^{bh(x) - 1} - 1 ]

Total_Nodes(x) >= 1 + 2 · 2^{bh(x) - 1} - 2

Total_Nodes(x) >= 2^{bh(x)} - 1.

The induction is complete. The lemma is proven.

Connecting Black-Height to Tree Height:

Let the root node have height h and black-height bh(root).

Applying the lemma to the root:

N >= 2^{bh(root)} - 1

N + 1 >= 2^{bh(root)}.

Taking log base 2:

bh(root) <= log2(N + 1).

Now consider Invariant 4: no two Red nodes can be adjacent on any path.

This means that on any simple path from the root to a leaf, red nodes can appear at most every other level.

Therefore, at least half of the nodes on the longest path must be Black:

bh(root) >= h / 2.

Combining the inequalities:

h / 2 <= bh(root) <= log2(N + 1)

h <= 2 · log2(N + 1).

Conclusion:

The height of a Red-Black tree is guaranteed never to exceed 2 · log2(N + 1).

Search queries are strictly guaranteed to execute in O(log N) time.

Red-Black Tree Insertion & Rebalancing Algorithm#

When inserting a new key into a Red-Black tree:

1. Perform standard BST insertion to place the new node Z as a leaf.
2. Color Z RED.

Why Red? Because adding a Red node adds zero black nodes to the path, preserving Invariant 5 (Black-Height) automatically!

1. If Z is the root: simply recolor Z to Black (satisfying Invariant 2).
2. If Z's parent P is Black: we are done! All 5 invariants are satisfied with zero rotations!
3. If Z's parent P is Red: Invariant 4 is violated (two consecutive red nodes: P and Z).

To fix this violation, we examine the color of Z's Uncle node U (the sibling of parent P, child of grandparent G):

Case 1: Uncle U is RED (Color Flip Case)

• Problem: Both Parent P and Uncle U are Red.
• Resolution: Recolor Parent P to Black, recolor Uncle U to Black, and recolor Grandparent G to Red.
• Why this works: Moving blackness from grandparent G down to children P and U preserves black-height along all subtrees.
• Propagation: Grandparent G is now Red. We repeat the rebalancing check at G (treating G as the new Z). If G's parent is also Red, the violation propagates upward. In the worst case, color flips propagate to the root, where the root is simply colored Black. Zero rotations performed!

Case 2: Uncle U is BLACK, Triangle Configuration (Zigzag)

• Configuration: Z is a right child and P is a left child of G (or vice versa).
• Resolution: Execute a rotation on Parent P (Left Rotation if Z is right child) to transform the triangle into a straight line.
• Node Z becomes the new parent of P. We immediately proceed to Case 3!

Case 3: Uncle U is BLACK, Line Configuration (Straight)

• Configuration: Z and P are both left children (or both right children) of G.
• Resolution:

1. Recolor Parent P to Black.

2. Recolor Grandparent G to Red.

3. Execute a Single Right Rotation on Grandparent G.

• Why this works: P becomes the new black root of the subtree, with red children Z and G. All paths retain their original black-height, and no two red nodes are adjacent.
• Rebalancing terminates immediately!

Crucial Efficiency Guarantee:

An insertion into a Red-Black tree requires at most 2 rotations in the absolute worst case!

Color flips may propagate up O(log N) levels, but rotations never exceed 2.

Red-Black Tree Deletion Mechanics#

Deleting a node requires removing the target and fixing any black-height violations:

• If the deleted node is Red: simply remove it. Zero invariants are violated.
• If the deleted node is Black: removing it removes a black node from that path, introducing a "Double-Black" deficiency.
• The algorithm resolves the double-black across 4 structural sibling cases.

Remarkable Property: Deleting a node from a Red-Black tree requires at most 3 rotations!

5. Production Systems & Industrial Architectural Applications#

Understanding balanced tree tradeoffs dictates data structure selection across operating systems and database storage engines.

+----------------------------------------------------------------------------------------------------+
|                                      AVL vs RED-BLACK TREE COMPARISON                              |
+----------------------------------------------------------------------------------------------------+
  Metric                        AVL Tree                           Red-Black Tree
  --------------------------------------------------------------------------------------------------
  Height Bound                  h <= 1.44 log2(N + 2)              h <= 2.0 log2(N + 1)
  Search Performance            Faster (~25% fewer pointer hops)   Slightly slower
  Insertion Rotations           At most 2                          At most 2
  Deletion Rotations            Up to O(log N)                     At most 3 (Strict constant!)
  Rebalancing Frequency         High (strict balance)              Low (amortized relaxations)
  Primary Use Cases             Read-heavy in-memory lookups       Write-intensive associative containers
+----------------------------------------------------------------------------------------------------+

The Linux Kernel Completely Fair Scheduler (CFS)#

The Linux kernel schedules millions of thread execution contexts using an augmented intrusive Red-Black tree (struct rb_node):

• Scheduling Metric: Each thread tracks its virtual runtime (vruntime). The CPU must always dispatch the thread that has consumed the least CPU time (the minimum vruntime).
• The Intrusive Tree Design: Linux embeds struct rb_node pointers directly inside the thread's task_struct, eliminating dynamic kmalloc allocations during thread scheduling.
• Cached Leftmost Optimization: The kernel maintains a cached pointer rb_leftmost pointing directly to the minimum node, providing instantaneous O(1) task dispatch.
• Why Red-Black over AVL? Threads constantly wake up, yield, sleep, and update their runtimes. The strict O(1) rotation bound (max 3 rotations on delete) of Red-Black trees guarantees deterministic sub-microsecond scheduling jitter.

C++ Standard Library `std::set` & `std::map`#

In GNU libstdc++ and LLVM libc++, std::map, std::set, std::multimap, and std::multiset are universally implemented as Red-Black trees:

• Iterator Invalidation Guarantees: The C++ standard mandates that inserting or removing an element from a std::map must NOT invalidate iterators or references pointing to other elements. Because Red-Black tree rotations manipulate only local pointers without relocating nodes in memory, all existing node references remain 100% valid.

6. Common Pitfalls & Misconceptions in Tree Implementations#

Engineers frequently fall into subtle traps when working with balanced search trees.

Pitfall 1: Forgetting to Update Heights After AVL Rotations#

In an AVL tree rotation, the parent-child relationship between nodes changes.

A common bug is returning the rotated node without recalculating heights:

// BUGGY ROTATION: Stale heights corrupt all subsequent balance checks!
Node* rotate_right(Node* y) {
    Node* x = y->left;
    y->left = x->right;
    x->right = y;
    return x; // Heights are wrong!
}

// CORRECT: Must recompute heights bottom-up (first y, then x!)
y->height = 1 + std::max(height(y->left), height(y->right));
x->height = 1 + std::max(height(x->left), height(x->right));

Pitfall 2: Assuming Red-Black Trees are Faster than AVL Trees for All Workloads#

A widespread myth is that Red-Black trees are strictly superior to AVL trees.

In reality:

• For read-heavy workloads (e.g., in-memory routing tables, linguistic dictionaries, read-to-write ratio > 90%), AVL trees outperform Red-Black trees by 15% to 25% because their tighter height bound (1.44 log2 N vs. 2.0 log2 N) requires fewer cache-line misses during lookups!
• Red-Black trees win only when write and delete frequencies are substantial.

Pitfall 3: Failing to Handle Strict Weak Ordering in Comparators#

When implementing custom key comparators for balanced trees (e.g., in std::map<Key, Value, Comparator>):

The comparator MUST satisfy Strict Weak Ordering:

• Irreflexivity: comp(a, a) must be false.
• Asymmetry: If comp(a, b) is true, comp(b, a) must be false.
• Transitivity: If comp(a, b) and comp(b, c) are true, comp(a, c) must be true.

If an engineer accidentally writes return a <= b; instead of return a < b;, comp(a, a) returns true. The tree invariant verification logic breaks down, causing corrupted node insertion paths, missing keys, and infinite loops!

7. Comprehensive Checkpoint Practice Problems & Complete Step-by-Step Solutions#

Mastery of tree balancing mechanics requires solving detailed structural tracing problems.

Problem 1 (AVL Tree Step-by-Step Insertion & Double Rotation Trace):

Construct an AVL tree by inserting the following sequence of integer keys into an initially empty tree:

Sequence = [ 14, 17, 11, 7, 53, 4, 13, 12 ]

1. Trace the tree topology step-by-step after each insertion.
2. For each insertion that triggers an imbalance:

- Identify the unbalanced node z.

- State the balance factor BF(z).

- Identify the imbalance type (LL, RR, LR, or RL).

- Show the intermediate rotation steps and the resulting balanced subtree.

1. Draw the final balanced AVL tree and report the height and balance factor of each node.

Solution:

Step 1: Step-by-Step Insertion Trace

• Insert 14:

Root is [14]. Height = 1, BF = 0.

• Insert 17:

[14] has right child [17]. Height = 2.

BF(14) = 0 - 1 = -1. BF(17) = 0. Balanced.

• Insert 11:

[14] has left child [11], right child [17]. Height = 2.

BF(14) = 1 - 1 = 0. Balanced.

• Insert 7:

Inserts as left child of [11].

Heights: [7] h=1, [11] h=2, [17] h=1, [14] h=3.

Balance Factors: BF(7) = 0, BF(11) = 1 - 0 = +1, BF(14) = 2 - 1 = +1. Balanced.

• Insert 53:

Inserts as right child of [17].

Heights: [53] h=1, [17] h=2, [7] h=1, [11] h=2, [14] h=3.

Balance Factors: BF(53) = 0, BF(17) = -1, BF(14) = 2 - 2 = 0. Balanced.

• Insert 4:

Inserts as left child of [7].

Check ancestors:

- Node [7]: left child [4] (h=1), right child None (h=0). BF(7) = 1 - 0 = +1. Height = 2.

- Node [11]: left child [7] (h=2), right child None (h=0). BF(11) = 2 - 0 = +2. IMBALANCE DETECTED at z = 11!

Identify Imbalance Type:

- Node z = 11 has BF = +2.

- Left child y = 7 has left child x = 4.

- Both steps are Left -> Case LL (Left-Left).

Resolution:

- Execute Single Right Rotation on z = 11:

[7] becomes root of this subtree, with left child [4] and right child [11].

Subtree becomes:

```

7

/ \

4 11

```

Connect back to root [14]:

Root [14] has left child [7] (h=2) and right child [17] (h=2).

BF(14) = 2 - 2 = 0. Overall tree balanced! Height = 3.

• Insert 13:

Inserts as right child of [11].

Node [11] has right child [13]. Height([11]) = 2. BF(11) = 0 - 1 = -1.

Node [7] has left child [4] (h=1) and right child [11] (h=2). Height([7]) = 3. BF(7) = 1 - 2 = -1.

Root [14] has left child [7] (h=3) and right child [17] (h=2). Height([14]) = 4. BF(14) = 3 - 2 = +1.

Balanced!

• Insert 12:

Inserts into [11]'s right subtree: 12 < 13, so 12 becomes left child of [13].

Walk up ancestors:

- Node [13]: left child [12] (h=1). BF(13) = 1 - 0 = +1. Height = 2.

- Node [11]: left child None (h=0), right child [13] (h=2). BF(11) = 0 - 2 = -2. IMBALANCE DETECTED at z = 11!

Identify Imbalance Type:

- Node z = 11 has BF = -2 (Right-heavy).

- Right child y = 13 has BF = +1 (Left-heavy).

- This is a Case RL (Right-Left) Double Rotation!

Resolution of Double Rotation:

1. Step 1 (Right Rotation on child y = 13):

Node [12] becomes right child of [11], with [13] as right child of [12].

Subtree: 11 -> right: 12 -> right: 13.

2. Step 2 (Left Rotation on z = 11):

Node [12] becomes root of subtree, with left child [11] and right child [13].

Subtree becomes:

```

12

/ \

11 13

```

Connect back to parent [7]:

Node [7] has right child [12] (h=2) and left child [4] (h=1). BF(7) = 1 - 2 = -1. Height = 3.

Root [14] has left child [7] (h=3) and right child [17] (h=2). BF(14) = 3 - 2 = +1. Height = 4.

All nodes balanced!

Step 2: Final Tree Topology

                  [ 14 ] (h=4, BF=+1)
                /        \
         [ 7 ] (h=3, BF=-1)   [ 17 ] (h=2, BF=-1)
        /     \                      \
     [ 4 ]    [ 12 ] (h=2, BF=0)     [ 53 ] (h=1, BF=0)
    (h=1,0)   /    \
           [ 11 ]  [ 13 ]
          (h=1,0)  (h=1,0)

Node Metrics:

• [4]: height = 1, BF = 0
• [11]: height = 1, BF = 0
• [13]: height = 1, BF = 0
• [53]: height = 1, BF = 0
• [12]: height = 2, BF = 0
• [17]: height = 2, BF = -1
• [7]: height = 3, BF = -1
• [14]: height = 4, BF = +1

Problem 2 (AVL Tree Minimum Nodes & Maximum Height Calculation):

An embedded system memory budget permits storing an AVL tree with at most N = 100 integer nodes.

1. Using the recurrence relation N(h) = 1 + N(h - 1) + N(h - 2), compute the exact minimum number of nodes required to form an AVL tree for heights h = 0, 1, 2, 3, 4, 5, 6, 7, 8.
2. Determine the maximum possible height h_max of an AVL tree containing exactly N = 100 nodes.
3. Compare this maximum height with the minimum possible height h_min achievable for N = 100 nodes in a perfectly balanced binary tree.

Solution:

Step 1: Compute Minimum Nodes N(h)

Base cases:

• N(0) = 1
• N(1) = 2

Use recurrence N(h) = 1 + N(h - 1) + N(h - 2):

• N(2) = 1 + N(1) + N(0) = 1 + 2 + 1 = 4
• N(3) = 1 + N(2) + N(1) = 1 + 4 + 2 = 7
• N(4) = 1 + N(3) + N(2) = 1 + 7 + 4 = 12
• N(5) = 1 + N(4) + N(3) = 1 + 12 + 7 = 20
• N(6) = 1 + N(5) + N(4) = 1 + 20 + 12 = 33
• N(7) = 1 + N(6) + N(5) = 1 + 33 + 20 = 54
• N(8) = 1 + N(7) + N(6) = 1 + 54 + 33 = 88
• N(9) = 1 + N(8) + N(7) = 1 + 88 + 54 = 143

Summary Table:

+--------+------+------+------+------+------+------+------+------+------+-------+
| Height | h=0  | h=1  | h=2  | h=3  | h=4  | h=5  | h=6  | h=7  | h=8  | h=9   |
+--------+------+------+------+------+------+------+------+------+------+-------+
| Min N  | 1    | 2    | 4    | 7    | 12   | 20   | 33   | 54   | 88   | 143   |
+--------+------+------+------+------+------+------+------+------+------+-------+

Step 2: Determine Maximum Height for N = 100 Nodes

We look for the largest height h such that N(h) <= 100:

• For h = 8: N(8) = 88 <= 100 (Possible!).
• For h = 9: N(9) = 143 > 100 (Impossible! A tree of height 9 requires at least 143 nodes).

Therefore, the maximum theoretical height of an AVL tree containing N = 100 nodes is h_max = 8.

Step 3: Comparison with Minimum Possible Height

In a perfectly balanced complete binary tree of N = 100 nodes:

h_min = floor(log2(N)) = floor(log2(100)) = floor(6.643856) = 6.

(A complete binary tree of height 6 can hold up to 2^{6+1} - 1 = 127 nodes).

Comparison:

• Minimum height = 6
• Maximum AVL height = 8

Even in the worst-case adversarial insertion order, an AVL tree of 100 nodes is at most 2 levels taller than a perfectly balanced binary tree!

Problem 3 (Red-Black Tree Insertion & Color Rebalancing Trace):

Trace the insertion of the following integer keys into an initially empty Red-Black tree:

Sequence = [ 10, 85, 15, 70, 20 ]

For each insertion:

1. Show the initial BST placement with the new node colored RED.
2. Identify any invariant violations.
3. State whether Case 1 (Uncle Red), Case 2 (Uncle Black, Triangle), or Case 3 (Uncle Black, Line) applies.
4. Show all recolorings and rotations step-by-step.
5. Draw the final Red-Black tree topology with node colors and verify that black-height is consistent across all paths.

Solution:

Step 1: Step-by-Step Insertion Trace

• Insert 10:

Root node. Invariant 2 requires root to be Black.

Tree: [10 (Black)].

• Insert 85:

Inserts as right child of [10], colored RED.

Parent [10] is Black. Zero violations.

Tree: [10 (B)] -> right: [85 (R)].

• Insert 15:

Standard BST insert: 15 > 10 (right), 15 < 85 (left).

Inserts as left child of [85], colored RED.

Violation: Parent [85] is RED, child [15] is RED (Consecutive Red Nodes, Invariant 4 violated!).

Inspect Uncle of [15]:

- Node Z = 15.

- Parent P = 85.

- Grandparent G = 10.

- Uncle U = left child of G = NIL (Black!).

Since Uncle is Black and configuration is G -> right (P) -> left (Z), this is a Triangle Configuration!

Step 1 (Transform Triangle to Line via Case 2):

- Perform Right Rotation on Parent P = 85.

- Subtree becomes: G(10) -> right: Z(15) -> right: P(85).

Now Z = 85, P = 15, G = 10. Straight line!

Step 2 (Case 3: Line Configuration):

- Recolor Parent P (15) to BLACK.

- Recolor Grandparent G (10) to RED.

- Perform Left Rotation on Grandparent G (10).

Node [15 (B)] becomes the new root of the subtree!

Left child is [10 (R)], right child is [85 (R)].

Verify root: [15] is root of tree and is Black.

Tree after inserting 15:

```

[ 15 (Black) ]

/ \

[ 10 (Red) ] [ 85 (Red) ]

```

• Insert 70:

Standard BST insert: 70 > 15 (right), 70 < 85 (left).

Inserts as left child of [85], colored RED.

Violation: Parent [85] is RED, child [70] is RED (Invariant 4 violated!).

Inspect Uncle of [70]:

- Node Z = 70.

- Parent P = 85 (Red).

- Grandparent G = 15 (Black).

- Uncle U = left child of G = [10 (Red)].

Case 1: Uncle U is RED (Color Flip Case)!

Resolution:

- Recolor Parent P (85) to BLACK.

- Recolor Uncle U (10) to BLACK.

- Recolor Grandparent G (15) to RED.

Check Root:

- Grandparent G (15) is the root of the tree.

- Invariant 2 requires the root to be Black.

- Recolor root [15] back to BLACK.

Zero rotations performed!

Tree after inserting 70:

```

[ 15 (Black) ]

/ \

[ 10 (Black) ] [ 85 (Black) ]

/

[ 70 (Red) ]

```

• Insert 20:

Standard BST insert: 20 > 15 (right), 20 < 85 (left), 20 < 70 (left).

Inserts as left child of [70], colored RED.

Violation: Parent [70] is RED, child [20] is RED (Invariant 4 violated!).

Inspect Uncle of [20]:

- Node Z = 20.

- Parent P = 70 (Red).

- Grandparent G = 85 (Black).

- Uncle U = right child of G = NIL (Black!).

Configuration:

- G(85) -> left: P(70) -> left: Z(20).

- Both are left children -> Case 3: Uncle Black, Line Configuration!

Resolution:

1. Recolor Parent P (70) to BLACK.

2. Recolor Grandparent G (85) to RED.

3. Execute Single Right Rotation on Grandparent G (85).

Subtree becomes:

Node [70 (Black)] becomes parent, with left child [20 (Red)] and right child [85 (Red)].

Connect back to root [15]:

Root [15] has right child [70].

Step 2: Final Tree Topology & Black-Height Verification

                [ 15 (Black) ]
               /              \
        [ 10 (Black) ]     [ 70 (Black) ]
                           /            \
                    [ 20 (Red) ]     [ 85 (Red) ]

Verify All 5 Red-Black Invariants:

1. Node Colors: All nodes are either Red or Black. (Satisfied)
2. Root Property: Root [15] is Black. (Satisfied)
3. Leaf Property: All NIL pointers are Black. (Satisfied)
4. Red Property: Red nodes are [20] and [85]. Their parent [70] is Black, and their children are NIL (Black). Zero consecutive red nodes! (Satisfied)
5. Black-Height Property:

- Path 1: Root(15) -> 10 -> NIL: Black nodes = [10, NIL] = 2.

- Path 2: Root(15) -> 70 -> 20 -> NIL: Black nodes = [70, NIL] = 2 (20 is Red).

- Path 3: Root(15) -> 70 -> 85 -> NIL: Black nodes = [70, NIL] = 2 (85 is Red).

Every simple path to a leaf has a black-height of exactly 2!

The tree is 100% valid.

Problem 4 (Black-Height Induction & Contradiction Proof):

An engineer claims to have constructed a valid Red-Black tree with the following properties:

• The tree contains N = 7 internal nodes.
• The height of the tree is h = 4.
• The root node has black-height bh(root) = 1.

1. Using the Red-Black Tree Black-Height theorem, prove whether it is mathematically possible for a valid Red-Black tree to have height h = 4 with bh(root) = 1.
2. Determine the maximum possible height h of any valid Red-Black tree with bh(root) = 1.
3. If an engineer wants to construct a Red-Black tree of height h = 4, what is the absolute minimum black-height bh(root) required?

Solution:

Step 1: Mathematical Feasibility of h = 4 with bh(root) = 1

Recall Invariant 4: No two Red nodes can appear consecutively on any path.

This implies that along any path from the root to a leaf:

• Red nodes can never be adjacent.
• Between any two Red nodes, there must be at least one Black node.
• A path of length h (containing h edges and h + 1 nodes from root to leaf) can contain at most:

Max_Red_Nodes = ceil( (h + 1) / 2 ).

Min_Black_Nodes = floor( (h + 1) / 2 ).

Furthermore, by definition, the black-height bh(root) counts all black nodes on the path to a leaf excluding the root itself.

Let h be the height of the tree (the number of edges on the longest path from root to leaf).

On the longest path of height h:

Every step from a red node must lead to a black node.

Therefore:

h <= 2 · bh(root).

Substitute bh(root) = 1:

h <= 2 · (1) = 2.

The maximum possible height of a Red-Black tree with black-height 1 is h = 2!

A height of h = 4 would require at least 3 black nodes along the path (since no two red nodes can touch).

Therefore, a tree of height h = 4 with bh(root) = 1 is MATHEMATICALLY IMPOSSIBLE. The claim is false.

Step 2: Maximum Height for bh(root) = 1

For bh(root) = 1:

• The root must be Black (Invariant 2).
• The children of the root can be Red.
• The children of those Red nodes must be Black leaves (NIL).

Longest path: Root(Black) -> Child(Red) -> Leaf(NIL Black).

Number of edges = 2 edges.

Thus, maximum height h = 2.

Step 3: Minimum Black-Height for Height h = 4

From the fundamental relationship:

h <= 2 · bh(root)

4 <= 2 · bh(root)

bh(root) >= 4 / 2 = 2.

The absolute minimum black-height required for a Red-Black tree to reach height h = 4 is bh(root) = 2.

An example path achieving h = 4 with bh = 2 is:

Root(Black) -> Red -> Black -> Red -> NIL(Black).

Edges = 4 (Height = 4).

Black nodes excluding root = 1 internal Black + 1 NIL Black = 2.