Balanced BSTs

The AVL Property — Height Balance

Why Height Balance Implies $O(\log n)$ Height

We need to show that an AVL tree on $n$ nodes has height $O(\log n)$. Equivalently, we show that any height-$h$ AVL tree has at least $F(h)$ nodes where $F(h) = 2^{\Omega(h)}$.

Let $F(h)$ be the minimum number of nodes in any height-$h$ AVL tree. An AVL tree of height $h$ must have a root, a subtree of height $h-1$ (the taller child), and — because the tree is height-balanced — a subtree of at least height $h-2$ (the shorter child). So:

Solving: $F(h) \geq 2^{h/2}$. Therefore an AVL tree with $n$ nodes satisfies $n \geq F(h) \geq 2^{h/2}$, which gives $h \leq 2 \log_2 n = O(\log n)$.

Rotations — Restructuring Without Reordering

When a node becomes imbalanced (skew $\pm 2$), we need to change the tree's shape without changing its traversal order. The operation that does this is a rotation.

A rotation takes two adjacent nodes $B$ and $D$ (where $D$ is the right child of $B$, or vice versa), and swaps which one is the parent. Crucially, it relinkss only $O(1)$ pointers and preserves the traversal order exactly.

Traversal order before: $A, B, C, D, E$. Traversal order after: $A, B, C, D, E$. Identical — the rotation preserves order while changing depth. $A$ and $E$ move up/down one level; $C$ switches parents; $B$ and $D$ swap their parent-child relationship.

def subtree_rotate_left(B):     # O(1) — promote B's right child D
    """Left rotation: D becomes parent, B becomes D's left child."""
    assert B.right
    A, D  = B.left,  B.right
    C, E  = D.left,  D.right
    # swap items so B stays at same memory address (cleaner for parent pointers)
    B.item, D.item = D.item, B.item
    B, D = D, B                  # B now holds old D's item (root of subtree)
    D.left,  D.right = B, E      # D (old B node) gets B and E as children
    B.left,  B.right = A, C      # B (old D node) gets A and C as children
    if A: A.parent = B
    if E: E.parent = D
    B.subtree_update()           # update augmentations bottom-up
    D.subtree_update()

def subtree_rotate_right(D):    # O(1) — promote D's left child B
    """Right rotation: B becomes parent, D becomes B's right child."""
    assert D.left
    B, E  = D.left,  D.right
    A, C  = B.left,  B.right
    D.item, B.item = B.item, D.item
    D, B = B, D
    B.left,  B.right = A, D
    D.left,  D.right = C, E
    if A: A.parent = B
    if E: E.parent = D
    B.subtree_update()
    D.subtree_update()

// Left rotation: promote node's right child — O(1)
template<typename T>
void rotate_left(AVL_Node<T>* B) {
    assert(B->right);
    auto* D = static_cast<AVL_Node<T>*>(B->right);
    auto* A = B->left;
    auto* C = D->left;
    auto* E = D->right;
    // swap items so pointers from parent still point to "B"
    swap(B->item, D->item);
    swap(B, D);                     // B now holds D's item
    D->left  = B; D->right = E;     // D (old B) keeps its position
    B->left  = A; B->right = C;     // B (old D) holds D's old children
    if (A) A->parent = B;
    if (E) E->parent = D;
    B->update(); D->update();        // recompute height/size bottom-up
}

template<typename T>
void rotate_right(AVL_Node<T>* D) {
    assert(D->left);
    auto* B = static_cast<AVL_Node<T>*>(D->left);
    auto* A = B->left;
    auto* C = B->right;
    auto* E = D->right;
    swap(D->item, B->item);
    swap(D, B);
    B->left  = A; B->right = D;
    D->left  = C; D->right = E;
    if (A) A->parent = B;
    if (E) E->parent = D;
    B->update(); D->update();
}

Rebalancing — Three Cases

After inserting or deleting a leaf, only ancestors of that leaf can become imbalanced. We walk from the leaf to the root, rebalancing each node with skew $\pm 2$. The key insight: at most $O(\log n)$ nodes need attention (there are only $O(\log n)$ ancestors), and each rebalancing requires at most 2 rotations.

Consider a node $B$ with skew $+2$ (right subtree is taller). Its right child is $D$. Three sub-cases based on $D$'s skew:

The symmetric cases (skew $-2$) use right rotations instead. The complete rebalance logic:

def height(A):
    """Height of node A (-1 if A is None)."""
    return A.height if A else -1

def subtree_update(A):          # O(1) — recompute augmentations
    A.height = 1 + max(height(A.left), height(A.right))
    A.size   = 1 + (A.left.size  if A.left  else 0) \
                 + (A.right.size if A.right else 0)

def skew(A):                    # O(1)
    return height(A.right) - height(A.left)

def rebalance(A):               # O(1) — fix skew ±2 using ≤ 2 rotations
    if skew(A) == 2:
        if skew(A.right) < 0:          # Case 2: double rotation
            A.right.subtree_rotate_right()
        A.subtree_rotate_left()        # Case 1 or 2: single rotation
    elif skew(A) == -2:
        if skew(A.left) > 0:           # symmetric Case 2
            A.left.subtree_rotate_left()
        A.subtree_rotate_right()       # symmetric Case 1 or 2

def maintain(A):                # O(log n) — rebalance from A up to root
    """Called after any structural change at or below A."""
    rebalance(A)                # fix A if needed (O(1))
    subtree_update(A)           # recompute A's height and size (O(1))
    if A.parent:
        A.parent.maintain()     # propagate up the tree

template<typename T>
struct AVL_Node {
    T item;
    int height = 0, sz = 1;
    AVL_Node *left = nullptr, *right = nullptr, *parent = nullptr;
    AVL_Node(T x) : item(x) {}

    void update() {                      // O(1)
        int lh = left  ? left->height  : -1;
        int rh = right ? right->height : -1;
        height = 1 + max(lh, rh);
        sz = 1 + (left  ? left->sz  : 0)
                + (right ? right->sz : 0);
    }
    int skew() const {
        int lh = left  ? left->height  : -1;
        int rh = right ? right->height : -1;
        return rh - lh;
    }

    void rebalance() {                   // O(1) — at most 2 rotations
        if (skew() == 2) {
            if (static_cast<AVL_Node*>(right)->skew() < 0)
                rotate_right(static_cast<AVL_Node*>(right));
            rotate_left(this);
        } else if (skew() == -2) {
            if (static_cast<AVL_Node*>(left)->skew() > 0)
                rotate_left(static_cast<AVL_Node*>(left));
            rotate_right(this);
        }
    }

    void maintain() {                    // O(log n)
        rebalance();
        update();
        if (parent) parent->maintain();
    }
};

The Augmentation Framework

Every binary tree can be augmented with additional information stored at each node. The rule is clean: augment a node with any subtree property — something computable from the node's item and its two children's augmentations in $O(1)$ time.

If you can compute the property in $O(1)$ from children, you can maintain it during any rotation or leaf modification without changing the $O(\log n)$ operation cost. The subtree_update function is where augmentations live.

class Size_Node(Binary_Node):
    """AVL node augmented with subtree size — enables O(log n) get_at(i)."""

    def subtree_update(self):       # O(1) — called after every structural change
        super().subtree_update()    # recompute height first
        self.size = 1
        if self.left:  self.size += self.left.size
        if self.right: self.size += self.right.size

    def subtree_at(self, i):        # O(log n) — find i-th node in traversal order
        assert 0 <= i
        L = self.left.size if self.left else 0
        if i < L:
            return self.left.subtree_at(i)
        elif i > L:
            return self.right.subtree_at(i - L - 1)
        else:
            return self                         # i == L → this is the i-th node


# With Size_Node, a Sequence AVL supports all operations in O(log n):
# get_at(i)     → subtree_at(i).item
# insert_at(i)  → subtree_at(i-1).insert_after(new_node)
# delete_at(i)  → subtree_at(i).subtree_delete()

// AVL node augmented with subtree size
// Enables O(log n) get_at(i) for Sequence interface
template<typename T>
struct Size_AVL_Node : AVL_Node<T> {
    using Base = AVL_Node<T>;
    int size = 1;

    Size_AVL_Node(T x) : Base(x) {}

    void update() override {            // O(1)
        Base::update();                 // recompute height first
        size = 1;
        auto* L = static_cast<Size_AVL_Node*>(this->left);
        auto* R = static_cast<Size_AVL_Node*>(this->right);
        if (L) size += L->size;
        if (R) size += R->size;
    }

    // Find i-th node in traversal order — O(log n)
    Size_AVL_Node* subtree_at(int i) {
        int L = this->left ? static_cast<Size_AVL_Node*>(this->left)->size : 0;
        if      (i < L) return static_cast<Size_AVL_Node*>(this->left)->subtree_at(i);
        else if (i > L) return static_cast<Size_AVL_Node*>(this->right)->subtree_at(i - L - 1);
        else            return this;
    }
};

The Complete Performance Picture

(e) expected · Sequence AVL build is O(n) via the recursive median-split construction from Ch6.

Augmentation in Practice — The Bit-Counting Problem

The augmentation framework is general. As a final example beyond size and height: maintain a sequence of $n$ bits supporting two $O(\log n)$ operations: flip(i) and count_ones_upto(i) (number of 1-bits in the prefix up to index $i$).

Augment each node with subtree_ones — the count of 1-bits in its subtree. This is a valid subtree property: computed in $O(1)$ from children. After flipping bit $i$, update augmentations up the tree in $O(\log n)$. For count_ones_upto(i), walk down the tree accumulating ones from left subtrees along the path.

This pattern — augmented Sequence AVL for prefix operations — is used directly in practice for rank/select data structures, Fenwick trees (binary indexed trees), and segment trees. Every one of these is either an AVL-style balanced tree or can be understood as one.