Splay Tree Amortized Analysis and Basic Rotation Operations: A Complete Guide

Splay trees achieve amortized O(log n) time for search, insert, and delete operations by moving accessed nodes to the root via a sequence of zig, zig-zig, and zig-zag rotations, with the amortized bound proven using a potential function based on subtree size logarithms.

The hzwer/shareoi repository maintains a curated collection of algorithm competition teaching materials, including a comprehensive slide deck dedicated to Splay tree amortized analysis. This article extracts the theoretical foundations and practical implementation details from 数据结构/Splay树及其应用_朱全民.ppt, explaining how self-adjusting rotations guarantee efficient amortized performance without explicit balance metadata.

What Is a Splay Tree?

A Splay tree is a self-adjusting binary search tree that stores no explicit balance information in its nodes. Unlike AVL or Red-Black trees that maintain strict height or color invariants, Splay trees reorganize through splaying—a sequence of rotations that moves an accessed node to the root. This heuristic ensures frequently accessed elements remain near the root, yielding amortized O(log n) time for all dictionary operations while maintaining implementation simplicity.

Core Rotation Operations

The efficiency of Splay trees relies on primitive single rotations and composite double rotations that constitute the splaying process.

Single Rotations (Left and Right)

Single rotations adjust local parent-child relationships while preserving the binary search tree invariant. These primitives are implemented in the rotateRight and rotateLeft functions.

• Right rotation at node x promotes its left child y to become the new subtree root, demoting x to the right child of y and rewiring the original right child of y to become the left child of x.
• Left rotation at node x performs the mirror operation, promoting its right child y to the root of the subtree.

Double Rotations: Zig, Zig-Zig, and Zig-Zag

Splaying combines single rotations into specific patterns that move target node z toward the root:

1. Zig: Performed when the parent of z is the tree root. A single left or right rotation brings z directly to the root.
2. Zig-Zig: Occurs when z and its parent p are both left children (or both right children) of their respective parents. The operation performs two same-direction rotations: first on the grandparent g, then on the parent p.
3. Zig-Zag: Occurs when z is a right child and its parent p is a left child (or vice versa). The operation performs two opposite-direction rotations: first on the parent p, then on the grandparent g.

According to the access lemma presented in 数据结构/Splay树及其应用_朱全民.ppt, zig-zig and zig-zag patterns are essential for the amortized bound because they reduce the potential function more aggressively than simple zig steps.

Splay Tree Amortized Analysis

The amortized analysis proves that any sequence of m operations on a tree with n nodes costs at most O(m log n) time, even though individual splay operations might require O(n) time in the worst case.

The Potential Function

The analysis employs a potential function Φ measuring tree "disorder." For each node x, define size s(x) as the number of nodes in the subtree rooted at x, and rank r(x) = log₂(s(x)). The tree potential equals the sum of all node ranks:

Φ = Σ r(x) for all nodes x in the tree

Balanced configurations yield low potential, while degenerate chains produce high potential.

The Access Lemma

The access lemma states that the amortized cost of splaying node x is at most 3·r'(x) - r(x) + 1, where r(x) denotes the pre-splay rank and r'(x) the post-splay rank. Since r'(x) ≤ log₂(n), this establishes the O(log n) amortized bound per operation.

The proof examines each splay step:

• Zig step: Amortized cost bounded by 3·r'(x) - r(x).
• Zig-zig step: Potential decrease compensates for both rotations.
• Zig-zag step: Similarly bounded by rank differences.

Because potential strictly decreases during zig-zig and zig-zag steps, expensive restructuring is amortized against previous cheap operations that accumulated potential.

Practical Implementation of Rotations

The following C++ implementation illustrates the rotation primitives and splay routine as conceptualized in 数据结构/Splay树及其应用_朱全民.ppt. This code maintains parent pointers to facilitate the bottom-up splaying required for amortized analysis.

// Node structure for a binary search tree
struct Node {
    int key;
    Node *left, *right, *parent;
    Node(int k) : key(k), left(nullptr), right(nullptr), parent(nullptr) {}
};

// ------- Single rotation (right) -------
void rotateRight(Node *x) {
    Node *y = x->left;               // y becomes new root of this subtree
    x->left = y->right;
    if (y->right) y->right->parent = x;
    y->parent = x->parent;
    if (!x->parent) ;                // x was root – caller must update root pointer
    else if (x == x->parent->right)  x->parent->right = y;
    else                             x->parent->left  = y;
    y->right = x;
    x->parent = y;
}

// ------- Single rotation (left) -------
void rotateLeft(Node *x) {
    Node *y = x->right;
    x->right = y->left;
    if (y->left) y->left->parent = x;
    y->parent = x->parent;
    if (!x->parent) ;
    else if (x == x->parent->left)  x->parent->left = y;
    else                             x->parent->right = y;
    y->left = x;
    x->parent = y;
}

// ------- Splay step (bringing node z to root) -------
void splay(Node *&root, Node *z) {
    while (z->parent) {
        Node *p = z->parent;
        Node *g = p->parent;
        if (!g) {                     // Zig
            if (z == p->left) rotateRight(p);
            else               rotateLeft(p);
        } else if ((z == p->left) == (p == g->left)) { // Zig‑Zig
            if (z == p->left) { rotateRight(g); rotateRight(p); }
            else               { rotateLeft(g);  rotateLeft(p);  }
        } else {                      // Zig‑Zag
            if (z == p->left) { rotateRight(p); rotateLeft(g); }
            else               { rotateLeft(p);  rotateRight(g); }
        }
    }
    root = z;                         // z is now the tree root
}

Explanation of the rotations

• Right rotation at node x promotes its left child y to become the new subtree root, moving x down to the right side of y.
• Left rotation at node x promotes its right child y to become the new subtree root, moving x down to the left side of y.
• The splay routine repeatedly applies zig, zig‑zig, or zig‑zag patterns until the accessed node becomes the overall root. Each double‑rotation reduces the potential function defined in the amortized analysis, ensuring the overall O(log n) amortized cost.

Applications and Related Resources

The hzwer/shareoi repository places Splay trees within a broader curriculum of advanced data structures for competitive programming. The primary resource 数据结构/Splay树及其应用_朱全民.ppt explores practical applications including dynamic order statistics, range reversal via implicit Splay trees, and link-cut trees for dynamic connectivity.

For comparative study, the repository provides related materials:

• Balanced BST alternatives: 数据结构/平衡树_王天懿.pptx covers AVL and Red-Black trees that maintain strict balance invariants rather than amortized bounds.
• Heap structures: 数据结构/左偏树的特点及其应用_黄源河.ppt discusses left-leaning heaps for priority queue operations.
• Foundational concepts: 数据结构/二叉树与其应用_朱全民.ppt establishes the binary tree prerequisites necessary for understanding rotation mechanics.

Summary

• Splay trees are self-adjusting binary search trees that move accessed nodes to the root via rotations, requiring no explicit balance metadata.
• Amortized analysis proves O(log n) time per operation using a potential function based on subtree size logarithms and the access lemma.
• Three splay patterns—zig, zig-zig, and zig-zag—systematically reduce potential while bringing target nodes to the root.
• Single rotations (left and right) form the primitive operations that rewire parent-child links while maintaining BST invariants.
• The hzwer/shareoi repository provides comprehensive teaching materials in 数据结构/Splay树及其应用_朱全民.ppt covering theory, implementation, and competitive programming applications.

Frequently Asked Questions

What is the amortized time complexity of Splay tree operations?

Splay tree operations have an amortized time complexity of O(log n) per operation, where n is the number of nodes. This bound holds for any sequence of m operations, resulting in a total cost of O(m log n), even though a single splay operation might require O(n) time in the worst case. The proof relies on the access lemma and a potential function measuring subtree size logarithms.

How do zig-zig and zig-zag rotations differ in Splay trees?

Zig-zig occurs when a node and its parent are both left children (or both right children) of their respective parents, requiring two same-direction rotations (first on the grandparent, then on the parent). Zig-zag occurs when a node is a right child but its parent is a left child (or vice versa), requiring two opposite-direction rotations (first on the parent, then on the grandparent). Both patterns are essential for the amortized O(log n) bound because they reduce the potential function more aggressively than simple zig steps.

Why don't Splay trees store balance information like AVL trees?

Splay trees eliminate the need for explicit balance fields (such as height or color bits) by using self-adjusting rotations that move frequently accessed nodes toward the root. The amortized analysis guarantees efficient performance without storing additional metadata, resulting in simpler code and less memory overhead per node compared to AVL or Red-Black trees. This trade-off accepts occasional linear-time operations in exchange for average-case efficiency and implementation simplicity.

Where can I find the original teaching materials on Splay trees?

The original lecture slides are located in the hzwer/shareoi repository at the path 数据结构/Splay树及其应用_朱全民.ppt. This file contains the complete theoretical exposition of Splay tree amortized analysis, rotation operations, and competitive programming applications. Related materials for comparative study include 数据结构/平衡树_王天懿.pptx for AVL/Red-Black trees and 数据结构/二叉树与其应用_朱全民.ppt for binary tree fundamentals.

{
  "mcpServers": {
    "instagit": {
      "command": "npx",
      "args": ["-y", "instagit@latest"]
    }
  }
}