Splay-Tree Operations at a High-Level (Optional)
We won't cover splay trees in detail in CS 70. We don't expect you to be able to perform splay-tree operations by hand or anything like that.
However, if you want a slightly better idea of how they work, you'll find some additional details on this page!
-
For every insert/lookup, the inserted/found node is rotated to the top.
When something is inserted/found in a tall branch, the branch is pulled upward so it won't be as long next time! An expensive operation enables cheap operations afterwards.
-
Splay trees use a special version of insert-and-move-to-root.
When a node is being rotated upwards, most of the operations are the same as insert-and-move-to-root. The one exception is when the node is the left child of a left child or a right child of a right child. In those cases, we perform a special double rotation to bring the node up two spots.
Double rotation turns out to be critical for the amortized complexity guarantee of splay trees. The splay operation ensures that really long branches get shorter very quickly.
In particular, if you insert at the bottom of a stick, then these two-at-a-time rotations will occur all the way up, fully halving the height of the tree. If we did regular insert-and-move-to-root operations on a stick, we would just end up with a different stick!
If you want to play around with the splay operation for yourself, check out the
(When logged in, completion status appears here.)