Splay Trees
A splay tree is a type of binary-search tree that does well when there is high temporal locality.
In other words, it makes it easy to find keys that have recently been inserted or recently been found.
Let's take a look at how it does that!
Playing with Splay Trees
Here's a really neat tool for visualizing splay tree operations:
Go to that site and insert these keys:
- 20
- 80
- 40
- 60
- 30
’Strewth! It moved newly inserted keys to the root!
-
That's right! So recently inserted keys are now the easiest to find.
When a splay tree inserts a new node, it performs a series of rotations to bring that new node to the root. This procedure is called the splay operation.
It is also the case that if there is a key already in our tree and someone looks it up, we expect that it will be looked up again soon.
So, we also want to make recently found keys easy to find again.
In the same tree that you were working on in the visualizer, find 40.
-
I'll be stuffed! It changed the tree on lookup!
-
That's right! We haven't seen that in a BST before.
Splay trees rearrange nodes on both insert and lookup.
Splay Trees: Big Idea
The big idea behind a splay tree is that whenever a node is inserted or is successfully found during a lookup, the splay operation moves that node to the root.
This behavior allows splay trees to take advantage of temporal locality: looking up recently inserted or recently found keys will take near best-case time!
In CS 70, you won't be implementing a splay tree and we won't require you to understand the splay operation in detail.
Just to be clear, it's not that you can't understand the splay operation.
-
We'll give you some (optional) explanation in the next lesson.
-
For now, we just want to focus on understanding the strengths and weaknesses of splay trees.
(When logged in, completion status appears here.)