Binary search trees are efficient, ordered data structures that have various important applications in fundamental areas of computer science, including database indexing, string matching, and sorting; however, standard BSTs do not guarantee logarithmic behavior given an arbitrary set of insertions. Indeed, it is possible to end up with a linked list of nodes given certain sets of insertions/deletions. Various types of balanced BSTs guarantee logarithmic behavior for insertion/search/deletion (by keeping the height of the tree logarithmic in the number of nodes), but this comes with the cost of maintaining balance. Self-adjusting BSTs are similar in that they seek to restrict the behavior of the basic BST operations to logarithmic time, but their method of maintaining this behavior is different. They exploit the fact that in many cases, patterns of access are nonuniform: that is, some elements are more likely to be accessed than others. In this project, I implemented a recently proposed type of balanced BST, the WAVL tree, and a common type of self-adjusting BST, the splay tree. In doing this, I hoped to quantitatively measure the performance of these trees across a range of different tests, aiming to highlight the strengths and weaknesses of each of them.
WAVL (weak AVL trees) are a relaxed variant of an older rank-balanced BST, the AVL tree. Rank-balanced trees are trees in which every node has an integer rank that corresponds roughly to the height of the node (within c log h to be exact, where c is a constant and h is the height of the tree). Given these ranks, different rank rules can be defined to give different BSTs. In a WAVL tree, the rank difference between any two adjacent nodes can only be 1 or 2, where leaves always have rank 0, and leaves have two "dummy nodes" as children with rank -1. They use rotations as a constant-time restructuring primitive and guarantee that during insertion and deletion, at most two rotations will be performed. The rank rule together with the rebalancing algorithms guarantee an upper bound of 2 log n for the height of the tree.
Insertion into WAVL trees is done the same way as insertion in standard BSTs, but a series of rebalancing steps must be done from the newly inserted node, possibly up to the root. Deletion is also done as it is in standard BSTs, with a series of rebalancing steps up to the root. Searches are performed identically to searches in standard BSTs.
If you are interested in learning more about the inner-workings of WAVL trees, I found the wikipedia page to give a good overview and the paper in which WAVL were introduced to give detailed description and analysis.
Splay trees are self-balancing BSTs that use an operation called "splaying" as a restructuring heuristic. To splay a node, a series of rotations are performed to move the node to the root of the tree. At each step along this node's route to the top, the structure of the tree local to the node being splayed is used to determine what rotations to perform. Any time a node is inserted or accessed, it is splayed to the top of the tree, and any time a node is deleted, its parent is splayed to the top of the tree. The motivation for this type of behavior is to keep nodes that are more frequently accessed closer to the root of the tree in order to improve the amortized performance of the tree over a sequence of operations. This means that for a single access, it is possible to see linear behavior, but over a range of several accesses, the average behavior is shown to be logarithmic.
Splaying also has the interesting property that it roughly halves the depth of every node along the path from the node being splayed all the way to the root. This has the effect of keeping the tree more balanced than it would be if the nodes were simply swapped to the root.
Although I use a standard binary search tree as a baseline to which I compare my results, it is important to note that randomly-built BSTs have an upper bound of 3 log n on their expected height, which makes their behavior comparable to that of WAVL and splay trees. The proof is rather complicated (at least relative to proving the same upper bound on the expected depth of a given node in a randomly-built BST), but an overview of the analysis can be found here.
I implemented standard BSTs, splay trees, and WAVL trees in Python (the code can be found here). In designing the classes for each of the trees, I felt it was important to share as much code as possible between the three implementations to keep testing as consistent as possible. I implemented basic operations (insertion, deletion, searching, traversal, rotation) in the BST class and have the WAVL and Splay classes inherit from the BST class. This has the added benefit that the codebase is reduced/simplified, making debugging far easier.
In implementing the standard BST, I adapted the algorithms for deletion and rotation from CLRS edition 3 (referenced below). For WAVL insertion/deletion and splaying, I used the papers in which each of the trees was initially discussed (also referenced below) to implement the algorithms. I found it rather difficult to adapt much of what was written in informal English into code. There were certain points that I ran into bugs because the authors of the papers left something implicit that was not immediately obvious.
The test suite file consists of a few functions that generate different distributions of random data for insertion, deletion, and access. I generated data that were entirely randomly distributed, as well as data that were non-uniform. To judge the performance of each tree, I decided to rely on CPU time. It would be rather unfair to splay trees to use tree height (which was my original, naive idea) to judge performance since they are not designed to have logarithmic height. I decided that the best way to run tests was to compute the average behavior of each tree over repetitions of several sequences of tests. This way, splay trees (whose behavior we expect to excel when view from an amortized point of view) had a chance to compete with WAVL trees.
First, I loaded each tree with the same sequence of 10000 elements. Then, I ran each of the tests (described below) 10 times and computed averages for each of the tests.
The most unsurprising results were those for the uniform access test cases. Splay trees performed far worse than both WAVL and standard BSTs with an average time of 0.318 seconds, with standard BSTs clocking in at 0.0602 seconds and WAVL at 0.0460 seconds. This is exactly what I expected to happen: with random patterns of access, splay trees will be constantly changing shape randomly, and since about half of the splay operations will be logarithmic, this has a lot of overhead. The WAVL tree did end up performing better than the vanilla BST, but not by as much as I would have guessed. I suppose for the small (10000 to be exact) number of elements I loaded into the trees, the relative times are small, but over longer sequences of operations with more elements, this difference could potentially be sizable. It is also worth noting that in this test, I did not delete any nodes from the WAVL tree prior to running the tests, so the tree is actually an AVL tree (this is known to true since AVL insertion is exactly the same as WAVL insertion). Because AVL trees have stricter rank rules, it is likely that if deletions had been performed, WAVL trees would have performed slightly worse because the height would have been slightly higher.
The next test case I ran was to query the same four elements repeatedly. At first, I always queried the first four elements in the array that were loaded into the trees; however, in this case, the standard BST actually consistently outperformed WAVL trees. My best guess as to why this was happening is that there is something about insertion rebalancing in WAVL (and also AVL) trees that place the elements that are inserted first further away from the root, though I cannot see exactly why. After noticing this, I randomly chose four adjacent elements in the data array (as opposed to just the first four), and repeatedly queried the trees using these in the same order. This also produced an interesting result; splay trees did not perform better than the other two trees. The reason for this is that since a different number was being queried every time, splaying was occurring with every access, which increased the overhead of splay insertion. Finally, I decided to randomly choose four elements in the range from 0 to the max element in the tree, produce a long, random sequence of these four elements, and then query the three trees using this sequence. This showed the expected result: the splay tree beat out the other two trees at 0.0404 seconds, with the WAVL tree at 0.0515 seconds and the standard BST at 0.0786 seconds.
The next test case I ran was exactly the same as the previous one, but instead of querying four elements repeatedly, I queried ten. This produced the most unexpected result: the WAVL tree outperformed splay trees with a time of 0.0603 seconds, with the splay tree at 0.0732 seconds and the standard BST at 0.0737 seconds. This goes to show expensive splaying can be; if too many splays occur in a sequence of operations, it can ruin the performance of the tree.
The final test case I ran was to perform the same sequence of 1000 deletions on each of the trees. This test also surprised me: the WAVL tree outperformed the other trees at 0.0113 seconds, with the splay tree at 0.0131 seconds and the standard BST at 0.01306 seconds. I expected the splay and WAVL trees to perform much worse than the standard BST, since splaying and deletion rebalancing in WAVL are both logarithmic. I suppose the reason for the results as they are is that WAVL trees are more balanced, so the height of the tree is significantly less than that of the other two trees, giving a smaller hidden constant in the O(log n) upper bound on deletion.
I think the most interesting extension of this work would be to find out which probability distributions of the keys would optimize the performance of splay trees and then to run a sequence of tests to gauge how splay trees perform relative to other trees with these different probability distributions.