Basic Idea

We allow the tree to become unbalanced.

The downside is that we might need to spend a lot of time finding a node that is deeper than it ought to be.

To make up for this, whenever we find a node, we move it up to the top!

Demonstrate rotation.


next up previous
Next: Splaying a Node Up: SPLAY TREES Previous: Review