COMP1927 - Splay Trees

Splay Trees are self-balancing, amortised (O(lg(n))) trees. Recently accessed (inserted, queried, or deleted) nodes are kept near the root.

The worst case with a Splay Tree is where the items are accessed sequentially. Using random insertions can fix this.

Insertion

Splay Trees insert nodes as leaf nodes, and then perform double rotations (i.e. rotating the grandparent twice) until the node is root.

Deletion

Deletions in Splay Trees consist of splaying (i.e. double-rotating) the node to the root of the tree, and then rotating its now-left-child (was its parent) until the root->left has no children. Delete the node by replacing it with it's old-left-child.

This leaves the left-child as the root, the parent as the left-child, and the grandparent as the right-child.

Overall

Splay Trees have an average amortised cost of O(lg(n)), but any particular operation might still be O(n).