为什么std :: map实现为红黑树？

Question

为什么std::map实现为红黑树？

那里有几个平衡的二叉搜索树(BST).选择红黑树的设计权衡是什么？

Answer 1

可能两种最常见的自平衡树算法是红黑树和AVL树.为了在插入/更新之后平衡树,两种算法都使用旋转的概念,其中树的节点被旋转以执行重新平衡.

在两种算法中,插入/删除操作都是O(log n),在Red-Black树的情况下,重新平衡旋转是O(1)操作,而使用AVL这是O(log n)操作,使得红黑树在重新平衡阶段的这个方面更有效,并且是更常用的可能原因之一.

大多数集合库中都使用了红黑树,包括Java和Microsoft .NET Framework的产品.

Answer 2

这真的取决于用法.AVL树通常有更多的重新平衡轮换.因此,如果您的应用程序没有太多的插入和删除操作,但在搜索时权重很大,那么AVL树可能是一个不错的选择.

std::map 使用红黑树,因为它在节点插入/删除和搜索的速度之间得到合理的权衡.

Answer 3

AVL树的最大高度为1.44logn,而RB树的最大高度为2logn.在AVL中插入元素可能意味着在树中的某一点重新平衡.重新平衡完成插入.插入新叶后,必须更新该叶的祖先,或者直到两个子树深度相等的点.必须更新k个节点的概率是1/3 ^ k.重新平衡是O(1).删除元素可能意味着不止一次重新平衡(最多可达树的一半深度).

RB树是4阶B树,表示为二叉搜索树.B树中的4节点导致等效BST中的两个级别.在最坏的情况下,树的所有节点都是2节点,只有一个3节点链到叶子.那片叶子与根部的距离为2logn.

从根到插入点,必须将4节点更改为2节点,以确保任何插入都不会使叶子饱和.从插入开始,必须分析所有这些节点以确保它们正确地表示4节点.这也可以在树上进行.全球成本将是相同的.天下没有免费的午餐!从树中删除元素的顺序相同.

所有这些树都要求节点携带有关高度,重量,颜色等的信息.只有Splay树没有这些附加信息.但是大多数人都害怕Splay树,因为它们的结构是拙劣的!

最后,树木还可以在节点中携带重量信息,从而允许重量平衡.可以应用各种方案.当子树包含的是另一个子树的元素数量的3倍以上时,应该重新平衡.通过单次或双次旋转再次进行再平衡.这意味着2.4logn的最坏情况.一个人可以获得2次而不是3次,这是一个更好的比例,但这可能意味着在这里和那里不会失衡​​1%的子树.整蛊!

哪种树最好？AVL肯定.它们是最简单的代码,其最差高度最接近logn.对于1000000个元素的树,AVL将最多为高度29,RB 40,以及权重平衡36或50,具体取决于比率.

还有很多其他变量:随机性,添加比例,删除,搜索等.

Answer 4

之前的答案仅针对树木替代方案,而红色黑色可能仅仅是出于历史原因.

为什么不是哈希表呢？

类型只需<要将部分排序(比较)用作树中的键.但是,哈希表要求每个键类型都hash定义了一个函数.将这些类型要求保持在最低限度对于通用编程非常重要.

设计一个好的哈希表需要对它将被使用的上下文有深入的了解.它应该使用开放式寻址还是链接链接？在调整大小之前它应该接受多少级别的负载？它应该使用一个避免碰撞的昂贵哈希,还是一​​个粗糙而快速的哈希？

由于STL无法预测哪个是您的应用程序的最佳选择,因此默认需要更灵活.树"只是工作"并且很好地扩展.

(C++ 11确实添加了哈希表unordered_map.您可以从文档中看到它需要设置策略来配置许多这些选项.)

其他树怎么样？

与BST不同,红黑树提供快速查找和自我平衡.另一位用户指出其优于自平衡AVL树的优势.

亚历山大·斯捷潘诺夫(STL的创造者)说,如果std::map再次写作,他会使用B*树而不是红黑树,因为它对现代记忆缓存更友好.

自那时以来最大的变化之一就是缓存的增长.高速缓存未命中非常昂贵,因此现在参考的位置更加重要.基于节点的数据结构具有较低的参考局部性,因此缺乏意义.如果我今天设计STL,我会有一套不同的容器.例如,内存中的B*树比用于实现关联容器的红黑树更好.- 亚历山大斯捷潘诺夫

你应该总是使用红黑树或B*树吗？

在其他场合,Alex表示,std::vector由于类似的原因,它几乎总是最好的列表容器.它很少有意义的使用std::list或者std::deque甚至教我们在上学的情况下(如从列表中删除中间的元素).std::vector是如此之快以至于它击败了那些结构,而不是大的N.

应用这种推理,如果你只有少量的元素(数百？)使用std::vector和线性搜索可能比树的实现更有效std::map.根据插入的频率,排序std::vector组合std::binary_search可以是最快的选择.