Lesson 10 · Non-linear structures

AVL Trees

AVL Trees automatically rebalance themselves during insertions and deletions to guarantee logarithmic search times under all conditions.

The Balance Factor

An AVL Tree prevents the worst-case O(N) degradation of standard BSTs by strictly maintaining balance. It tracks the 'balance factor' of every node, defined as the height of its left subtree minus the height of its right subtree. In an AVL tree, this factor must always be -1, 0, or 1.

Detecting Imbalance

After inserting or deleting a node, the tree updates the heights of its ancestors. If any ancestor's balance factor becomes +2 or -2, the AVL property is violated. The tree must immediately restructure itself at this node to restore the balance factor without breaking the BST ordering.

Key reference

Terms, operations, and practical uses

Balance Mechanics

Balance FactorCalculated as the height of the left subtree minus the height of the right subtree. Must be -1, 0, or 1.
Height TrackingEach node actively stores its height, which is updated whenever its children are modified.
Imbalance DetectionChecked on the path back to the root after an insertion/deletion. Triggered if a balance factor reaches +2 or -2.

Rotations

Right Rotation (LL)Performed when a node is unbalanced due to an insertion in the left child's left subtree. The left child becomes the new root.
Left Rotation (RR)Performed when a node is unbalanced due to an insertion in the right child's right subtree.
Left-Right Rotation (LR)A double rotation (Left on child, Right on parent) used when the insertion is in the left child's right subtree.

Complexity

SearchStrictly O(log N) because the height is mathematically guaranteed to be proportional to log(N).
InsertionO(log N) to find the spot and update heights, requiring at most two rotations to rebalance.
DeletionO(log N), but unlike insertion, a deletion might trigger O(log N) cascading rotations all the way to the root.

Code example

Repair an AVL tree with a right rotation

class AVLNode:
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None
        self.height = 1

def height(node):
    return node.height if node else 0

def balance(node):
    return height(node.left) - height(node.right) if node else 0

def rotate_right(y):
    x = y.left
    y.left = x.right
    x.right = y
    y.height = 1 + max(height(y.left), height(y.right))
    x.height = 1 + max(height(x.left), height(x.right))
    return x

class AVLTree:
    def insert(self, root, key):
        if not root:
            return AVLNode(key)
        if key < root.key:
            root.left = self.insert(root.left, key)
        else:
            root.right = self.insert(root.right, key)
        root.height = 1 + max(height(root.left), height(root.right))
        # Left-left case: one right rotation restores the balance factor
        if balance(root) > 1 and key < root.left.key:
            return rotate_right(root)
        return root

tree = AVLTree()
root = None
for key in (3, 2, 1):
    root = tree.insert(root, key)
print('Root after rotation:', root.key)

struct AVLNode {
    int key, height;
    AVLNode *left, *right;
    explicit AVLNode(int key) : key(key), height(1), left(nullptr), right(nullptr) {}
};

class AVLTree {
public:
    AVLNode* insert(AVLNode* node, int key) {
        // A complete implementation performs BST insertion, updates height, and rotates.
        return node ? node : new AVLNode(key);
    }
};

class AVLTree {
    static class Node {
        int key, height = 1;
        Node left, right;
        Node(int key) { this.key = key; }
    }
    Node insert(Node node, int key) {
        // A complete implementation performs BST insertion, updates height, and rotates.
        return node != null ? node : new Node(key);
    }
}

Inputinsert 3, 2, 1

OutputRoot after rotation: 2

Example

Run the example step by step

Output

Tree Rotations

Restructuring is achieved via 'rotations'. A rotation changes the root of a subtree while preserving the in-order relationship of the elements. Depending on where the imbalance occurred, the tree will perform a Left, Right, Left-Right, or Right-Left rotation.

Strict Balance Guarantee

Because AVL trees enforce a strict balance factor, they tend to be perfectly bushy. This guarantees that lookup operations are incredibly fast. However, this strictness means insertions and deletions might trigger multiple rotations, adding a small constant overhead to write-heavy workloads.