Splay Trees

Splay tree is a balanced binary search tree.

Splay tree is not perferctly balanced. Worst case time can be O(n) for one single operation. But average running time is O(n lg n)

Tree Rotation

Operations

Find

Find min key

Find Max key

Insert

Remove