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.
-
Comparing Self-Balancing Search Trees
-
Collision Detection With Spatial Grid Partitioning
-
Keep Calm And Parse On: Error Handling for LR Parsers
-
From Finite Automata To A Lexical Analyzer
-
DFA Minimization: Moore's Algorithm
-
Parsing Regular Expressions with MGCPGen
-
Determinization: Converting εNFA to DFA
-
Implementing Lexical Scoping: Resolving Variable Names with De Bruijn Indices
-
Improving Balance of Ternary Search Tries
-
Making Sense of LALR Parser Construction
Leave A Comment