Splay trees, or self-adjusting binary search trees, represent a fascinating approach to maintaining balance through continuous restructuring. Unlike rigid balancing schemes, splay trees reorganize themselves based on access patterns, achieving amortized logarithmic performance while remaining conceptually elegant.

Understanding Balance in Binary Search Trees

The concept of "balance" becomes clear when comparing tree structures. Consider a tree with 5 nodes:

• In a degenerate chain configuration, root-to-leaf traversal visits all 5 nodes, yielding O(n) complexity.
• In a properly balanced configuration, the maximum depth reduces to 3 nodes, delivering O(log n) performance.

Essentially, balance refers to uniform node distribution that minimizes tree height. Balanced BSTs maintain this property while preserving binary search tree ordering, enabling efficient operations.

What Are Splay Trees?

Developed by Robert Tarjan, splay trees acheive balance through the splay operation—a sequence of rotations that moves a target node to a specified position (typically the root). This process maintains BST properties while ensuring amortized O(log n) time for insertion, deletion, and search operations.

Core Operations

1. Rotation (Zig and Zag)

Rotation is the fundamental building block. It elevates a node by one level while preserving BST ordering:

• Right Rotation (Zig): A node moves up via its left child
• Left Rotation (Zag): A node moves up via its right child

During rotation, the elevated node becomes the parent of its former ancestor, and subtree attachments adjust automatically to maintain ordering. The key insight: inorder traversal remains unchanged after rotation.

2. The Splay Operation

Splaying moves node x to become a child of node target. The special case splay(x, 0) promotes x to the root.

Let parent = tree[x].parent and grandparent = tree[parent].parent. Four cases exist:

Case 1: parent == target

No action required—the node is already posisioned correctly.

Case 2: grandparent == target

A single rotation suffices. If x is the left child of parent, perform a right rotation on x; otherwise, left-rotate x.

Case 3: parent and grandparent are not target, and x, parent, grandparent are collinear

When the path forms a straight line (either all left children or all right children), perform double rotation: first rotate parent, then rotate x. This "folding" effect is crucial for amortized complexity.

Case 4: parent and grandparent are not target, and the path is zig-zag shaped

When the path alternates directions (left-right or right-left), rotate x twice. This handles the "zig-zag" scenario efficiently.

Main Tree Operations

Search and Promotion

To locate value v, traverse from the root using BST comparisons: move right if v exceeds the current node's value, otherwise move left. Upon finding the node or reaching a null child, splay the final node to the root.

Insertion

Search for the insertion position while tracking the parent node. If the value exists, increment its count. Otherwise, create a new node and attach it appropriately. Finally, splay the relevant node to the root.

Deletion

First locate and splay the target node to the root. This splits the tree into left and right subtrees. Find the maximum node in the left subtree (which has no right child) and splay it to become the new root. Attach the right subtree as its right child to complete the merge.

Rank Query

After splaying the target value to the root, its rank equals the size of its left subtree plus one. Sentinel nodes require adjusting this calculation.

Predecessor and Successor

Splay the reference value to the root. For predecessor: if root's value is less then the target, it's the answer; otherwise, descend to the left subtree and find the rightmost node. For successor, use the symmetric approach.

K-th Order Statistic

Starting from the root, compare k with left subtree size. If k exceeds left subtree size plus current node's count, subtract that sum from k and move right. Otherwise, if left subtree size covers k, move left. The answer lies where neither condition holds.

Implementation Details

Below is a complete C++ implementation for a standard balanced tree problem, demonstrating all concepts discussed.

#include <iostream>
#define INFINITY 0x7fffffff
using namespace std;

int operationCount;

namespace FastIO {
    char buffer[1<<21], *ptr1, *ptr2;
    #define getchar() (ptr1 == ptr2 && (ptr2 = (ptr1 = buffer) + fread(buffer, 1, 1<<21, stdin), ptr1 == ptr2) ? 0 : *ptr1++)
    
    inline int readInt() {
        int value = 0, sign = 1;
        char ch = getchar();
        while (ch < '0' || ch > '9') {
            if (ch == '-') sign = -1;
            ch = getchar();
        }
        while (ch >= '0' && ch <= '9') {
            value = (value << 1) + (value << 3) + (ch ^ 48);
            ch = getchar();
        }
        return value * sign;
    }
    
    inline void writeInt(int value, char terminator = '\n') {
        if (value < 0) {
            putchar('-');
            value = -value;
        }
        char digits[20];
        int len = 0;
        do {
            digits[len++] = value % 10 + '0';
            value /= 10;
        } while (value);
        while (len--) putchar(digits[len]);
        putchar(terminator);
    }
} using namespace FastIO;

namespace SplayTree {
    #define leftChild children[0]
    #define rightChild children[1]
    #define isRightChild(x) (nodes[nodes[x].parent].rightChild == x)
    
    const int MAX_NODES = 1000005;
    
    struct TreeNode {
        int value, parent, subtreeSize, duplicateCount;
        int children[2];
    };
    
    TreeNode nodes[MAX_NODES];
    int nodeCount = 0, root = 0;
    
    inline void initializeNode(int idx, int val, int parent) {
        nodes[idx].value = val;
        nodes[idx].parent = parent;
        nodes[idx].subtreeSize = nodes[idx].duplicateCount = 1;
        nodes[idx].children[0] = nodes[idx].children[1] = 0;
    }
    
    inline void updateSize(int idx) {
        nodes[idx].subtreeSize = nodes[nodes[idx].leftChild].subtreeSize + 
                                 nodes[nodes[idx].rightChild].subtreeSize + 
                                 nodes[idx].duplicateCount;
    }
    
    inline void performRotation(int x) {
        int y = nodes[x].parent;
        int z = nodes[y].parent;
        bool xIsRight = isRightChild(x);
        
        nodes[z].children[isRightChild(y)] = x;
        nodes[x].parent = z;
        
        nodes[y].children[xIsRight] = nodes[x].children[xIsRight ^ 1];
        nodes[nodes[x].children[xIsRight ^ 1]].parent = y;
        
        nodes[x].children[xIsRight ^ 1] = y;
        nodes[y].parent = x;
        
        updateSize(y);
        updateSize(x);
    }
    
    inline void splayNode(int x, int targetParent) {
        while (nodes[x].parent != targetParent) {
            int y = nodes[x].parent;
            int z = nodes[y].parent;
            if (z != targetParent) {
                if (isRightChild(x) ^ isRightChild(y)) performRotation(x);
                else performRotation(y);
            }
            performRotation(x);
        }
        if (targetParent == 0) root = x;
    }
    
    inline void searchAndSplay(int value) {
        int current = root;
        if (!current) return;
        while (nodes[current].value != value && nodes[current].children[value > nodes[current].value]) {
            current = nodes[current].children[value > nodes[current].value];
        }
        splayNode(current, 0);
    }
    
    inline void insertValue(int value) {
        int current = root, parent = 0;
        while (current && nodes[current].value != value) {
            parent = current;
            current = nodes[current].children[value > nodes[current].value];
        }
        if (current) {
            nodes[current].duplicateCount++;
        } else {
            current = ++nodeCount;
            initializeNode(current, value, parent);
            if (parent) {
                nodes[parent].children[value > nodes[parent].value] = current;
            }
        }
        splayNode(current, 0);
    }
    
    inline int findNeighbor(int value, bool findSuccessor) {
        searchAndSplay(value);
        int current = root;
        if (value < nodes[current].value && findSuccessor) return current;
        if (value > nodes[current].value && !findSuccessor) return current;
        current = nodes[current].children[findSuccessor];
        while (nodes[current].children[findSuccessor ^ 1]) {
            current = nodes[current].children[findSuccessor ^ 1];
        }
        splayNode(current, 0);
        return current;
    }
    
    inline void deleteValue(int value) {
        int pred = findNeighbor(value, false);
        int succ = findNeighbor(value, true);
        splayNode(pred, 0);
        splayNode(succ, pred);
        if (nodes[nodes[succ].leftChild].duplicateCount > 1) {
            nodes[nodes[succ].leftChild].duplicateCount--;
            splayNode(nodes[succ].leftChild, 0);
        } else {
            nodes[succ].leftChild = 0;
        }
    }
    
    inline int getRank(int value) {
        searchAndSplay(value);
        return nodes[nodes[root].leftChild].subtreeSize;
    }
    
    inline int findKth(int k) {
        int current = root;
        if (nodes[current].subtreeSize < k) return -1;
        while (true) {
            int leftSize = nodes[nodes[current].leftChild].subtreeSize;
            if (k > leftSize + nodes[current].duplicateCount) {
                k -= leftSize + nodes[current].duplicateCount;
                current = nodes[current].rightChild;
            } else {
                if (leftSize >= k) {
                    current = nodes[current].leftChild;
                } else {
                    splayNode(current, 0);
                    return nodes[current].value;
                }
            }
        }
    }
} using namespace SplayTree;

inline void processOperation() {
    int operation = readInt(), x = readInt();
    if (operation == 1) insertValue(x);
    else if (operation == 2) deleteValue(x);
    else if (operation == 3) {
        insertValue(x);
        writeInt(getRank(x) + 1);
        deleteValue(x);
    }
    else if (operation == 4) writeInt(findKth(x + 1));
    else if (operation == 5) writeInt(nodes[findNeighbor(x, false)].value);
    else if (operation == 6) writeInt(nodes[findNeighbor(x, true)].value);
}

int main() {
    insertValue(-INFINITY);
    insertValue(INFINITY);
    operationCount = readInt();
    while (operationCount--) processOperation();
    return 0;
}

Code Structure Analysis

Framework and I/O Optimization

The implementation uses separate namespaces for I/O optimization and tree logic. Fast I/O significantly improves performance for competitive programming contexts. The main function initializes sentinel nodes (positive and negative infinity) before processing operations, preventing edge cases involving empty subtrees.

Node Representation

Each node stores:

• value: The key value
• parent: Parent node index
• subtreeSize: Total nodes in subtree including duplicates
• duplicateCount: Occurrences of the same value
• children[2]: Left and right child indices

The children[value > nodes[current].value] indexing technique elegantly handles direction selection without conditional statements.

Helper Functions

initializeNode sets up new nodes with default values. updateSize recalculates subtree sizes after structural changes, crucial for rank and selection queries.

Rotation and Splaying

performRotation executes single rotations generically, determining direction through the isRightChild macro. splayNode implements the four splaying cases, with special handling for the root update.

Tree Operations

Each public operation follows the pattern: locate relevant nodes, perform splaying, execute logic, and maintain invariants. The findNeighbor function cleverly handles both predecessor and successor queries through its boolean parameter.

Sentinel Impact

Sentinel nodes simplify boundary conditions but require adjustments:

• Rank queries return left subtree size directly (the sentinel occupies position 0)
• K-th queries use k + 1 to skip the negative infinity sentinel
• Predecessor/successor functions work with values directly without temporary insertion

Amortized Complexity

The splay operation's folding strategy ensures that frequently accessed nodes remain near the root, providing the O(log n) amortized bound. While individual operations might be linear, the aggregate cost over a sequence remains logarithmic per operation.

Interesting Application: Splay Sort

An unconventional sorting approach emerges from splay tree operations: insert all elements into a splay tree, then repeatedly extract the k-th smallest element. This yields O(n log n) complexity, matching quicksort and mergesort. Each insertion costs O(log n), and each k-th query also costs O(log n) amortized. This demonstrates how data structure operations can compose into novel algorithms.