Splay tree

The splay tree is type of self-adjusting binary search tree like the red-black tree. What makes the splay tree special is its ability to access recently accessed elements faster. Whenever an operation is performed, the tree performs an operation called splaying which pulls the element to the top of the tree.

The worst case height of a splay tree is \(n\), this could be the case if all nodes were accessed in ascending order for example.

This makes the worst case complexity of the splay tree's operations \(O(n)\). Since all operations also splay the tree on the node, the tree ends up roughly balancing itself, this results in a \(O(\log n)\) amortized worst case time complexity for all operations.

The splay tree is a particularly good choice as a data structure when it's likely that the same nodes will be accessed multiple times in a short period. This is where the real power in the splay tree lies, in its ability to hoist nodes up to the root when they are accessed, giving speedy access for nearby successive accesses.

Data structure: Red-black tree

The red-black tree is a type of self-balancing binary search tree that assigns a colour of red or black to each node. On every insert or delete, the tree re-organises itself so that it is approximately \(\log n\) nodes high, allowing search in \(O(\log n)\) time. The re-organising does not guarantee a perfectly balanced tree, it is however good enough to guarantee \(O(\log n)\) search.

Insert and delete are also performed in \(O(\log n)\) time. The 'fixup' operations where the balancing occurs after insert and delete have quite complex implementations as you will see below. This is because we need the properties of the red-black tree to hold otherwise it may not be balanced.

Binary search tree

A binary search tree (BST) is a node-based tree data structure in which each node can have at most two children, it supports several operations common to any search tree such as search, insert and delete. Operations on a BST always start at the root node and work their way down, because of this they take time based on how high the tree is. For example a tree with n nodes where there are no right children will take \(O(n)\) time, a complete BST however (every level except the last is completely filled, with nodes on the last as left as possible) has the worst case time of \(O(\log n)\).