Red-black tree over AVL tree

Question

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?

Cointon

possible duplicate of Why is std::map implemented as red-black tree? – Nogood

As an aside, the Rust developers chose to use a B-tree instead of either of these for their standard ordered map. – Sawicki

Answer 1

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

Rapture

In general, the rotations for an AVL tree are harder to implement and debug than that for a Red-Black tree. is not true. – Danyluk

To be pedantic, the C++ standard does not mandate that std:: map and friends use any particular structure. That's left to the implementation, although libstdc++ and Dinkumware at least uses red-black trees, and it seems like you're right in practice. – Automata

The balance factor stored in each node of an AVL tree is two bits (-1 / 0 / +1). A red-black tree stores one bit of color information in each node. Thus in total both trees require O(N) memory for the extra information. – Sausa

"For an insert intensive tasks, use a Red-Black tree." Why? AVL tree insertion only takes one rotation at worst, while Red Black tree can take two. – Cheyney

It is good to know that in Java 8, HashMap will use Red Black Tree if the linkedlist in a bucket is longer than 8. – Hawkes

This should be updated per Ben Pfaff's 2003 analysis of BST performance - AVL trees are more general purpose and perform better. Exact historical reasons for Java, C++ and the Linux kernel choosing the slower implementation would be interesting to track down. – Bloomington

@DavidMcManamon Are you referring to Performance Analysis of BSTs in System Software? The abstract says "The results indicate that when input is expected to be randomly ordered with occasional runs of sorted order, red-black trees are preferred; when insertions often occur in sorted order, AVL trees excel for later random access, whereas splay trees perform best for later sequential or clustered access". I have yet to read the rest of the paper. – Sawicki

@Cheyney There is a lot of FUD around the cost of balancing in AVL trees; the truth of the matter is that they are almost exactly the same, except AVL trees decide to rotate slightly more often. As a result, insert-intensive workloads where the order is well randomized may end up wasting work. Generally speaking, I'm pretty sure AVL trees are still better for most cases, especially since even in insertion-heavy workloads the rotations are useful when the items are already ordered -- and data is very often already ordered. – Abbess

Note that if you store a binary flag higher sibling with each node instead of higher child left/right/none/, the amount of balance information with an AVL node is exactly the same as with an RB one. It happens not to be how the original article described it, and you need to touch more nodes in case of updates. – Laconic

AFAIK, in detail, RB tree is 2lg(n + 1) height, and AVL tree is exactly lg(n) + 1/0 height. Insert Rotate: RB tree <= 2, AVL tree <= 1. So in theory, I think, AVL is faster. But in practice, RB tree is more common. – Laliberte

If you store pointers with alignment greater than 4 bytes you can use the 2 least significant bits for the balance factor of an AVL, just as you would do with the color of an RBT. – Prague

so java uses reb black tree for its TreeMap etc, but who uses AVL? is there any language or famous library that uses AVL? or is AVL just for theoretical knowledge? – Repugnance

Answer 2

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.

Tout

AFIAK, an AVL tree has also O(1) rotation per insertion. For RB-tree and AVL - one insertion may have 1 or 0 rotations. If rotation happens, the algorithms stop. If it doesn't happen, usually, algorithms continue to check/repaint nodes from bottom to the root of the tree. So, sometimes rotation O(1) can be better because it eliminates scanning remaining items O(log(n)). Because AVL tree, in average, makes more rotation, AVL tree is, usually, has better balance ~1.44 log(N) than RB-tree 2 log(N). – Lurie

Answer 3

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.

Bloomington

Funny! in my reading, the libavl article seems to say that AVL and RB are head-to-head, and neither is very clearly better than the other in general (which one is better depends on the workload). I don't see anywhere a claim that AVL is overall about 20% faster. – Cartier

Answer 4

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.

Adulterate

I believe, AVL tree insertion has the same/similar amortized cost but produces better balanced tree (1.44log(N) vs 2log(N)). In the same time, deletion in AVL tree may require more rotations. IMHO, this is addressed in WAVL en.wikipedia.org/wiki/WAVL_tree – Lurie

Answer 5

Deletion in RB trees only requires a maximum of three rotations. Source: Red-Black Trees :

"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."

Undersexed

Answer 6

They're both the most commonly used tree types but Red black trees have faster insertions because they have relaxed balancing apart from that they both have O(log N) search time something that's common between them. They are both equally good but AVL is usually more balanced because of it's 1.44 logN complexity over 2 logN complexity

Brodeur