Balanced Tree Operations - Learning Module

Loading content...

0/276

Delete with Rebalancing

The Deletion Challenge

If insertion threatens balance by adding weight to one side of the tree, deletion threatens it by removing weight—potentially from the 'wrong' side. While the insert-then-rebalance pattern applies to deletion as well, the details are significantly more complex.

Why deletion is harder than insertion:

Insertion always adds a leaf: The structural change is predictable—height can only increase
Deletion can remove internal nodes: We may need to find replacement nodes, recursively delete, and handle cascading height changes
Imbalance direction is less predictable: Removing a node from the right subtree can cause left-heavy imbalance
Multiple rebalancing operations may be needed: Unlike insertion, one rotation may not suffice

Despite these complications, the fundamental approach remains: delete as in a standard BST, then detect and repair any balance violations while walking back up the tree.

What You Will Learn

By the end of this page, you will understand:

• How standard BST deletion creates imbalance opportunities • Why deletion can require multiple rebalancing operations • How AVL trees handle deletion with rotations • How Red-Black trees use recoloring and rotations for deletion • The time complexity guarantees for deletion with rebalancing • Why deletion is O(log n) despite its additional complexity

BST Deletion Recap: The Three Cases

Before examining how balanced trees handle deletion, we must thoroughly understand standard BST deletion. The operation divides into three cases based on the structure of the node being deleted.

Case 1: Deleting a Leaf Node

The target node has no children. This is the simplest case—we simply remove the node and update its parent's pointer to null.

Before:         After deleting 5:
    10              10
   /  \            /  \
  5    15         ∅    15

Impact on balance: The height of the subtree rooted at the deleted node's parent may decrease by 1, but only if the deleted leaf was the only child. If a sibling exists, the subtree height may remain unchanged.

Case 2: Deleting a Node with One Child

The target node has exactly one child. We 'bypass' the node by connecting its parent directly to its only child.

Before:         After deleting 15:
    10              10
   /  \            /  \
  5    15         5    20
        \
         20

Impact on balance: Similar to Case 1—the height at the deletion point may decrease by 1.

Case 3: Deleting a Node with Two Children

The target node has both children. This is the complex case. We cannot simply remove the node without losing connectivity. The standard approach:

Find the inorder successor (smallest node in right subtree) or inorder predecessor (largest in left subtree)
Copy the successor's key into the target node
Recursively delete the successor (which has at most one child)

Before:         Find successor:     After deleting 10:
    10              10                  12
   /  \            /  \                /  \
  5    15         5    15             5    15
      /  \            /  \                   \
     12   20        12   20                   20

Impact on balance: The structural change occurs where the successor was originally located, not at the original target. This can cause imbalance far from where deletion was initiated.

The Cascade Effect

In Case 3, the actual structural modification happens at the successor's location, which may be deep in the tree. Any imbalance detection and repairs must begin from there, not from the original deletion target. This means the rebalancing path could start arbitrarily deep in the tree and propagate all the way to the root.

Deletion Complexity Factors

•Height can decrease: Unlike insertion (where height can only increase or stay same), deletion can decrease the height of subtrees
•Both subtrees may need checking: After insertion, we only check ancestors. After deletion, both subtrees' heights have potentially changed relative to each other
•Multiple rotations may be needed: A rotation that fixes imbalance at one node may cause imbalance at an ancestor—requiring another rotation
•Successor deletion is recursive: The two-child case involves a nested deletion, which can itself require rebalancing

How Deletion Creates Imbalance

When we insert a node, the imbalance (if any) is always on the side where we inserted—we added weight, so that side became heavier. Deletion works oppositely: we removed weight from one side, potentially making the other side heavier.

Consider this balanced tree:

         20(bf=0)
        /  \
      10    30(bf=0)
     /     /  \
    5    25    35

All balance factors are 0 (or the tree is height-balanced with small offsets). Now delete node 5:

         20(bf=-1)
        /  \
      10    30(bf=0)
           /  \
         25    35

Node 10 now has no children, height 1. Node 30 has height 2. Node 20's balance factor becomes height(left) - height(right) = 1 - 2 = -1. This is acceptable.

But now delete node 10:

         20(bf=-2)  ← IMBALANCED!
            \
             30(bf=0)
            /  \
          25    35

Node 20's left subtree has height 0 (empty), right subtree has height 2. Balance factor = 0 - 2 = -2. We have a right-heavy imbalance.

The imbalance is on the opposite side from the deletion.

This is the key difference from insertion. When we inserted, the heavy side was where we inserted. When we delete, the heavy side is where we didn't delete—the imbalance appears on the side that remained.

Insertion Imbalance

•Heavy side = insertion side
•Imbalance at first node with |bf| = 2
•One rotation typically suffices
•Fixed by rotating away from insertion

Deletion Imbalance

•Heavy side = opposite of deletion side
•Imbalance possible at multiple ancestors
•Multiple rotations may be needed
•Fixed by rotating toward the heavy side

Why multiple rotations may be needed:

After insertion, when we perform a rotation, the height of the subtree rooted at the rotation point typically returns to what it was before insertion. This means ancestors above that point see no height change—they remain balanced.

After deletion, a rotation fixes the local imbalance, but the subtree height may still be 1 less than before deletion. This height reduction propagates upward:

Before deletion:          After deletion:         After rotation:
       A (bf=0)             A (bf=-2)              A (bf=-1)  ← still unbalanced!
      / \                    \                        \
     X   B (bf=0)             B (bf=-1)                 C
        / \                    \                       / \
       Y   C                    C                     B   Z
          / \                  / \
         W   Z                W   Z

In this example, after deleting X and rotating to fix A, the subtree at A might still have reduced height, causing imbalance at A's parent. We must continue checking upward.

The O(log n) Rotations Worst Case

Unlike insertion (≤2 rotations), AVL deletion can require O(log n) rotations in the worst case—one at each level of the tree. This happens when each rotation still leaves the subtree height reduced, propagating the height change all the way to the root. Despite more rotations, the total work remains O(log n) since each rotation is O(1).

AVL Deletion: The Complete Algorithm

The AVL deletion algorithm follows the delete-then-rebalance pattern but must handle all the complexities we've identified. Here's the complete procedure:

Step 1: Locate and Delete (Standard BST)

Find the node to delete
Handle the three cases (leaf, one child, two children)
For two-child case, find successor, copy key, recursively delete successor

Step 2: Update Heights

After deletion, walk back up from the deletion point
Update each ancestor's height based on its children's heights

Step 3: Check Balance and Rebalance

At each ancestor, compute the balance factor
If |balance factor| ≤ 1, continue to next ancestor
If |balance factor| = 2, determine the case and rotate

Step 4: Continue to Root

Unlike insertion, don't stop after one rotation
Continue checking all ancestors up to the root

Determining the rotation case after deletion:

After deletion, if node Z has balance factor +2 (left-heavy), we look at Z's left child Y:

If Y's balance factor ≥ 0: Right rotation on Z (Left-Left case)
If Y's balance factor < 0: Left rotation on Y, then right rotation on Z (Left-Right case)

If Z has balance factor -2 (right-heavy), we look at Z's right child Y:

If Y's balance factor ≤ 0: Left rotation on Z (Right-Right case)
If Y's balance factor > 0: Right rotation on Y, then left rotation on Z (Right-Left case)

avl_deletion.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
def delete_avl(node, key):
    """
    Delete a key from AVL tree rooted at node.
    Returns the (potentially new) root after deletion and rebalancing.
    """
    # Step 1: Standard BST deletion
    if node is None:
        return node  # Key not found
    
    if key < node.key:
        node.left = delete_avl(node.left, key)
    elif key > node.key:
        node.right = delete_avl(node.right, key)
    else:
        # Found the node to delete
        
        # Case 1 & 2: Node with <= 1 child
        if node.left is None:
            return node.right  # Return right child (or None)
        elif node.right is None:
            return node.left   # Return left child
        
        # Case 3: Node with 2 children
        # Find inorder successor (smallest in right subtree)
        successor = find_min(node.right)
        
        # Copy successor's key to this node
        node.key = successor.key
        
        # Recursively delete the successor
        node.right = delete_avl(node.right, successor.key)
    
    # Step 2: Update height of current node
    update_height(node)
    
    # Step 3: Get balance factor and rebalance if needed
    balance = get_balance_factor(node)
    
    # Left-heavy (balance = +2)
    if balance > 1:
        # Check left child's balance to determine rotation type
        if get_balance_factor(node.left) >= 0:
            # Left-Left case
            return rotate_right(node)
        else:
            # Left-Right case
            node.left = rotate_left(node.left)
            return rotate_right(node)
    
    # Right-heavy (balance = -2)
    if balance < -1:
        # Check right child's balance to determine rotation type
        if get_balance_factor(node.right) <= 0:
            # Right-Right case
            return rotate_left(node)
        else:
            # Right-Left case
            node.right = rotate_right(node.right)
            return rotate_left(node)
    
    # Node is balanced
    return node
 
 
def find_min(node):
    """Find the node with minimum key in subtree rooted at node."""
    current = node
    while current.left is not None:
        current = current.left
    return current

The Recursive Nature

Notice how the recursive structure naturally handles Step 4 (continuing to root). Each recursive call returns, allowing the parent call to update its height and check its balance. The recursion stack effectively implements the 'walk back up to root' without explicit iteration. For the two-child case, the nested recursive deletion handles the successor's subtree, which may itself require rebalancing—all captured elegantly by the same recursive logic.

Complete AVL Deletion Example

Let's trace through a deletion that requires multiple rotations, demonstrating the complexity that doesn't arise in insertion.

Starting tree:

              20 (bf=0)
             /  \
           10    30 (bf=0)
          /  \     \
         5    15    50
        /           / \
       3          40   60
                       / \
                      55  70

Delete 15:

Node 15 has no children (leaf). Simply remove it.

              20 (bf=+1)
             /  \
           10    30 (bf=-1)
          /       \
         5         50
        /         /  \
       3        40    60
                     /  \
                   55    70

Node 10's balance factor becomes +1 (left-heavy but OK). Node 20's balance factor becomes +1. All balanced—no rotation needed.

Now delete 10:

Node 10 has one child (5). Replace 10 with 5.

              20 (bf=+2)  ← IMBALANCED!
             /  \
            5    30 (bf=-1)
           /       \
          3         50
                   /  \
                 40    60
                      /  \
                    55    70

Node 20 now has balance factor +2 (left subtree height 2, right subtree height 4... wait, let's recalculate).

Actually, left subtree (rooted at 5) has height 2. Right subtree (rooted at 30) has height 4. Balance factor = 2 - 4 = -2 (right-heavy).

So node 20 is right-heavy with bf = -2. Check right child (30): bf = -1 (right-heavy). This is the Right-Right case.

Perform left rotation on 20:

              30 (bf=0)
             /  \
           20    50 (bf=0)
          /  \   /  \
         5   ∅  40   60
        /           /  \
       3          55    70

Wait, where does 30's left subtree go? Let me redo this more carefully.

Correct analysis:

After deleting 10 and replacing with 5:

Subtree at 5: height 2 (5→3)
Subtree at 30: need to trace carefully
- 30→50 (h=1 for 30-50 edge)
- 50→40 (left): height 1
- 50→60 (right): height 2 (60→55 or 60→70)
- So subtree at 50 has height 3
- Subtree at 30 has height 4
Node 20: left height = 2, right height = 4, bf = -2 (right-heavy)

30's balance factor: left (null) = 0, right (50) = 3, bf = -3? That can't be right for a previously balanced tree.

Let me reconsider the original tree. I believe I made an error in the original tree's balance. Let me use a simpler example.

Corrected example - simpler tree:

Original balanced AVL tree:
          30 (bf=0)
         /  \
       20    40 (bf=+1)
      /  \   /
    10   25 35

All balance factors are within {-1, 0, +1}.

Delete 35:

Node 35 is a leaf. Remove it.

          30 (bf=+1)
         /  \
       20    40 (bf=0)
      /  \
    10   25

Node 40 now has no children, height 1. Node 30's left has height 2, right has height 1. Balance factor = +1. Still balanced.

Now delete 40:

          30 (bf=+2)  ← IMBALANCED!
         /
       20 (bf=0)
      /  \
    10   25

Node 30's left has height 2, right has height 0 (empty). Balance factor = +2 (left-heavy).

Check left child (20): balance factor = 0 (both children have height 1).

When left child's balance factor is 0 or +1, this is the Left-Left case. Perform right rotation on 30.

          20 (bf=0)
         /  \
       10    30 (bf=-1)
            /
          25

After rotation, all balance factors are within bounds. Tree is balanced.

Deletion Edge Cases

When the child on the heavy side has balance factor 0, either single or double rotation would work for deletion. The convention is typically to use the single rotation (LL or RR case), which is simpler. This is different from insertion, where balance factor 0 at the child doesn't occur because we just inserted there (the child would have bf = ±1 toward the insertion point).

Red-Black Deletion: A Color-Based Approach

Red-Black deletion is notoriously complex—one of the most intricate algorithms in standard data structure curricula. Rather than detailing every case (which would span multiple pages), we'll focus on understanding the key principles and why the complexity arises.

The fundamental challenge:

When we delete a node from a Red-Black tree, we must maintain all five Red-Black properties:

Every node is red or black ✓ (trivially maintained)
Root is black
All null leaves are black ✓ (trivially maintained)
Red nodes have black children (no red-red)
All paths from root to null have equal black-height

Property 5—the black-height invariant—is what makes deletion complicated.

The color problem:

If we delete a red node: Black-height is preserved! Red nodes don't contribute to black-height. Deletion is straightforward.
If we delete a black node: The path through that node loses one black node. Black-height is violated! We need to fix this.

The 'double-black' concept:

When a black node is deleted, we conceptually mark its replacement (or the null taking its place) as 'double-black'—meaning this position needs to contribute an extra black to satisfy property 5. The fixup process pushes this 'extra blackness' up the tree until it can be absorbed (by recoloring a red node to black) or pushed off the root.

Red-Black Deletion Case Summary
State	Sibling Color	Sibling's Children	Action
Double-black at x	Red	Any	Rotate sibling up, recolor, reduces to other cases
Double-black at x	Black	Both black	Recolor sibling red, push double-black up
Double-black at x	Black	Near child red, far black	Rotate sibling, recolor, reduces to next case
Double-black at x	Black	Far child red	Rotate parent, recolor, eliminates double-black

Why this complexity?

The black-height property is global—every path must have the same black-height. When we decrement black-height on one path, we must either:

Increment it elsewhere (impossible without adding nodes)
Decrement all other paths (recoloring)
Restructure so the path no longer exists as it did (rotation)

Option 2 (recoloring a black node to red on sibling's path) decrements sibling paths but may create a red-red violation or push the problem upward. Option 3 (rotation) moves nodes between paths, redistributing the black-height burden.

The saving grace:

Despite the complexity of the case analysis, Red-Black deletion has bounded complexity:

At most 3 rotations (constant)
At most O(log n) recolorings
Total time: O(log n)

In practice, most deletions are simple. The complex cases arise infrequently, and the constant factors are small enough that Red-Black trees remain highly practical.

The Practitioner's Perspective

Most engineers never implement Red-Black deletion themselves—they use library implementations. Understanding that it maintains O(log n) time with O(1) rotations is more valuable than memorizing every case. If you ever need to implement it, reference a textbook like CLRS (Introduction to Algorithms) which provides rigorous case-by-case analysis with correctness proofs.

Time Complexity of Delete with Rebalancing

Let's rigorously analyze the time complexity of deletion in balanced trees, accounting for all phases of the operation.

Phase 1: BST Deletion (Search + Restructure)

Finding the node: O(h) comparisons where h is tree height
For two-child case, finding successor: O(h) additional traversal
Pointer updates for removal: O(1)

Total for this phase: O(h) = O(log n)

Phase 2: Rebalancing (Walking Back Up)

AVL Trees:

Traverse from deletion point to root: O(h) nodes
At each node: compute balance factor O(1), update height O(1)
Rotations: O(1) each, but may need O(h) rotations total
Total: O(h) = O(log n)

Red-Black Trees:

Traverse from deletion point toward root: O(h) nodes in worst case
Recoloring: O(1) each, up to O(h) recolorings
Rotations: at most 3, regardless of tree size
Total: O(h) = O(log n)

Overall Time Complexity: O(log n)

Deletion Complexity Comparison
Metric	AVL Trees	Red-Black Trees
Time complexity	O(log n)	O(log n)
Space complexity	O(1) auxiliary	O(1) auxiliary
Maximum rotations	O(log n)	3
Maximum recolorings	N/A	O(log n)
Typical rotations	0-2	0-2
Average case	O(log n)	O(log n)

The rotation count difference explained:

Why does AVL deletion potentially need O(log n) rotations while Red-Black needs at most 3?

AVL: A rotation at node Z may reduce the subtree height by 1. If this height reduction propagates upward, Z's parent may become imbalanced and need another rotation. This can cascade all the way to the root.

Red-Black: The 'double-black' fix either absorbs the extra black (via recoloring or a specific rotation pattern) or pushes it up. When pushed up via recoloring, no rotation occurs. The cases that use rotations also eliminate the double-black, terminating the fixup. The structure of Red-Black properties ensures at most 3 rotations suffice.

Practical implications:

Despite AVL's worst-case O(log n) rotations, each rotation is O(1) work. The total time remains O(log n). In practice, AVL trees typically need 0-2 rotations per deletion. The theoretical difference matters more for specialized hardware (where rotations have non-trivial costs) than for general software applications.

Performance Guarantee Achieved

Both AVL and Red-Black trees achieve O(log n) deletion regardless of the tree's history or deletion pattern. This is the same guarantee as for insertion and search. The self-balancing mechanism ensures that no sequence of operations can degrade the tree into a structure with worse than logarithmic height.

Deletion vs. Insertion: A Comparison

Having studied both operations in depth, let's consolidate the key differences and similarities. Understanding these distinctions helps when reasoning about balanced tree behavior in practice.

What they share:

Both use the 'modify first, rebalance second' approach
Both traverse from the modification point back toward the root
Both use the same rotation primitives (left rotation, right rotation)
Both achieve O(log n) time complexity
Both preserve the BST property through careful rotation design
Both maintain the balance invariant through local checks and fixes

Where they differ:

Insertion vs. Deletion Comparison
Aspect	Insertion	Deletion
Direction of imbalance	Heavy on insertion side	Heavy on opposite side
Modification point	Always a new leaf	Can be any node; may involve successor
Height change	Subtree height may increase by 1	Subtree height may decrease by 1
Propagation (AVL)	Typically stops after first rotation	May need rotations at multiple levels
Max rotations (AVL)	2 (one double rotation)	O(log n)
Max rotations (RB)	2	3
Conceptual simplicity	Moderate	Complex (especially Red-Black)

Why insertion stops early but deletion may not:

After insertion + rotation: The subtree height typically returns to its pre-insertion value. Ancestors see no height change and remain balanced.

After deletion + rotation: The subtree height may still be 1 less than before deletion. This height change propagates upward, potentially causing imbalance at ancestors. Each rotation fixes one level but may not restore the height, so the chain continues.

Example illustrating the difference:

Before insertion/deletion:     After insertion of X:      After rotation:
        A (bf=+1)                   A (bf=+2)               B (bf=0)
       /                           /                       / \
      B (bf=0)                   B (bf=+1)                X   A
     / \                        /                             \
    C   D                      X                               D
                              (inserted here)

Height of subtree at A before: 3. After insertion and rotation: 3 (same). A's parent sees no change.

Before deletion:               After deletion of D:       After rotation:
        A (bf=+1)                   A (bf=+2)               B (bf=-1)
       /                           /                       / \
      B (bf=0)                   B (bf=+1)                C   A
     / \                        /                              
    C   D                      C                              
        (deleted)

Height of subtree at A before: 3. After deletion and rotation: 2. A's parent may now be imbalanced!

Engineering Implication

In workloads dominated by insertions, balanced trees may do fewer rotations overall. In workloads with heavy deletions, more rotations per operation are expected. For mixed workloads, the difference is usually negligible. This is one reason Red-Black trees are often preferred for general-purpose use—their O(1) rotation guarantee for both insertion and deletion simplifies performance reasoning.

Summary: Delete with Rebalancing

Deletion with rebalancing completes our understanding of how balanced trees maintain their invariants under modification. While more complex than insertion, the fundamental principles remain consistent: delete first, then detect and repair imbalance while walking back toward the root.

Key Takeaways

•Deletion uses standard BST deletion first: All three cases (leaf, one child, two children) apply before rebalancing begins
•Imbalance appears opposite to deletion side: Removing a node makes the remaining side relatively heavier
•Multiple rotations may be needed: Unlike insertion, height reduction can propagate upward requiring rotations at multiple levels
•AVL deletion can need O(log n) rotations: Each rotation is O(1), so total complexity remains O(log n)
•Red-Black deletion is complex but bounded: At most 3 rotations with O(log n) recolorings ensure O(log n) time
•Same rotation primitives apply: Left and right rotations preserve BST ordering while adjusting heights
•O(log n) guarantee holds for all operations: Deletion matches insertion and search in worst-case complexity

What's next:

With insertion and deletion covered, we've seen how balanced trees handle modifications. The next page examines search—an operation that, refreshingly, requires no rebalancing at all. We'll see how the balance guarantees translate directly into search performance without adding any overhead to the search operation itself.

Page Complete

You now understand the mechanics of deletion in balanced trees. The key insight is that while deletion is more complex than insertion—potentially requiring multiple rotations and involving intricate case analysis for Red-Black trees—the O(log n) time guarantee remains intact. Self-balancing trees provide this guarantee for all operations, making them reliable building blocks for systems that require consistent performance.