Difference between red-black trees and AVL trees

问题:

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?

回答1:

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.

回答2:

For small data:

insert: RB tree & avl tree has constant number of max rotation but RB tree will be faster because on average RB tree use less rotation.

lookup: AVL tree is faster, because AVL tree has less depth.

delete: RB tree has constant number of max rotation but AVL tree can have O(log N) times of rotation as worst. and on average RB tree also has less number of rotation thus RB tree is faster.

for large data:

insert: AVL tree is faster. because you need to lookup for a particular node before insertion. as you have more data the time difference on looking up the particular node grows proportional to O(log N). but AVL tree & RB tree still only need constant number of rotation at the worst case. Thus the bottle neck will become the time you lookup for that particular node.

lookup: AVL tree is faster. (same as in small data case)

delete: AVL tree is faster on average, but in worst case RB tree is faster. because you also need to lookup for a very deep node to swap before removal (similar to the reason of insertion). on average both trees has constant number of rotation. but RB tree has a constant upper bound for rotation.

回答3:

Quoting from this: Difference between AVL and Red-Black Trees

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.

by definition, every AVL is therefore subsets of Red-Black. One should be able to color any AVL tree, without restructuring or rotation, to transform it into a Red-Black tree.

回答4:

AVL trees are often compared with red-black trees because both support the same set of operations and take O(log n) time for the basic operations. For lookup-intensive applications, AVL trees are faster than red-black trees because they are more rigidly balanced. Similar to red-black trees, AVL trees are height-balanced. Both are in general not weight-balanced nor μ-balanced for any μ ≤ ½; that is, sibling nodes can have hugely differing numbers of descendants.

From the Wikipedia Article on AVL Trees

回答5:

The max height of the trees is the paramount important to keep balance. It almost equals 1.44 * log(n) for AVL, but for RB tree, it is 2 * log(n). So we can get the conclusion that it is better to use the AVL when the problem is search incentive. What matters is another question for AVL and RB tree. RB tree is better than AVL when facing the random insertion at the lower cost of the rotation but the AVL that is good to insert the ascending or descending datas. So if the problem is insertion incentive, we can use RB tree.

回答6:

The fact that RedBlack trees have less rotations can make them faster on inserts/deletes, however .... . Since they are usually a bit deeper They can also be slower on inserts and deletes. Every time you go from one level in the tree to the next, there is a big change that the information requested is not in the cache and must be retrieved from RAM. Thus the time gained on less rotations can already be lost since it has to navigate deeper and thus have to update its cache more often. Being able to operate from cache or not makes a big difference. If the relevant information is in cache, then you can do multiple rotations operations, in the time needed to navigate an additional level and the next level information is not in cache. Thus in cases that RedBlack is in theory faster, looking only at the operations needed, it could be slower in practice, due to cache misses.

回答7:

From what I have seen it seems that AVL Trees do as many rotations(recursively up the tree sometimes) as needed to get the desired height of the AVL Tree (Log n). This makes it more rigidly balanced.

For Red Black Trees there are 5 Sets of rules you need to make sure stay through insertion and removal which you can find here http://en.wikipedia.org/wiki/Red-black_tree.

The main thing that might help you for red black trees is the fact that depending on those five rules you can recursively color the tree up to the root if the uncle is red. If the uncle is black you going to need to do maximum two rotations to fix whatever issues you have but after those one or two rotations YOU'RE DONE. Pack it in and say goodnight because that's the end of the manipulation you need to do.

The Big rule is number 5... 'Every simple path from a given node to any of its descendant leaves contains the same number of black nodes'.

This will cause most of the rotations youll need to make the tree work and that causes the tree not to go too far out of balance.

回答8:

In summary: AvlTrees are slightly better balanced than RedBlackTrees. Both trees take O(log n) time overall for lookups, insertions, and deletions, but for insertion and deletion the former requires O(log n) rotations, while the latter takes only O(1) rotations.

Since rotations mean writing to memory, and writing to memory is expensive, RedBlackTrees are in practice faster to update than AvlTrees

回答9:

To get an idea of how an AVL Tree works, this interactive visualization helps.

AVL as well as RedBlack Trees are height-balanced Tree Data Structures. They are pretty similar, and the real difference consists in the number of rotation operation done upon any add/remove operation - higher in the case of AVL, to preserve an overall more homogeneous balancing.

Both implementations scale as a O(lg N), where N is the number of leaves, but in practice a AVL Tree is faster on lookup intensive tasks: taking advantage of the better balancing, the Tree traversals are shorter on average. On the other hand, insertion and deletion wise, an AVL Tree is slower: a higher number of rotations are needed to rebalance properly the Data Structure upon modification.

For general purpose implementations (i.e. a-priori it is not clear if lookups are the predominant of operations), RedBlack Trees are preferred: they are easier to implement, and faster on the common cases - wherever the Data Structure is modified as frequently as searched. An example, TreeMap and TreeSet in Java make use of a backing RedBlack Tree.