Splay Tree

Tree Structures

O(log n) amortized time, O(n) space

Advanced

Self-adjusting BST that splays (rotates) accessed node to root, providing amortized O(log n).

Prerequisites:

Binary Search Tree

Tree Rotations

Amortized Analysis

Visualization

Interactive visualization for Splay Tree

Splay Tree Visualization

Self-adjusting BST that moves accessed elements to root via splaying

Insert values to build the splay tree

Operations: O(log n) amortized

How it works:

Every access (search/insert) splays node to root
Uses zig, zig-zig, and zig-zag rotations
Frequently accessed items stay near root
Excellent for non-uniform access patterns
No balance factor or color tracking needed

Interactive visualization with step-by-step execution

Implementation

Language:

1class SplayNode { constructor(public key:number, public l:SplayNode|null=null, public r:SplayNode|null=null){} }
2function splay(root:SplayNode|null, key:number):SplayNode|null{ if(!root||root.key===key) return root; if(key<root.key){ if(!root.l) return root; if(key<root.l.key){ root.l.l = splay(root.l.l,key); root = rotateRight(root); } else if(key>root.l.key){ root.l.r = splay(root.l.r,key); if(root.l.r) root.l = rotateLeft(root.l); } return root.l? rotateRight(root):root; } else { if(!root.r) return root; if(key>root.r.key){ root.r.r = splay(root.r.r,key); root = rotateLeft(root); } else if(key<root.r.key){ root.r.l = splay(root.r.l,key); if(root.r.l) root.r = rotateRight(root.r); } return root.r? rotateLeft(root):root; } }
3function rotateRight(y:SplayNode){ const x=y.l!; y.l=x.r; x.r=y; return x; }
4function rotateLeft(x:SplayNode){ const y=x.r!; x.r=y.l; y.l=x; return y; }
5function splayInsert(root:SplayNode|null, key:number):SplayNode{ if(!root) return new SplayNode(key); root = splay(root,key); if(root.key===key) return root; const n=new SplayNode(key); if(key<root.key){ n.r=root; n.l=root.l; root.l=null; } else { n.l=root; n.r=root.r; root.r=null; } return n; }

Deep Dive

Theoretical Foundation

Splay trees are self-adjusting BSTs. Any accessed node is rotated (splayed) to the root using zig, zig-zig, or zig-zag operations. Although a single operation can be O(n), the amortized complexity of a sequence of m operations on a tree of size n is O(m log n).

Complexity

Time

Best

O(1)

Average

O(log n)

Worst

O(n)

Space

Required

O(n)

Applications

Industry Use

Caches and self-adjusting dictionaries

Rope data structures / text editors

Dynamic trees (foundation for link-cut trees)

Use Cases

Caches

Adaptive access patterns

Related Algorithms

AVL Tree (Self-Balancing BST)

A self-balancing binary search tree where the heights of the two child subtrees of any node differ by at most one. Named after inventors Adelson-Velsky and Landis (1962), AVL trees guarantee O(log n) time for search, insert, and delete operations by maintaining balance through rotations. It was the first self-balancing binary search tree to be invented.

Tree Structures

Segment Tree (Range Query Tree)

Segment Tree is a binary tree data structure for storing intervals/segments that enables efficient range queries (sum, min, max, GCD) and updates in O(log n) time. Each node represents an interval, with leaves representing single elements. Essential for competitive programming, it solves problems like range sum queries with updates, which would be O(n) with arrays but becomes O(log n) with segment trees.

Tree Structures

Fenwick Tree (Binary Indexed Tree - BIT)

A data structure that can efficiently update elements and calculate prefix sums in O(log n) time. Also known as Binary Indexed Tree (BIT), invented by Peter Fenwick in 1994. Fenwick trees are more space-efficient and simpler than segment trees for range sum queries, using only O(n) space compared to segment tree's O(4n).

Tree Structures

Lowest Common Ancestor (LCA)

Lowest Common Ancestor (LCA) finds the deepest node that is an ancestor of two given nodes in a tree. This fundamental tree query operation has applications in computational biology (phylogenetic trees), version control systems (finding merge base), network routing, and range queries. Multiple algorithms exist: simple recursive O(n), binary lifting O(log n) per query after O(n log n) preprocessing, and Tarjan's offline algorithm for batch queries.

Tree Structures