在avl树上的红色黑色树 [英] Red black tree over avl tree
问题描述
AVL和红黑树都是自平衡的，除了节点中的红色和黑色之外。选择红黑树代替AVL树的主要原因是什么？红黑树的应用是什么？
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?
推荐答案
选择红黑树的主要原因是什么而不是AVL树？
What's the main reason for choosing Red black trees instead of AVL trees?
红黑树和AVL树都是最常用的平衡二叉搜索树，它们支持插入，保留 O（logN）时间中的删除和查找。然而，两者之间有以下几点比较：
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树更加平衡，从而提供更快的查找。因此，对于查找密集型任务，请使用AVL树。
- 对于插入密集型任务，请使用红黑树。
- AVL树存储每个节点的平衡因子。这需要
O（N）个额外空间。但是，如果我们知道将插入到树中的键将始终大于零，我们可以使用键的符号位来存储红黑树的颜色信息。因此，在这种情况下，红黑树采取O（1）额外空间。 - 通常，AVL树的旋转比Red-Black树更容易实现和调试。
- 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 takesO(1) extra space. - In general, the rotations for an AVL tree are harder to implement and debug than that for a Red-Black tree.
红黑树？
What are the application of Red black tree?
红黑树更通用。他们在添加，删除和查找方面做的相对较好，但是AVL树具有更快的查找速度，代价是减慢添加/删除。以下使用红黑树：
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：map，multimap，multiset。
- Linux内核：完全公平的调度程序，linux / rbtree.h
这篇关于在avl树上的红色黑色树的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
