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 !

Variants of Binary Search

Introduction

Given a sorted array $A$ and a target value $k$ to search for, return a position $p$ in the array for which $A[p]=k$ or return $-1$ to signal that the element was not found. The folklore algorithm to solve this problem is binary search: you look at the middle element, compare it to $k$ and decide whether to terminate, search in the left half-array or search in the right half-array. This is pretty fast and it takes time $O(\lg N)$ where $N$ is the length of the array. In this post we will explore several ways to implement binary search.

Standard Binary Search

Let's start by giving the standard implementation. The recursive implementation is obvious so let's focus on iterative implementations instead.

Meta Binary Search

Meta binary search is a variant in which the position containing the target value is built one bit at a time, starting with the most significant bit.

To get a better idea of how this algorithm works, let's walk through an example. Imagine that the input array is $A=[1, 3, 5, 7, 11]$ and that we are looking for the value $k=7$. The last position of the array is $4$ and we need $2$ bits to store it. The first loop computes this value. Now we start at the most significant bit and we have two options: set it to $1$ or set it to $0$. We try both options and select the correct one. If setting the current bit to $1$ exceeds the length of the array then our only choice is to set it to $0$. In the other case we set the bit to $1$ and check if the value sitting in the position is strictly greater than $k$, in which case we set the bit to $0$ instead because our position never decreases in value (so by setting the current bit to $1$ we'll just be searching in parts of the array in which all values are strictly greater than the target value).

Like standard binary search, meta binary search takes $O(\lg N)$ time. The first loop computes the number of bits required to encode the largest position in the array and the second one iterates over these bits and builds up the answer.

This might be your first encounter with meta binary search but you might have used it in the past without paying attention. If you wrote code to answer lowest common ancestor (LCA) queries by using sparse tables then your LCA procedure is actually a form of meta binary search.

Binary Search over Real Numbers

How to write binary search when the search space is a monotonic real interval ? Many programmers use epsilons as a terminating condition. So you often see code that looks like:

This approach is error prone and might even time out. We'll describe a clean binary search over a real interval. Instead of storing the left and right end points of the interval as we did with the integers, we'll store the left end point and the size of the search space. We divide the size of the search space by 2 after each step and so the algorithm is guaranteed to terminate when the size reaches $0$.

Fractional Cascading

We will close this post with a useful technique that can be used to reduce the cost of searching for a target value $k$ in a list of $M \ge 1$ sorted arrays instead of just one. To simplify the discussion let's assume that all of the arrays have length $N$. An easy way to solve this problem is to binary search in each of the arrays; this takes time $O(M \lg N)$. Can we do better ? Yes !

We will preprocess the list of arrays so that search queries are fast. The idea is to cascade a fraction of the last list to the one right above it and add links from those cascaded elements to their locations in the list they came from. Now take this newly created list and cascade a fraction of its elements to the list on top of it, and so on. Now we perform one binary search in the first array and then follow the pointers to locate the values in the subsequent arrays. This technique is often used in geometric algorithms to reduce the cost of searching.