Splay Trees

The standard way to achieve worst case logarithmic performance per operation in a binary search tree is by imposing a balance condition on the nodes. AVL trees, for example, force logarithmic height by making each node store its height in addition to its left/right/parent pointers. The balance condition is invariant and a rebalancing operation is necessary to restore the invariant whenever it is violated.

There is another way to obtain logarithmic performance but in an amortized sense. We do not need to impose a balance condition. Rather, the tree adjusts itself after each operation by using a restructuring heuristic. Sleator and Tarjan proposed a heuristic that achieves O(lg n) time amortized per operation (over a sequence of operations). This heuristic is the splay operation. In the remainder of this post, we shall describe how the splay operation works and provide a C/C++ implementation.

We are going to use a C++ structure to represent a node. A node stores pointers to its left/right children and to its parent. Initially, all pointers point to nothing.

In a splay tree, a node x is splayed to the root of the tree whenever it is accessed. Splaying x works by climbing the x-to-root path by following parent pointers and performing rotations. A rotation is a local restructuring operation. If x is a left child, it is rotated to the right and if it is a right child, it is rotated to the left. The following is a pictorial representation of a rotation. Here x and y are nodes and A, B and C are sub-trees (possibly null).

Rotations do not change the binary search property, i.e., inorder traversals of the tree before and after the rotation give the same output. The following function performs a right rotation.

Here is code to perform a left rotation.

The splay operation performs rotations in pairs. There are two cases to consider, a zig-zig case and a zig-zag case. Let x be the node that we want to splay and let y be its parent. The zig-zig case occurs when both x and y are left children (or both right children). The zig-zag case occurs when x is a left child and y is a right child (or x is a right child and y is a left child). If y is neither a left nor a right child (it is the root), we do a single rotation. Let us elaborate.

The following figure shows the pair of rotations performed in the zig-zig step. Here x is a left child and y is a left child (the right-right case is symmetric). The order of rotations is important, we first rotate y and then we rotate x.

The following figure shows the pair of rotations performed in the zig-zag step. Here x is a right child and y is a left child (the left-right case is symmetric). We rotate x twice

To wrap, there are two cases up to symmetry and four cases in general, and we might do one last rotation at the end if x does not have a grand-parent.

By the end of the splay operation, x becomes the root of the tree. This is very useful because nodes that are accessed frequently live near the root of the tree as a result of splay.

Now you can augment nodes with keys and use the splay operation to implement the other operations. For example, to insert a node with key k, you do a regular binary search on k to find where to insert the node, and then you splay that node to the root of the tree.

That is all for this post. Thank you for reading !

Maintaining Disjoint Sets under Union

Time for a new post. This time, we will cover an elegant data structure for maintaining a class of sets under the operation of union. Formally, we start with $n$ classes each consisting of a single element: $\{1\}, \{2\}, \dots, \{n\}$. These correspond to the equivalent classes of some equivalent relation. We would like to be able to quickly find which class an element belongs to and quickly join two classes together to form one class (destroying the old classes along the way). These two operations are known as find and union and the data structure is often times called union-find.

There are many ways to implement these operations but we will cut to the chase and implement find with path compression and union by rank.

Representation of a Class

We are going to use a tree to represent an equivalent class. Each node in the tree corresponds to an element in the class. Each node also points to its parent in the tree. The root of the tree points back to itself. The root of the tree also serves as the representative element of the class. The root node will also maintain the number of nodes in its tree (we will see why this is useful when we talk about union by rank). Initially, every element lives in a separate class, so the trees will look like this for $n=5$ (the size of the trees is dropped here).

Initial setting

Find with Path Compression

Given an element, we would like to find the class it belongs to (or the representative of that class since each class has a unique representative). Using the representation above, we just climb to the root by following parent pointers and return the root element. The path to the root could be long and so making several calls to find with the same argument could end up taking a lot of time. Path compression avoids this by making the nodes along the path (except for the root itself) point to the root. This renders subsequent calls to find very cheap in terms of running time. Here is a pictorial representation of path compression. The right tree is the new state we get after a call to $find(4)$. The path to the root is highlighted in red.

Find with path compression

Union by Rank

The union operation takes two disjoint classes as input and creates a new class that is the union of the elements in the input classes. An easy way to implement this is to take one of the root elements and make it a child of the other root element. The union by rank heuristic suggests that it is a good idea to make the root of the class with the smaller number of elements a child of the root of the class with the larger number of elements. In the following figure, the class $\{1,2\}$ is joined with the class $\{3,4,5\}$ by making $1$ a child of $3$.

Union by rank

Implementation

For each node we need to know its parent node and the size of its subtree. We will use one array, $uf$ (for union-find), of integers to account for both pieces of data. $uf[x]$ gives the parent of a node when $x$ is not a root and it gives the size of the subtree when $x$ is a root. How do we differentiate between the two ? We simply negate the size when the element is a root. So if $uf[x]$ is negative we can say that $x$ is a root element and that $-uf[x]$ is the size of the tree rooted at $x$ and when $uf[x]$ is non-negative we can say that $x$ is a non-root element and that it is a child of $uf[x]$.

Initially, every element lives in its own tree and so is the root of that tree. We can write a function to initialize the array as follows:

The union operation is very easy to implement. First we find the root elements and then make the one with the smaller size a child of the one with the larger size.

The find operation is slightly harder to implement. We find the root element in a first pass and then make the nodes along the path children of the root in a second pass.

That is all for this post. I hope that it was helpful. As always, feedback and questions are welcome.