Skip to content
Algorithm Atlas
Data StructuresAll categories
ExtendedSource checked

Splay Tree

Moves recently accessed nodes to the root using rotations.

Explore relationshipsOpen constellationBrowse atlas

Quick Facts

Compact metadata for implementation and discovery.

Category
Data Structures
Difficulty
Advanced
Family
Self-Adjusting Search Tree
Tier
Extended
Status
Verified
Review
Source Checked
Sources
1
Formulas
0
Relationships
3
Code example
Ready
Visualization
Ready

Overview

A splay tree adapts to access patterns by restructuring after each lookup, giving amortized logarithmic performance without stored balance metadata.

Core Concepts

splayingzig-zig rotationzig-zag rotationamortized cost

Quick facts

Complexity

Runtime and memory behavior at a glance.

Best

O(1)

Average

O(log n) amortized

Worst

O(n)

Space

O(n)

When to Use

  • Use when fast lookup needs splaying.
  • Use when the input matches the assumptions behind self-Adjusting Search Tree.

When Not to Use

  • Avoid when the operation mix does not benefit from the structure's maintenance cost.
  • Avoid when a simpler algorithm gives the required result with less setup.

What It Does

  • Moves recently accessed nodes to the root using rotations
  • Uses splaying and zig-zig rotation to guide the work.
  • Produces stored structure.

Use Cases

  • Fast lookup
  • Maintaining ordered data
  • Representing graphs or spatial data

Inputs

  • Items
  • Keys or indexes
  • Operations to support

Outputs

  • Stored structure
  • Query results
  • Updated state

Pseudocode

  1. 1.Prepare the inputs and state needed for Splay Tree.
  2. 2.Apply the splaying step while the stopping condition has not been met.
  3. 3.Update intermediate state and discard invalid candidates.
  4. 4.Return stored structure.

Canonical Example

Input
Splay Tree input with a small representative case
Output
Stored structure
Explanation
Splay Tree applies splaying to produce stored structure.

Implementation Notes

  • Test insertion, deletion, lookup, and boundary cases separately.
  • Keep the splaying step separate enough to test independently.

Common Pitfalls

  • Ignoring update costs can make a structure look faster than it is in practice.
  • Forgetting to check edge cases can make Splay Tree look correct on only ideal inputs.

Interactive Mechanism Walkthrough

Graph Frontier & Edge Relaxation

Show the structure layout and how operations move through or update it.

Splay Tree mechanism walkthrough step 1 of 4suvwxt
Step 1 of 4: Prepare the inputs and state needed for Splay Tree.
data-structures-mechanism

Notes

Splay Tree should be used with the assumptions and tradeoffs of self-Adjusting Search Tree in mind.

Sources (1)

What each reference supports for this entry.

Self-Adjusting Binary Search Trees

Paper

Original reference for splay trees, rotations, and amortized self-adjusting search-tree behavior.

Open source

Explore Next

Good next jumps from the relationship graph, ranked for useful discovery.

Open discoveryOpen map
Variant ofBinary Search Tree

Data Structures · Foundation

Splay Tree is a data-structure variant of Binary Search Tree with different update or query tradeoffs.

Compare with this
Alternative toAVL Tree

Data Structures · Core

Splay trees self-adjust by access, while AVL trees maintain explicit height balance.

Compare with this
Used byLink-Cut Tree

Data Structures · Specialized

Link-cut trees use splay trees to represent preferred paths in dynamic forests.

Compare with this

Relationships

View full relationship page
Alternative toAVL Tree

Splay trees self-adjust by access, while AVL trees maintain explicit height balance.

Variant ofBinary Search Tree

Splay Tree is a data-structure variant of Binary Search Tree with different update or query tradeoffs.

Related Algorithms

Binary Search TreeAVL TreeRed-Black Tree

Tags

Data StructureTreeBalanced TreeTree Balancing