Splay Tree

Self-Organizing BST

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:

Move-to-root example

Splay Trees

Splaying

Splay step at x

let p(x) = parent of node x

case 1 (zig) p(x) = root of the tree



case 2 (zig-zig) p(x) is not the root and x and p(x) are both left (right) children
case 3 (zig-zag) 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. Move-to-root

Case 1

Case 2
Splay vs. Move-to-root

Case 3

Move-to-root A
Splay A
Example Splay at B
Example Splay at B