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?

Solution 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

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

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

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

View more solutions

Comments

[Lior Kogan]

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

[Tom Anderson]

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

[Jingguo Yao]

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

[smiling_nameless]

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.

[Seppo Enarvi]

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.

[Daniel]

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

[Sergey Shandar]

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

[Sergey Shandar]

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

[Ev3rlasting]

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.

[David McManamon]

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.

[Stefan]

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.

[Tom Anderson]

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

[Mumbleskates]

@Daniel 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.

[greybeard]

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.

[大宝剑]

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.

[Oppen]

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.

[theprogrammer]

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?