Ok, ok, I know these are data structures and not algorithms but never-the-less, we will have a face off for tree supremacy. To see how these data structures match up, let’s go to the Tale of the Tape.
| Binary Search Tree | Tale of the Tape | Red-Black Tree |
|---|---|---|
| logn | Insert | logn |
| logn | Delete | logn |
| logn | Search | logn |
| n | Memory | n |
If you need a primer on our two combatants:
Binary Tree
Red-Black Tree
Wait a second, are these two trees the same? They are both Self Balancing Binary Search Trees and have the same stats. To find the difference, we are going to need to dive a bit deeper.
Insertion & Deletion
AVL Trees are (ever so slightly) better at balancing than Red-Black Trees. This comes at a cost due to the potential for more rotations during insertion and deletion. Advantage: Red-Black Tree
Search
Since AVL Trees are (ever so slightly) better at balancing, they have the potential for faster search. Advantage: AVL Tree
Memory
AVL Trees store a balance factor at each node taking up O(n) extra space. Red-Black Trees have a sign bit to store the color information at each node, taking up O(1) extra space. Advantage: Red-Black Tree
TL;DR use Red-Black Trees for situations that are heavy in Insertion and Deletion and AVL Trees for situations that are Search intensive.