为什么std::map实现为红黑树？
那里有几种平衡二叉搜索树（BST）。选择红黑树时的设计权衡是什么？
问问题
98902 次
6 回答
49
这真的取决于使用情况。AVL 树通常有更多的再平衡轮换。因此，如果您的应用程序没有太多的插入和删除操作，但对搜索的权重很大，那么 AVL 树可能是一个不错的选择。
std::map使用红黑树，因为它在节点插入/删除和搜索的速度之间进行了合理的权衡。
于 2012-05-26T18:32:09.763 回答
31
先前的答案仅针对树的替代方案，而红黑可能仅出于历史原因而保留。
为什么不是哈希表？
类型只需要<运算符（比较）用作树中的键。但是，哈希表要求每个键类型都hash定义了一个函数。将类型要求保持在最低限度对于泛型编程非常重要，因此您可以将其与各种类型和算法一起使用。
设计一个好的哈希表需要对它所使用的上下文有深入的了解。它应该使用开放寻址还是链接链接？在调整大小之前它应该接受什么级别的负载？它应该使用避免冲突的昂贵散列，还是使用粗略和快速的散列？
由于 STL 无法预测哪个是您的应用程序的最佳选择，因此默认值需要更加灵活。树木“正常工作”并且可以很好地扩展。
（C++11 确实添加了带有 . 的哈希表unordered_map。您可以从文档中看到它需要设置策略来配置其中的许多选项。）
其他树呢？
与 BST 不同，红黑树提供快速查找和自我平衡。另一位用户指出了它相对于自平衡 AVL 树的优势。
Alexander Stepanov（STL 的创建者）表示，如果他再次编写，他将使用 B* 树而不是红黑树std::map，因为它对现代内存缓存更友好。
从那时起，最大的变化之一就是缓存的增长。缓存未命中的代价非常高昂，因此现在引用的局部性更为重要。基于节点的数据结构具有较低的参考局部性，因此意义不大。如果我今天设计 STL，我会有一组不同的容器。例如，在实现关联容器时，内存中的 B*-tree 比红黑树要好得多。——亚历山大·斯捷潘诺夫
地图应该总是使用树吗？
另一种可能的映射实现是排序向量（插入排序）和二进制搜索。这适用于不经常修改但经常查询的容器。我经常在 C 中这样做，因为qsort它bsearch是内置的。
我什至需要使用地图吗？
缓存考虑意味着即使对于我们在学校教过的那些情况（例如从列表中间删除一个元素） ，使用std::list或std::deque过度使用也很少有意义。std:vector应用相同的推理，使用 for 循环对列表进行线性搜索通常比为几次查找构建地图更有效和更简洁。
当然，选择一个可读的容器通常比性能更重要。
于 2017-12-22T00:46:07.450 回答
28
AVL 树的最大高度为 1.44logn，而 RB 树的最大高度为 2logn。在 AVL 中插入一个元素可能意味着在树中的某个点重新平衡。重新平衡完成插入。插入新叶子后，必须更新该叶子的祖先，直到根，或者直到两个子树的深度相等的点。必须更新 k 个节点的概率是 1/3^k。再平衡是 O(1)。移除一个元素可能意味着不止一次的重新平衡（最多为树的一半深度）。
RB-trees 是表示为二叉搜索树的 4 阶 B-tree。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，具体取决于比率。
还有很多其他变量：随机性、添加、删除、搜索的比率等。
于 2011-07-16T01:52:59.417 回答
3
这只是您实现的选择——它们可以作为任何平衡树来实现。各种选择都具有可比性，差异很小。因此，any 和 any 一样好。
于 2011-03-13T08:48:05.090 回答
3
2017-06-14 更新：webbertiger 在我发表评论后编辑其答案。我应该指出，它的答案现在对我来说好多了。但我保留了我的答案作为附加信息......
由于我认为第一个答案是错误的（更正：不再是两者），而第三个答案是错误的。我觉得我必须澄清一些事情......
最受欢迎的 2 种树是 AVL 和红黑 (RB)。主要区别在于利用率：
- AVL：如果咨询（阅读）的比例大于操纵（修改），则更好。内存占用比 RB 略少（由于着色所需的位）。
- RB：在咨询（阅读）和操纵（修改）之间或更多修改超过咨询之间存在平衡的一般情况下更好。由于存储了红黑标志，内存占用略大。
主要区别在于着色。RB 树中的重新平衡操作确实比 AVL 少，因为着色使您有时可以跳过或缩短具有相对高成本的重新平衡操作。由于着色，RB 树也有更高级别的节点，因为它可以接受黑色节点之间的红色节点（有大约 2 倍以上的级别的可能性），这使得搜索（读取）的效率有点低......但因为它是一个常数（2x），它保持在O（log n）。
如果您考虑修改树的性能影响（显着）VS 咨询树的性能影响（几乎微不足道），对于一般情况，自然会更喜欢 RB 而不是 AVL。
于 2017-05-30T20:33:26.193 回答