AVL Tree Rebalancing in C: Pointer Techniques

This article examines the essential pointer manipulation techniques required to restore balance in an AVL tree implemented in C. It breaks down how memory addresses and child links are adjusted during single and double rotations, explores the use of return pointers versus double pointers (Node **) to update parent-child relationships, and outlines the correct sequence of operations necessary to maintain binary search tree invariant properties without causing memory leaks or dangling references.

Node Representation in C

An AVL tree node in C contains pointers to its left and right children, alongside stored data and an integer tracking node height:

typedef struct Node {
    int key;
    struct Node *left;
    struct Node *right;
    int height;
} Node;

Rebalancing is triggered when the balance factor—the height difference between the left and right subtrees (height(left) - height(right))—becomes greater than 1 or less than -1. Restoring this balance requires specific pointer reassignment patterns known as rotations.

Single Rotations

Single rotations resolve linear imbalances: the Left-Left (LL) case and the Right-Right (RR) case.

Right Rotation (LL Imbalance)

A right rotation occurs when a node becomes unbalanced due to an insertion into the left subtree of its left child. Three pointer references must be updated:

1. Identify the pivot: Let y be the unbalanced node, and let x = y->left be the pivot.
2. Preserve the inner subtree: Store x->right into a temporary pointer T2 (Node *T2 = x->right).
3. Reassign pointers:
   • Set x->right = y (making y the right child of x).
   • Set y->left = T2 (adopting T2 as the left child of y).

Node *rightRotate(Node *y) {
    Node *x = y->left;
    Node *T2 = x->right;

    // Pointer manipulation
    x->right = y;
    y->left = T2;

    // Update heights
    y->height = max(height(y->left), height(y->right)) + 1;
    x->height = max(height(x->left), height(x->right)) + 1;

    // Return new root of the subtree
    return x;
}

Left Rotation (RR Imbalance)

A left rotation is the exact mirror of the right rotation and resolves an insertion into the right subtree of a right child:

1. Let x be the unbalanced node, and let y = x->right be the pivot.
2. Store y->left into a temporary pointer T2.
3. Reassign pointers:
   • Set y->left = x.
   • Set x->right = T2.

Node *leftRotate(Node *x) {
    Node *y = x->right;
    Node *T2 = y->left;

    // Pointer manipulation
    y->left = x;
    x->right = T2;

    // Update heights
    x->height = max(height(x->left), height(x->right)) + 1;
    y->height = max(height(y->left), height(y->right)) + 1;

    // Return new root of the subtree
    return y;
}

Double Rotations

Zig-zag imbalances require double rotations: a rotation of the child node followed by a rotation of the unbalanced root.

Left-Right Rotation (LR Imbalance)

An LR imbalance occurs when a node y is left-heavy, but its left child x is right-heavy.

1. Perform a left rotation on the left child: y->left = leftRotate(y->left);.
2. Perform a right rotation on the unbalanced root: return rightRotate(y);.

Right-Left Rotation (RL Imbalance)

An RL imbalance occurs when a node x is right-heavy, but its right child y is left-heavy.

1. Perform a right rotation on the right child: x->right = rightRotate(x->right);.
2. Perform a left rotation on the unbalanced root: return leftRotate(x);.

Parent Pointer Updating Strategies

When a rotation changes which node serves as the root of a subtree, the parent must be updated to reference the new root. There are two primary techniques in C to accomplish this:

1. Recursive Value-Returning Pattern

The most common approach returns the updated node pointer up the recursion stack:

Node* insert(Node* node, int key) {
    // Normal BST insertion omitted for brevity...
    
    int balance = getBalance(node);

    // LL Case
    if (balance > 1 && key < node->left->key)
        return rightRotate(node);

    // RR Case
    if (balance < -1 && key > node->right->key)
        return leftRotate(node);

    // LR Case
    if (balance > 1 && key > node->left->key) {
        node->left = leftRotate(node->left);
        return rightRotate(node);
    }

    // RL Case
    if (balance < -1 && key < node->right->key) {
        node->right = rightRotate(node->right);
        return leftRotate(node);
    }

    return node;
}

The caller reassigns its own pointer (node->left = ... or node->right = ...) using the returned address, naturally propagating pointer adjustments up the tree.

2. Double-Pointer (Node **) Manipulation

In iterative implementations or scenarios without recursion, a pointer-to-pointer (Node **) is used. This enables direct modification of the parent's pointer to the current subtree without needing to backtrack or return values:

void rightRotateDoublePtr(Node **rootRef) {
    Node *y = *rootRef;
    Node *x = y->left;
    Node *T2 = x->right;

    x->right = y;
    y->left = T2;

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

    // Dereference to update the parent's child pointer directly
    *rootRef = x;
}

This technique modifies the memory address stored in the parent node (or the tree root) in place, avoiding assignment operations further up the call chain.