Picking up where I left off a couple of weeks back, I’m continuing the binary tree family refresher course with Splay Trees.

I Google’d a couple of “java” and “splay” term permutations, but I did not find any obvious traces of splays being used anywhere in the JDK. It would be nice to get something other than AVL-based TreeMaps in the JDK.

A splay tree is a self-balancing binary search tree with the additional unusual property that recently accessed elements are quick to access again. It performs basic operations such as insertion, look-up and removal in O(log(n)) amortized time.

Good performance for a splay tree depends on the fact that it is self-balancing, and indeed self optimising, in that frequently accessed nodes will move nearer to the root where they can be accessed more quickly. This is an advantage for nearly all practical applications, and is particularly useful for implementing caches; however it is important to note that for uniform access, a splay tree’s performance will be considerably (although not asymptotically) worse than a somewhat balanced simple binary search tree.

Reference to “amortized time” in the definition above triggered another Wikipedia page lookup…

In analysis of algorithms, amortized analysis refers to finding the average running time per operation over a worst-case sequence of operations. Amortized analysis differs from average-case performance in that probability is not involved; amortized analysis guarantees the time per operation over worst-case performance.

The method requires knowledge of which series of operations are possible. This is most commonly the case with data structures, which have state that persists between operations. The basic idea is that a worst case operation can alter the state in such a way that the worst case cannot occur again for a long time, thus “amortizing” its cost.