红黑(RB)树有哪些应用?有没有什么应用程序只能使用RB Tree而不能使用其他数据结构?
A 红黑树 http://en.wikipedia.org/wiki/Red-black_tree是一个特定的实现自平衡二叉搜索树 http://en.wikipedia.org/wiki/Self-balancing_binary_search_tree,今天它似乎是最流行的实现选择。
二叉搜索树 http://en.wikipedia.org/wiki/Binary_search_tree用于实现有限映射,在其中存储一组具有关联值的键。您还可以通过仅使用键而不存储任何值来实现集合。
需要平衡树来保证良好的性能,否则树可能会退化为列表,例如,如果您插入已经排序的键。
搜索树相对于哈希表的优点是您可以按排序顺序有效地遍历树。
AVL树 http://en.wikipedia.org/wiki/Avl_tree是平衡二叉搜索树的另一种变体。在红黑树出现之前它们就很流行。它们更加仔细地平衡,左右子树的高度之间的最大差异为 1(RB 树保证最多为 2)。它们的主要缺点是重新平衡需要付出更多努力。
所以红黑树当然是一个不错的选择,但不是这个应用程序的唯一选择。
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)