Splay Tree
A self-adjusting BST that moves each accessed node to the root.
Splay Tree: A deep key splays to the root and halves the path
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.