AlgoScope

Splay Tree

A self-adjusting BST that moves each accessed node to the root.

Data structures, data structure, advanced
Zig-zig at 70.10203040506070xpg
Zig-zig at 70.10203040506070xpg

Splay Tree: A deep key splays to the root and halves the path

Decision, step 3 of 9

70 is the right child of 60, which is the right child of 50: the same side. Zig-zig: rotate 60 over 50 first, then 70 over 60.

Cost

Search
O(log n) amortized
Insert
O(log n) amortized
Delete
O(log n) amortized
Space
O(n)

Single operations may be O(n). Bounds are amortized.