Difference between red-black trees and AVL trees

data-structures tree language-agnostic avl-tree red-black-tree
Bob John picture Bob John · Apr 28, 2013 · Viewed 49.3k times · Source

Can someone please explain what the main differences between these two data structures are? I've been trying to find a source online that highlights the differences/similarities, but I haven't found anything too informative. In what cases would one be preferred over the other? What practical situations make one "better" to use than the other?

Answer

Fred Foo picture Fred Foo · Jul 24, 2013

AVL trees maintain a more rigid balance than red-black trees. The path from the root to the deepest leaf in an AVL tree is at most ~1.44 lg(n+2), while in red black trees it's at most ~2 lg (n+1).

As a result, lookup in an AVL tree is typically faster, but this comes at the cost of slower insertion and deletion due to more rotation operations. So use an AVL tree if you expect the number of lookups to dominate the number of updates to the tree.

Related questions

Hash table vs Balanced binary tree

What factors should I take into account when I need to choose between a hash table or a balanced binary tree in order to implement a set or an associative array?

Read More
Behavior Tree Implementations

I am looking for behavior tree implementations in any language, I would like to learn more about how they are implemented and used so can roll my own but I could only find one Owyl, unfortunately, it does not contain …

Read More
How to implement a tree data-structure in Java?

Is there any standard Java library class to represent a tree in Java? Specifically I need to represent the following: The sub-tree at any node can have an arbitrary number of children Each node (after the root) and it's children …

Read More