A splay tree is an efficient implementation of binary search trees that takes advantage of locality in the incoming lookup requests. Locality in this context is a tendency to look for the same element multiple times. A stream of requests exhibits no locality if every element is equally likely to be accessed at each point. For many applications, there is locality, and elements tend to be accessed repeatedly. A good example of an application with this property is a network router. Routers must decide on which outgoing wire to route the incoming packets, based on the IP address in the packets. The router needs a big table (a map) that can be used to look up an IP address and find out which outgoing connection to use. If an IP address has been used once, it is likely to be used again, perhaps many times. Splay trees are designed to provide good performance in this situation.
In addition, splay trees offer amortized O(lg n) performance. That is, a sequence of M operations on an n-node splay tree takes O(M lg n) time.
A splay tree is a binary search tree. It has one interesting difference, however: every operation on the tree causes the splay tree to reorganize itself, moving the target element to the root of the tree, without breaking the binary search tree invariant. If the next operation is for the same element, it can be retrieved immediately. In general, if a small number of elements are being heavily used, they will tend to be found near the top of the tree and are thus found quickly.
We have already seen a way to move an element upward in a binary search tree: tree rotation. When an element is accessed in a splay tree, tree rotations are used to move it to the top of the tree. Notice that the algorithm requires that we be able to update the tree in place, but the abstract view of the set of elements represented by the tree does not change and the rep invariant is maintained. This is an example of a benevolent side effect: a side effect that does not change the abstract view of the value represented.
To make the operations efficiently, whenever possible, rotations are done in pairs. This results in extremely good performance in practice. There are three kinds of tree rotations that are used to move elements upward in the tree. These rotations have two important effects: they move the node being splayed upward in the tree, and they also shorten the path to any nodes along the path to the splayed node. This latter effect means that splaying operations tend to make the tree more balanced.
The simple tree rotation used in AVL trees is also applied at the root of the splay tree, moving the splayed node x up to become the new tree root. Here we have A < x < B < y < C, and the splayed node is either x or y depending on which direction the rotation is. It is highlighted in red.
y x
/ \ / \
x C <-> A y
/ \ / \
A B B C
Lower down in the tree rotations are performed in pairs so that nodes on the path from the splayed node to the root move closer to the root on average. In the "zig-zig" case, the splayed node is the left child of a left child or the right child of a right child ("zag-zag").
z x
/ \ / \
y D A y
/ \ <-> / \ (A < x < B < y < C < z < D)
x C B z
/ \ / \
A B C D
In the "zig-zag" case, the splayed node is the left child of a right child or vice-versa. The rotations produce a subtree whose height is less than that of the original tree. Thus, this rotation improves the balance of the tree. In each of the two cases shown, y is the splayed node:
z x y
/ \ / \ / \
y D / \ A z (A < y < B < x < z < D)
/ \ -> y z <- / \
A x / \ / \ x D
/ \ A B C D / \
B C B C
See this page for a nice visualization of splay tree rotations and a demonstration that these rotations tend to make the tree more balanced while also moving frequently accessed elements to the top of the tree.
We present the SML code for Splay trees bellow. The key function is splay, which takes a non-leaf node and a key k to look for, and returns a node that is the new top of the tree. The element whose key is k, if it was present in the tree, is the value of the returned node. If it was not present in the tree, a nearby value is in the node.
functor SplayTree(structure Params : ORDERED_SET_PARAMS)
:> ORDERED_FUNCTIONAL_SET where type key = Params.key and
type elem = Params.elem =
struct
type key = Params.key
type elem = Params.elem
val compare = Params.compare
val keyOf = Params.keyOf
datatype tree =
Empty
| Node of tree * elem * tree
type node = tree * elem * tree
(* Representation invariant:
* All values in the left subtree are less than "value", and
* all values in the right subtree are greater than "value".
*)
type set = int * (tree ref)
(* Representation invariant: size is the number of elements in
* the referenced tree. *)
fun empty() = (0, ref Empty)
(* splay(n,k) is a BST node n' where n' contains all the
* elements that n does, and if an element keyed by k is in under n',
* #value n is that element.
* Requires: n satisfies the BST invariant.
*)
fun splay((L, V, R), k: key): node =
case compare(k, keyOf(V))
of EQUAL => (L, V, R)
| LESS =>
(case L
of Empty => (L, V, R) (* not found *)
| Node (LL, LV, LR) =>
case compare(k, keyOf(LV))
of EQUAL => (LL, LV, Node(LR, V, R)) (* 1: zig *)
| LESS =>
(case LL
of Empty => (LL, LV, Node(LR, V, R)) (* not found *)
| Node n => (* 2: zig-zig *)
let val (LLL, LLV, LLR) = splay(n,k) in
(LLL,LLV,Node(LLR,LV,Node(LR,V,R)))
end)
| GREATER =>
(case LR
of Empty => (LL, LV, Node(LR, V, R))
| Node n => (* 3: zig-zag *)
let val (RLL, RLV, RLR) = splay(n,k) in
(Node(LL,LV,RLL),RLV,Node(RLR,V,R))
end))
| GREATER =>
(case R
of Empty => (L, V, R) (* not found *)
| Node (RL, RV, RR) =>
case compare(k, keyOf(RV))
of EQUAL => (Node(L,V,RL),RV,RR) (* 1: zag *)
| GREATER =>
(case RR
of Empty => (Node(L,V,RL),RV,RR) (* not found *)
| Node n => (* 3: zag-zag *)
let val (RRL, RRV, RRR) = splay(n,k) in
(Node(Node(L,V,RL),RV,RRL),RRV,RRR)
end)
| LESS =>
(case RL
of Empty => (Node(L,V,RL),RV,RR) (* not found *)
| Node n => (* 2: zag-zig *)
let val (LRL, LRV, LRR) = splay(n,k) in
(Node(L,V,LRL),LRV,Node(LRR,RV,RR))
end))
fun lookup((size,tr),k) =
case !tr of
Empty => NONE
| Node n =>
let val n' as (L,V,R) = splay(n,k) in
tr := Node n';
if compare(k, keyOf(V)) = EQUAL then SOME(V)
else NONE
end
fun add((size,tr):set, e:elem) = let
val (t', b) = add_tree(!tr, e)
val t'': node = splay(t', keyOf(e))
val size' = if b then size else size+1
in
((size', ref (Node(t''))),b)
end
and add_tree(t: tree, e: elem): node * bool =
case t
of Empty => ((Empty, e, Empty), false)
| Node (L,V,R) =>
(case compare (keyOf(V),keyOf(e))
of EQUAL => ((L,e,R),true)
| GREATER => let val (n',b) = add_tree(L, e) in
((Node(n'),V,R),b)
end
| LESS => let val (n',b) = add_tree(R, e) in
((L,V,Node(n')),b)
end)
...
end
To show that splay trees deliver the promised amortized performance, we will use the banker's method, similar to the one used in our analysis of dynamic resizable arrays in class.
In this scenario, each node of the tree has a savings account containing a certain amount of money. When a node x is created, we overcharge the add operation that creates x, and deposit the extra credits to x's account. These credits will be used later to pay for restructuring operations on the tree.
Let S(x) be the subtree rooted at node x (including x) and |S(x)| the number of nodes in tree S(x). Define:
μ(x) = floor(log |S(x)|)
where floor(n) returns the smallest integer greater than n. We maintain the following credit invariant:
Node x always has at least μ(x) credits on deposit.
Notice that each operation can be performed using a constant number of splay operations plus a constant number of comparisons and pointer manipulations. The extra amount needed to be charged from the add operation and then deposited in x's account is at most μ(r) = log(floor(n)), where r is the root node of the tree, and n is the total number of elements in that tree. This overcharge does not increase the complexity of add more than O(log n). However, we know that some individual operations may take more than O(log n) time.
If we could withdraw some credits from our savings to reduce the cost of each
splay operation to O(log n) time, it would immediatelly follow that the
total amortized time required for a sequence of M operations is O(M log n). But we do not know how many credits
we need to spend in order to perform each splay operation and, at the same
time, to maintain the credit invariant. It turns out that one
can prove that we need to spend no more than 3(μ(r)
- μ(x)) + 1 credits, where r is the root of
the tree. Let us demonstrate this in each of the three splay scenarios:
Only nodes x, y, and z change in size. Thus, the cost to maintain the invariant is:
μ'(x) + μ'(y) + μ'(z) − μ(x) − μ(y) − μ(z)
Since the μ'(x) is the same as μ(z), this is equal to
= μ'(y) + μ'(z) − μ(x) - μ(y)
= (μ'(y) − μ(x)) + (μ'(z) - μ(y))
Note that μ'(x) is greater than μ'(z) and μ'(y), and μ(x) is less than μ(y), so this is at most
= (μ'(x) − μ(x)) + (μ'(x) - μ(x))
= 2(μ'(x) - μ(x))
We can afford to pay for this operation and still have μ'(x) − μ(x) + 1 credits left over to pay for the constant number of low-level operations needed to perform these two rotations.
Unfortunaltely, this may not always be the case: it may turn out that μ'(x) = μ(x), in which case we have nothing left over. It can be shown that in this case the cost of the operation is strictly negative. What is needed to be shown is that, if μ'(x) = μ(x), then
μ'(x) + μ'(y) + μ'(z) >= μ(x) + μ(y) + μ(z)
leads to a contradition. This proof is left to the reader as an exercise.
Therefore, if μ'(x) = μ(x), the invariant is maintained for free, and we can afford to spend our saved credits to pay for the low-level operations.
Again, the amortized time is
μ'(x) + μ'(y) + μ'(z) −μ(x) − μ(y) − μ(z)This case is similar to the previous one, and this completes our proof.