Algorithm Fight Club: AVL Binary Search Tree vs Red-Black Tree

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.

Leave a Reply

Your email address will not be published. Required fields are marked *