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

> Explore splay tree amortized analysis and basic rotation operations. Learn how zig zig-zig and zig-zag rotations achieve O(log n) performance with our comprehensive guide.

- Repository: [hzwer/shareoi](https://github.com/hzwer/shareoi)
- Tags: tutorial
- Published: 2026-03-03

---

**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.

```cpp
// 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.