Introduction

A Binary Search Tree (BST) is defined as follows:

1. An empty tree is a BST.
2. If the left subtree of a BST is non-empty, all keys in the left subtree are less than the root's key.
3. If the right subtree of a BST is non-empty, all keys in the right subtree are greater than the root's key.
4. Both left and right subtrees must also be BSTs.

The time complexity of basic operations on a BST is proportional to the tree's height. For a tree with $n$ nodes, the optimal time complexity is $O(\log n)$.

However, if the tree degenerates into a linked list (chain), the time complexity degrades to $O(n)$, which is unacceptable for efficient operations. This motivated the development of balanced trees, which maintain a relatively balanced BST structure.

While Splay trees do not guarantee strict balance at all times, they ensure that the amortized time complexity of each operation is $O(\log n)$, making them effectively balanced binary search trees through self-adjustment.

Rotation Operasions

Splay trees use rotations to adjust the tree structure. There are two fundamental rotations:

• ZIG (Right Rotation): Rotates a node upward to the right
• ZAG (Left Rotation): Rotates a node upward to the left

The general rotation process maintains the BST property while changing the tree topology. Below is a unified rotation implementation:

struct Node {
    int key, frequency, size;
    int parent, left, right;
} tree[MAX_NODES];

int nodeCount = 0, root = 0;

int getSize(int idx) {
    return idx ? tree[idx].size : 0;
}

void updateSize(int idx) {
    if (idx) {
        tree[idx].size = tree[idx].frequency + getSize(tree[idx].left) + getSize(tree[idx].right);
    }
}

// Returns 0 for left child, 1 for right child
int getDirection(int parent, int child) {
    return tree[parent].right == child ? 1 : 0;
}

void performRotation(int current) {
    int p = tree[current].parent;
    int g = tree[p].parent;
    int dir = getDirection(p, current);
    
    // Move current's opposite child to parent
    int oppositeChild = dir ? tree[current].left : tree[current].right;
    if (dir) {
        tree[p].right = oppositeChild;
    } else {
        tree[p].left = oppositeChild;
    }
    if (oppositeChild) {
        tree[oppositeChild].parent = p;
    }
    
    // Move parent under current
    if (dir) {
        tree[current].left = p;
    } else {
        tree[current].right = p;
    }
    tree[p].parent = current;
    
    // Update grandparent connection
    tree[current].parent = g;
    if (g) {
        if (tree[g].left == p) {
            tree[g].left = current;
        } else {
            tree[g].right = current;
        }
    }
    
    updateSize(p);
    updateSize(current);
}

The Splay Operation

The core operation of a Splay tree is splaying: moving a specified node to the root (or to a specific ancestor) through a series of rotations.

There are several cases depending on the relative positions of the target node, its parent, and its grandparent:

1. Zig: Parent is root (single rotation)
2. Zig-Zig: Node and parent are both left children or both right children
3. Zig-Zag: Node and parent are on opposite sides

The standrad splay-to-root implementation:

void splayNode(int target, int ancestor) {
    while (tree[target].parent != ancestor) {
        int p = tree[target].parent;
        int gp = tree[p].parent;
        
        if (gp != ancestor) {
            // Check for Zig-Zig vs Zig-Zag
            int targetDir = getDirection(p, target);
            int parentDir = getDirection(gp, p);
            
            if (targetDir == parentDir) {
                performRotation(p);  // Zig-Zig: rotate parent first
            } else {
                performRotation(target);  // Zig-Zag: rotate target first
            }
        }
        performRotation(target);
    }
    
    if (ancestor == 0) {
        root = target;
    }
}

Insertion

Insertion follows standard BST rules: traverse left if the new key is smaller, right if larger. If a duplicate is found, increment the frequency counter. Otherwise, create a new node at the appropriate null position. After insertion, splay the node to the root.

void insertValue(int key) {
    if (root == 0) {
        root = ++nodeCount;
        tree[root].key = key;
        tree[root].frequency = 1;
        updateSize(root);
        return;
    }
    
    int current = root;
    int last = 0;
    
    while (true) {
        if (tree[current].key == key) {
            tree[current].frequency++;
            updateSize(current);
            updateSize(last);
            splayNode(current, 0);
            break;
        }
        
        last = current;
        int direction = (tree[current].key < key) ? 1 : 0;
        int next = direction ? tree[current].right : tree[current].left;
        
        if (next == 0) {
            nodeCount++;
            tree[nodeCount].key = key;
            tree[nodeCount].frequency = 1;
            tree[nodeCount].parent = last;
            if (direction) {
                tree[last].right = nodeCount;
            } else {
                tree[last].left = nodeCount;
            }
            updateSize(nodeCount);
            updateSize(last);
            splayNode(nodeCount, 0);
            break;
        }
        current = next;
    }
}

Querying the Rank of a Value

To find the rank of value $k$ (its position in the sorted order), traverse the tree while accumulating the sizes of left subtrees and frequencies of visited nodes.

int getRank(int key) {
    int rank = 0;
    int current = root;
    
    while (current != 0) {
        if (key < tree[current].key) {
            current = tree[current].left;
        } else {
            rank += getSize(tree[current].left);
            if (key == tree[current].key) {
                splayNode(current, 0);
                return rank + 1;
            }
            rank += tree[current].frequency;
            current = tree[current].right;
        }
    }
    return rank + 1;  // Return would-be rank if not found
}

Finding the k-th Element

To find the element with rank $k$, traverse the tree comparing $k$ with the size of the left subtree:

int findKth(int k) {
    int current = root;
    
    while (current != 0) {
        int leftSize = getSize(tree[current].left);
        
        if (k <= leftSize) {
            current = tree[current].left;
        } else if (k <= leftSize + tree[current].frequency) {
            splayNode(current, 0);
            return tree[current].key;
        } else {
            k -= leftSize + tree[current].frequency;
            current = tree[current].right;
        }
    }
    return -1;  // k is out of bounds
}

Summary

Splay trees provide efficient amortized performance by moving frequently accessed nodes closer to the root. Through rotation operations and the splaying mechanism, they maintain $O(\log n)$ amortized time complexity for insertion, delesion, and search operations, making them valuable in scenarios where certain elements are accessed more frequently than others.