Tree Rotations & AVL Trees: Balance Factors, LL/RR/LR/RL Rebalancing & Fibonacci Height Bound

Local Algebra of Rotations & The Four AVL Rebalancing Cases

Define the height of a null subtree as $-1$ and a leaf as $0$, so $h(u) = 1 + \max(h(u.\text{left}), h(u.\text{right}))$. The balance factor is $\text{bf}(u) = h(u.\text{left}) - h(u.\text{right}) \in \{-1, 0, +1\}$. When an insertion or deletion pushes $\text{bf}(z)$ to $+2$ (left-heavy) or $-2$ (right-heavy) at the lowest unbalanced ancestor $z$, let $y$ be the taller child of $z$ and $x$ be the taller child of $y$:

• Left-Left (LL, Outer): $\text{bf}(z) = +2$ and $\text{bf}(y) \ge 0$. A single rotateRight(z) restores balance and reduces the subtree height by $1$.
• Right-Right (RR, Outer): $\text{bf}(z) = -2$ and $\text{bf}(y) \le 0$. A single rotateLeft(z) restores balance.
• Left-Right (LR, Inner Zig-Zag): $\text{bf}(z) = +2$ and $\text{bf}(y) = -1$. A single right rotation on $z$ fails because the heavy grandchild $x = y.\text{right}$ stays at the same depth! We must perform a double rotation: rotateLeft(y) followed by rotateRight(z), lifting $x$ to the root of the subtree.
• Right-Left (RL, Inner Zig-Zag): $\text{bf}(z) = -2$ and $\text{bf}(y) = +1$. Execute rotateRight(y) followed by rotateLeft(z).

Implementation: Clean AVL Rotations & Rebalance Engine

// C++20: Self-Balancing AVL Tree Core with LL, RR, LR, RL Rebalancing
#include <algorithm>
#include <cstdint>

struct AVLNode {
    int key;
    int32_t height = 0; // Leaf has height 0; nullptr has height -1
    AVLNode *left = nullptr, *right = nullptr;
    explicit AVLNode(int k) : key(k) {}
};

inline int32_t h(const AVLNode* n) noexcept { return n ? n->height : -1; }
inline int32_t bf(const AVLNode* n) noexcept { return n ? (h(n->left) - h(n->right)) : 0; }
inline void pullHeight(AVLNode* n) noexcept { n->height = 1 + std::max(h(n->left), h(n->right)); }

AVLNode* rotateRight(AVLNode* z) noexcept {
    AVLNode* y = z->left;
    z->left = y->right;
    y->right = z;
    pullHeight(z); // Must update lower node z BEFORE new root y!
    pullHeight(y);
    return y;
}

AVLNode* rotateLeft(AVLNode* z) noexcept {
    AVLNode* y = z->right;
    z->right = y->left;
    y->left = z;
    pullHeight(z);
    pullHeight(y);
    return y;
}

AVLNode* rebalance(AVLNode* u) noexcept {
    pullHeight(u);
    int32_t balance = bf(u);
    if (balance > 1) { // Left-heavy (+2)
        if (bf(u->left) < 0) u->left = rotateLeft(u->left); // LR -> LL
        return rotateRight(u);
    }
    if (balance < -1) { // Right-heavy (-2)
        if (bf(u->right) > 0) u->right = rotateRight(u->right); // RL -> RR
        return rotateLeft(u);
    }
    return u;
}