Red black tree over avl tree
AlgorithmData StructuresRed Black-TreeAlgorithm Problem Overview
AVL and Red black trees are both self-balancing except Red and black color in the nodes. What's the main reason for choosing Red black trees instead of AVL trees? What are the applications of Red black trees?
Algorithm Solutions
Solution 1 - Algorithm
> What's the main reason for choosing Red black trees instead of AVL trees?
Both red-black trees and AVL trees are the most commonly used balanced binary search trees and they support insertion, deletion and look-up in guaranteed O(logN) time
. However, there are following points of comparison between the two:
- AVL trees are more rigidly balanced and hence provide faster look-ups. Thus for a look-up intensive task use an AVL tree.
- For an insert intensive tasks, use a Red-Black tree.
- AVL trees store the balance factor at each node. This takes
O(N)
extra space. However, if we know that the keys that will be inserted in the tree will always be greater than zero, we can use the sign bit of the keys to store the colour information of a red-black tree. Thus, in such cases red-black tree takes no extra space.
>What are the application of Red black tree?
Red-black trees are more general purpose. They do relatively well on add, remove, and look-up but AVL trees have faster look-ups at the cost of slower add/remove. Red-black tree is used in the following:
- Java:
java.util.TreeMap
,java.util.TreeSet
- C++ STL (in most implementations): map, multimap, multiset
- Linux kernel: completely fair scheduler, linux/rbtree.h
Solution 2 - Algorithm
Try reading this article
It offers some good insights on differences, similarities, performance, etc.
Here's a quote from the article:
> RB-Trees are, as well as AVL trees, self-balancing. Both of them provide O(log n) lookup and insertion performance. > > The difference is that RB-Trees guarantee O(1) rotations per insert operation. That is what actually costs performance in real implementations. > > Simplified, RB-Trees gain this advantage from conceptually being 2-3 trees without carrying around the overhead of dynamic node structures. Physically RB-Trees are implemented as binary trees, the red/black-flags simulate 2-3 behaviour
As far as my own understanding goes, AVL trees and RB trees are not very far off in terms of performance. An RB tree is simply a variant of a B-tree and balancing is implemented differently than an AVL tree.
Solution 3 - Algorithm
Our understanding of the differences in performance has improved over the years and now the main reason to use red-black trees over AVL would be not having access to a good AVL implementation since they are slightly less common perhaps because they are not covered in CLRS.
Both trees are now considered forms of rank-balanced trees but red-black trees are consistently slower by about 20% in real world tests. Or even 30-40% slower when sequential data is inserted.
So people who have studied red-black trees but not AVL trees tend to choose red-black trees. The primary uses for red-black trees are detailed on the Wikipedia entry for them.
Solution 4 - Algorithm
Other answers here sum up the pros & cons of RB and AVL trees well, but I found this difference particularly interesting:
> AVL trees do not support constant amortized update cost [but red-black trees do]
Source: Mehlhorn & Sanders (2008) (section 7.4)
So, while both RB and AVL trees guarantee O(log(N)) worst-case time for lookup, insert and delete, restoring the AVL/RB property after inserting or deleting a node can be done in O(1) amortized time for red-black trees.
Solution 5 - Algorithm
Insertions in AVL trees and in RB trees both require a maximum of 2 rotations. From https://adtinfo.org/ :
> The primary advantage of red-black trees is that, in AVL trees, deleting one node from a tree containing n nodes may require log 2 n rotations, but deletion in a red-black tree never requires more than three rotations.