Splay Tree
Basic Rotation
Simple Exchange (Transpose)
 When we access a node, apply a rotation to move the node one level
closer to root

 If each node is accessed with probability of 1/n the average search time
is:
Movetoroot example
Splaying
Splay step at x
let p(x) = parent of
node x
case 1 (zig) p(x) = root of the tree
case
2 (zigzig) p(x) is not the root and x and p(x) are both left (right)
children
case 3
(zigzag) p(x) is not the root and x is a left (right) child and p(x) is a
right(left ) child
To Splay a
node X, repeat the splay step on X until it is the root
Splay B
Splay vs. Movetoroot
Case 1
Case
2
Splay vs. Movetoroot
Case 3
Movetoroot A
Splay A
Example Splay at B
Example Splay at B