Splay Tree
A self-adjusting BST that moves each accessed node to the root.
Decision · step 3 of 9Splay 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.
What you will see
An accessed node rotates upward until it becomes the root.
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.
How you work with it here
play it through, step one change at a time, scrub to any step, run it on your own input, try operations in any order.
Screen readers: Each element is an accessibility element with position, value and state; structural changes are announced per step.
Reduced motion: Elements appear at their destination with a crossfade; no travel longer than the element's own size.