Comparing Self-Balancing Search Trees

When it comes to choosing a self balancing binary search tree, the common wisdom is to use which ever you already have a debugged working implementation of. That is pretty good advice, and most programming languages these days come with one in the standard library. The problem with this approach is that standard libraries, and general purpose libraries tend to implement what will work best in most situations, not necessarily your situation. Sometimes we have several good options and simply want to know which one is best for the scenario at hand.

In todays post I'm going to compare three different Red/Black tree implementations, one AVL tree, and an in-memory B+ tree to see how they perform in comparison to each other with regards to insertion, deletion, and search performance on data sets of varying size and compositions.

The Trees

We will be comparing 3 types of red black trees, 2 of my own implementation and one being std::set. In addition we will also be subjecting AVL trees and In-memory B+ Trees to the same battery of tests.

- Iterative 2-3-4 Red/Black Tree with Top Down Insertion and Deltion, no parent pointers.

- Recursive 2-3-4 Red/Black Tree with Bottom up Insertion and Top-Down Deletion, no parent pointers

- std::set, an Iterative 2-3-4 Red/Black Tree using the CLRS bottom-up re-balancing and parent pointers.

- Recursive Bottom-up AVL Tree, no parent pointers.

- Recursive B+ Tree with a node size of 128. bottom up splitting on insertion and merging on deletion. 

 

Insertion

When it comes to insertion the red/black tree's outperform both the AVL tree and the B+ tree quite handily. The larger the input size gets, the worse the B+ tree performs in comparison to the others, a trait it shares with the AVL tree. It is here that we also start to get an inclination that not all red/black tree's are created equal. 

tree size  TD Red/Black  Rec. Red/Black  AVL Tree  B+ Tree  std::set
5000 1.01914 1.24572 1.85107 1.56446 1.04726
10000 1.2222 2.22877 4.71991 4.75535 2.37551
20000 4.82464 7.65541 17.3609 18.985 5.27756
40000 6.51627 14.1519 21.9774 26.3956 9.83322
80000 14.1725 31.1491 48.4518 56.0826 23.8249
160000 32.8826 65.5426 120.947 124.349 64.1564
320000 91.0177 134.979 241.028 328.801 210.755

The top down iterative version is more than 2x faster to insert the same data set once the N is above 20k. The recursive bottom up and iterative bottom up implementations trade places in being faster than the other, though they are about equal until N grows larger where the recursive implementation eeks it's way ahead. Neither bottom up implementation even approaches the top down red/black tree for insertion.

Deletion

As Was seen with insertion, the AVL tree and B+ tree are among the worst performing of the trees. Quite unexpectedly however the recursive top-down red/black deletion is the slowest! This is also surprising because the iterative top-down red/black tree is among the fastest!

tree size  TD Red/Black  Rec. Red/Black  AVL Tree  B+ Tree  std::set
5000 1.22311 2.25849 2.63901 2.24432 1.50801
10000 3.21832 5.79406 4.01614 3.94771 5.68597
20000 6.9749 12.4602 9.13388 10.3731 6.0718
40000 14.7501 26.6432 20.0036 21.8127 11.9279
80000 29.9678 63.7851 43.3052 51.4703 25.4568
160000 71.556 135.941 106.106 119.473 61.6562
320000 186.641 338.369 271.806 310.629 146.331

The bottom up red/black tree is just slightly faster than the iterative top down implementation, with them taking the 1st and 2nd spot respectively for all sizes of n. This is because the top-down tree performs rotations that may be unenecessary, which the bottom up tree can safely skip.

 


Leave A Comment