红黑树在AVL树 [英] Red black tree over avl tree

问题描述

AVL和红黑色的中，这两种不同的红色和黑色的nodes.what的主要目的，我们挑选一红黑色的树，而不是AVL树是自平衡？什么是红黑色的树中的应用程序？

解决方案

  

什么是主要目的，我们挑选一，而不是AVL树红黑色的树？

这两个红黑树和AVL树是最常用的平衡二叉搜索树，它们支持插入，删除和查找在保证 O（logN）的时间 。但是，有以下两者之间的比较点：

• AVL树是更刚性的平衡，因此提供了更快的查找。因此，对于一个查找密集型任务使用的AVL树。
• 对于插入密集型TAKS，使用红黑树。
• AVL树存储在每个节点的平衡因子。这需要 O（N）的额外空间。然而，如果我们知道，这将在树被插入钥匙大于零总是会更大，我们可以利用的键的符号位来存储一个红 - 黑树的颜色信息。因此，在这种情况下，红黑树需要 O（1）额外的空间。
• 在一般情况下，为AVL树的旋转是难度比，对于一个红 - 黑树来实现和调试。

  

什么是红黑色的树中的应用程序？

红黑树是更通用的。他们做的比较出色的添加，删除和查询，但AVL树有更快的查找窗口以较慢的添加/删除成本。红 - 黑树是用于以下：

• Java的：java.util.TreeMap中，java.util.TreeSet中
• 在C ++ STL：地图，multimap中，多集
• 在Linux内核：完全公平调度器，Linux的/ rbtree.h

Avl and Red black tree both are self balanced except Red and black color in the nodes.what's the main aim we are chossing Red black tree instead of Avl tree? what are the application of Red black tree?

解决方案

What's the main aim we are chossing Red black tree instead of Avl tree?

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 taks, 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 O(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?

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 kernel: completely fair scheduler, linux/rbtree.h

这篇关于红黑树在AVL树的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！