AVL trees, sets and skip lists

Learning outcomes

Identify AVL imbalance cases, perform basic set operations and explain the probabilistic structure of a skip list.

14.1 AVL balance

An AVL tree is a BST in which every node's left and right subtree heights differ by at most one. Define the balance factor as height(left) − height(right). Allowed values are −1, 0 and +1. The lab stores null height 0 and leaf height 1; this differs by a constant from edge-count height, but balance factors are unchanged.

After insertion, update heights on the path to the root. At the first unbalanced ancestor, identify the heavy path and rotate while preserving inorder key order.

For insertion 30, 20, 10, node 30 becomes left-heavy by two; a right rotation makes 20 the root. For 30, 10, 20, first rotate left at 10, then right at 30. Do not select a rotation by looking only at the imbalance sign; the child's shape matters too.

The laboratory inserts 30, 100, 150, 20, 10, 45, 80, 75, 120, 130, 125, 200, 75, ignoring the duplicate 75. Its final inorder sequence is 10, 20, 30, 45, 75, 80, 100, 120, 125, 130, 150, 200. Checking sorted order alone is insufficient: tests must also verify every stored height and every balance factor after each update.

14.2 AVL deletion reasoning

Delete as in a BST, then update heights and rebalance while returning towards the root. Unlike insertion, deletion can require repairs at multiple ancestors. The child balance factor may be zero, so insertion-key comparisons are not a valid deletion rotation rule.

Consider keys 100, 50, 150, 25, 75, 125, 175, 10, 30, 60. Deleting 75 replaces that one-child node with 60. At node 50, the left subtree rooted at 25 has edge-height 1 and the right leaf 60 has height 0; its balance factor is +1. The root remains balanced, so no rotation is required. An update is not obliged to rotate merely because the structure is an AVL tree.

AVL search, insertion and deletion take O(log n) worst-case time when the balance invariant is maintained. The supplied executable implements insertion; deletion above is a reasoning exercise, not a claim that the lab implements it.

14.3 Sets and list representation

A set contains distinct elements. Membership asks whether a value is present. Union contains elements in either set; intersection contains elements in both; difference A − B contains elements in A but not B.

For A = {1,3,5} and B = {3,4,5}, union is {1,3,4,5}, intersection {3,5}, and A − B is {1}. Difference is not commutative.

An unsorted list implements membership in O(n). Inserting a value while preserving uniqueness needs a membership test unless a stronger precondition is provided. For two sorted distinct-element lists of lengths m and n, two-pointer merging computes union or intersection in O(m + n) time, using output space proportional to the result.

Applications include removing duplicate identifiers, tracking visited graph vertices and comparing access lists. The appropriate representation depends on key range and workload: bit sets suit bounded integer universes, hash sets suit membership, and balanced trees also support ordered iteration.

14.4 Skip lists

A skip list has a sorted base-level list and additional forward links that skip over groups of elements. Random promotion gives some nodes taller “towers”. To search, begin at the highest level, move right while the next key is less than the target, then move down. At the base level, check the next key for equality.

Insertion records the predecessor at each visited level, chooses the new node's height and reconnects the relevant forward links. Deletion bypasses the target on every level where it occurs. Under a standard independent geometric-height model, search, insertion and deletion have expected O(log n) time and expected O(n) total link storage. A poor random outcome can still produce O(n) search time; this is an expected bound, not AVL-style deterministic balance. OpenDSA's skip-list explanation develops this distinction.

Level 2: HEAD ───────────────→ 20 ───────────────→ END
Level 1: HEAD ───→ 10 ──────→ 20 ──────→ 40 ───→ END
Level 0: HEAD → 5 → 10 → 15 → 20 → 30 → 40 → 50 → END

To search for 30, reach 20 on the upper level, descend when the next jump would overshoot, and then follow the base-level link to 30. The diagram is an example tower arrangement, not a uniquely determined structure for these keys.

Practice

1. Which rotation repairs insertion of 10, 30, 20 into an empty AVL tree?
2. Why does AVL deletion need to continue checking ancestors after one repair?
3. Compute union, intersection and both differences for {2,4,6} and {1,4,7}.
4. Contrast the worst-case guarantee of AVL search with the expected bound of skip-list search.
5. Explain how a sorted-list intersection advances pointers when the two current values differ.

/* C11. AVL insertion; heights count nodes (empty=0, leaf=1). */
#include <assert.h>
#include <stdbool.h>
#include <limits.h>
#include <stdio.h>
#include <stdlib.h>

typedef struct Node { int key, height; struct Node *left, *right; } Node;
static int height(const Node *p) { return p == NULL ? 0 : p->height; }
static int maximum(int a, int b) { return a > b ? a : b; }
static void update(Node *p) { p->height = 1 + maximum(height(p->left), height(p->right)); }
static Node *rotate_right(Node *y)
{
    Node *x = y->left, *middle = x->right;
    x->right = y; y->left = middle; update(y); update(x); return x;
}
static Node *rotate_left(Node *x)
{
    Node *y = x->right, *middle = y->left;
    y->left = x; x->right = middle; update(x); update(y); return y;
}
/* ok is set false only on allocation failure. Existing nodes remain owned. */
static Node *insert(Node *root, int key, bool *ok)
{
    if (root == NULL) {
        Node *p = malloc(sizeof *p);
        if (p == NULL) { *ok = false; return NULL; }
        *p = (Node){key, 1, NULL, NULL}; return p;
    }
    if (key < root->key) root->left = insert(root->left, key, ok);
    else if (key > root->key) root->right = insert(root->right, key, ok);
    else return root; /* Ignore duplicates. */
    update(root);
    int balance = height(root->left) - height(root->right);
    if (balance > 1) {
        if (key > root->left->key) root->left = rotate_left(root->left); /* LR */
        return rotate_right(root); /* LL or second step of LR */
    }
    if (balance < -1) {
        if (key < root->right->key) root->right = rotate_right(root->right); /* RL */
        return rotate_left(root); /* RR or second step of RL */
    }
    return root;
}
static void destroy(Node *p)
{
    if (p == NULL) return;
    destroy(p->left); destroy(p->right); free(p);
}
/* Independently recompute height and check strict BST ordering after each insert. */
static int validate(const Node *p, long long lower, long long upper)
{
    if (p == NULL) return 0;
    assert(lower < p->key && p->key < upper);
    int left = validate(p->left, lower, p->key);
    int right = validate(p->right, p->key, upper);
    assert(left - right >= -1 && left - right <= 1);
    assert(p->height == 1 + maximum(left, right));
    return 1 + maximum(left, right);
}
static void inorder(const Node *p, int out[], size_t *n)
{
    if (p == NULL) return;
    inorder(p->left, out, n); out[(*n)++] = p->key; inorder(p->right, out, n);
}
static bool check_rotation(const int keys[3])
{
    Node *root = NULL; bool ok = true;
    for (size_t i = 0; i < 3; ++i) {
        root = insert(root, keys[i], &ok);
        if (!ok) { destroy(root); return false; }
        (void)validate(root, LLONG_MIN, LLONG_MAX);
    }
    assert(root->key == 20 && root->left->key == 10 && root->right->key == 30);
    destroy(root); return true;
}
int main(void)
{
    const int cases[4][3] = {{30,20,10}, {10,20,30}, {30,10,20}, {10,30,20}};
    for (size_t i = 0; i < 4; ++i) if (!check_rotation(cases[i])) return EXIT_FAILURE;
    puts("LL, RR, LR and RL rotation tests passed");
    const int keys[] = {30,100,150,20,10,45,80,75,120,130,125,200,75};
    const int expected[] = {10,20,30,45,75,80,100,120,125,130,150,200};
    Node *root = NULL; bool ok = true;
    for (size_t i = 0; i < sizeof keys / sizeof keys[0]; ++i) {
        root = insert(root, keys[i], &ok);
        if (!ok) { destroy(root); return EXIT_FAILURE; }
        (void)validate(root, LLONG_MIN, LLONG_MAX);
        int partial[13]; size_t count = 0; inorder(root, partial, &count);
        for (size_t j = 1; j < count; ++j) assert(partial[j - 1] < partial[j]);
    }
    int out[13]; size_t n = 0; inorder(root, out, &n); assert(n == 12);
    printf("AVL inorder:");
    for (size_t i = 0; i < n; ++i) { assert(out[i] == expected[i]); printf(" %d", out[i]); }
    putchar('\n'); destroy(root);
    puts("AVL tests passed");
    return EXIT_SUCCESS;
}