Splay tree is a data structure, structurally identitical to a Balanced Binary Search Tree. Every operation performed on a Splay Tree causes a readjustment in order to provide fast access to recently operated values. On every access, the tree is rearranged and the node accessed is moved to the root of the tree using a set of specific rotations, which together are referred to as Splaying.
Given a node a if a is not the root, and a has a child b, and both a and b are left children or right children, a Zig-Zig is performed.
Given a node a if a is not the root, and a has a child b, and b is the left child of a being the right child (or the opporsite), a Zig-Zag is performed.
A Zig is performed when the node a to be rotated has the root as parent.
Splay trees provide an efficient way to quickly access elements that are frequently requested. This characteristic makes then a good choice to implement, for exmaple, caches or garbage collection algorithms, or in any other problem involving frequent access to a certain numbers of elements from a data set.
Splay tree are not perfectly balanced always, so in case of accessing all the elements in the tree in an increasing order, the height of the tree becomes n.
| Case | Performance |
|---|---|
| Average | O(log n) |
| Worst | n |
With n being the number of items in the tree.
Splay Tree on Wikipedia Splay Tree by University of California in Berkeley - CS 61B Lecture 34
Written for Swift Algorithm Club by Barbara Martina Rodeker