为什么 std::map 实现为red-black tree？
std::map
那里有几个 balancer 的binary search trees（BST） . 选择红黑树的设计权衡是什么？
这真的取决于用法 . AVL树通常有更多的重新 balancer 轮换 . 因此，如果您的应用程序没有太多的插入和删除操作，但在搜索时权重很大，那么AVL树可能是一个不错的选择 .
std::map 使用红黑树，因为它在节点插入/删除和搜索的速度之间得到合理的权衡 .
AVL树的最大高度为1.44logn，而RB树的最大高度为2logn . 在AVL中插入元素可能意味着在树中的某一点重新 balancer . 重新 balancer 完成插入 . 插入新叶后，必须更新该叶的祖先，或者直到两个子树深度相等的点 . 必须更新k个节点的概率是1/3 ^ k . 重新 balancer 是O（1） . 删除元素可能意味着不止一次重新 balancer （最多可达树的一半深度） .
RB树是4阶B树，表示为二叉搜索树 . B树中的4节点导致等效BST中的两个级别 . 在最坏的情况下，树的所有节点都是2节点，只有一个3节点链到叶子 . 那片叶子与根部的距离为2logn .
从根到插入点，必须将4节点更改为2节点，以确保任何插入都不会使叶子饱和 . 从插入开始，必须分析所有这些节点以确保它们正确地表示4节点 . 这也可以在树上进行 . 全球成本将是相同的 . 天下没有免费的午餐！从树中删除元素的顺序相同 .
所有这些树都要求节点携带有关高度，重量，颜色等的信息 . 只有Splay树没有这些附加信息 . 但是大多数人都害怕Splay树，因为它们的结构是拙劣的！
最后，树木还可以在节点中携带重量信息，从而允许重量 balancer . 可以应用各种方案 . 当子树包含的是另一个子树的元素数量的3倍以上时，应该重新 balancer . 通过单次或双次旋转再次进行再 balancer . 这意味着2.4logn的最坏情况 . 一个人可以获得2次而不是3次，这是一个更好的比例，但这可能意味着在这里和那里不会失衡1％的子树 . 整蛊！
哪种树最好？ AVL肯定 . 它们是最简单的代码，其最差高度最接近logn . 对于1000000个元素的树，AVL将最多为高度29，RB 40，以及权重 balancer 36或50，具体取决于比率 .
还有很多其他变量：随机性，添加比例，删除，搜索等 .
之前的答案仅针对树木替代方案，而红色黑色可能仅仅是出于历史原因 .
Why not a hash table?
类型只需要部分排序（ < 比较）即可用作树中的键 . 但是，哈希表要求每个键类型都定义了 hash 函数 . 将这些类型要求保持在最低限度对于通用编程非常重要 .
<
hash
设计一个好的哈希表需要对它将被使用的上下文有深入的了解 . 它应该使用开放式寻址还是链接链接？在调整大小之前它应该接受多少级别的负载？它应该使用一个避免碰撞的昂贵哈希，还是一个粗糙而快速的哈希？
由于STL无法预测哪个是您的应用程序的最佳选择，因此默认需要更灵活 . 树“只是工作”和规模很好 .
（C 11确实添加了带有 unordered_map 的哈希表 . 您可以从documentation看到它需要设置策略来配置其中许多选项 . ）
unordered_map
What about other trees?
与BST不同，红黑树提供快速查找和自我 balancer . 另一位用户指出其优于自 balancer AVL树的优势 .
亚历山大·斯捷潘诺夫（STL的创造者）说，如果他再次写一个B *树而不是红黑树，他会使用B *树，因为它对现代记忆缓存更友好 .
此后最大的变化之一就是缓存的增长 . 高速缓存未命中非常昂贵，因此现在参考的位置更加重要 . 基于节点的数据结构具有较低的参考局部性，因此缺乏意义 . 如果我今天设计STL，我会有一套不同的容器 . 例如，内存中的B *树比用于实现关联容器的红黑树更好 . - 亚历山大斯捷潘诺夫
Should you always use a red black tree or B tree?*
在其他场合，Alex表示 std::vector 几乎总是出于类似原因的最佳列表容器 . 即使对于我们在学校教授的情况（例如从列表中间删除元素），使用 std::list 或 std::deque 也很少有意义 . std::vector 是如此之快以至于它击败了那些结构而不是大的 N .
std::vector
std::list
std::deque
N
应用这种推理，如果使用 std::vector 只有少量元素（数百？）并且线性搜索可能比 std::map 的树实现更有效 . 根据插入的频率，排序的 std::vector 与 std::binary_search 结合可能是最快的选择 .
std::binary_search
它只是您实现的选择 - 它们可以作为任何 balancer 树实现 . 各种选择都与微小差异相当 . 因此，任何一个都是好的 .
可能两种最常见的自 balancer 树算法是Red-Black trees和AVL trees . 为了在插入/更新之后 balancer 树，两种算法都使用旋转的概念，其中树的节点被旋转以执行重新 balancer .
在两种算法中，插入/删除操作都是O（log n），在Red-Black树的情况下，重新 balancer 旋转是O(1)操作，而使用AVL这是一个O(log n)操作，使得Red-Black树更有效率 . 重新 balancer 阶段的这个方面以及更常用的可能原因之一 .
大多数集合库中都使用了红黑树，包括Java和Microsoft .NET Framework的产品 .
更新2017-06-14：webbertiger在评论后编辑了它的答案 . 我应该指出，现在它的答案对我来说好多了 . 但我保留了我的答案，就像其他信息一样......
由于我认为第一个答案是错误的（更正：不再两个），第三个答案是错误的肯定 . 我觉得我必须澄清一些事情......
最受欢迎的2棵树是AVL和Red Black（RB） . 主要区别在于利用率：
AVL：如果咨询（阅读）的比例大于操纵（修改），则更好 . 记忆足印小于RB（由于着色所需的位） .
RB：在咨询（阅读）和操纵（修改）之间存在 balancer 或者对咨询进行更多修改的一般情况下更好 . 由于红黑标志的存储，内存占用量略大 .
主要区别来自着色 . RB树中的重新 balancer 操作比AVL少，因为着色使您有时可以跳过或缩短具有相对高成本的重新 balancer 操作 . 由于着色，RB树也具有更高级别的节点，因为它可以接受黑色节点之间的红色节点（具有~2倍更多级别的可能性）使得搜索（读取）效率稍低......但是因为它是常数（2x），它保持在O（log n） .
如果你考虑修改树的性能（有意义的）VS树的咨询性能（几乎无关紧要），对于一般情况，更喜欢RB而不是AVL .
6 回答
这真的取决于用法 . AVL树通常有更多的重新 balancer 轮换 . 因此，如果您的应用程序没有太多的插入和删除操作，但在搜索时权重很大，那么AVL树可能是一个不错的选择 .
std::map使用红黑树，因为它在节点插入/删除和搜索的速度之间得到合理的权衡 .AVL树的最大高度为1.44logn，而RB树的最大高度为2logn . 在AVL中插入元素可能意味着在树中的某一点重新 balancer . 重新 balancer 完成插入 . 插入新叶后，必须更新该叶的祖先，或者直到两个子树深度相等的点 . 必须更新k个节点的概率是1/3 ^ k . 重新 balancer 是O（1） . 删除元素可能意味着不止一次重新 balancer （最多可达树的一半深度） .
RB树是4阶B树，表示为二叉搜索树 . B树中的4节点导致等效BST中的两个级别 . 在最坏的情况下，树的所有节点都是2节点，只有一个3节点链到叶子 . 那片叶子与根部的距离为2logn .
从根到插入点，必须将4节点更改为2节点，以确保任何插入都不会使叶子饱和 . 从插入开始，必须分析所有这些节点以确保它们正确地表示4节点 . 这也可以在树上进行 . 全球成本将是相同的 . 天下没有免费的午餐！从树中删除元素的顺序相同 .
所有这些树都要求节点携带有关高度，重量，颜色等的信息 . 只有Splay树没有这些附加信息 . 但是大多数人都害怕Splay树，因为它们的结构是拙劣的！
最后，树木还可以在节点中携带重量信息，从而允许重量 balancer . 可以应用各种方案 . 当子树包含的是另一个子树的元素数量的3倍以上时，应该重新 balancer . 通过单次或双次旋转再次进行再 balancer . 这意味着2.4logn的最坏情况 . 一个人可以获得2次而不是3次，这是一个更好的比例，但这可能意味着在这里和那里不会失衡1％的子树 . 整蛊！
哪种树最好？ AVL肯定 . 它们是最简单的代码，其最差高度最接近logn . 对于1000000个元素的树，AVL将最多为高度29，RB 40，以及权重 balancer 36或50，具体取决于比率 .
还有很多其他变量：随机性，添加比例，删除，搜索等 .
之前的答案仅针对树木替代方案，而红色黑色可能仅仅是出于历史原因 .
Why not a hash table?
类型只需要部分排序（
<比较）即可用作树中的键 . 但是，哈希表要求每个键类型都定义了hash函数 . 将这些类型要求保持在最低限度对于通用编程非常重要 .设计一个好的哈希表需要对它将被使用的上下文有深入的了解 . 它应该使用开放式寻址还是链接链接？在调整大小之前它应该接受多少级别的负载？它应该使用一个避免碰撞的昂贵哈希，还是一个粗糙而快速的哈希？
由于STL无法预测哪个是您的应用程序的最佳选择，因此默认需要更灵活 . 树“只是工作”和规模很好 .
（C 11确实添加了带有
unordered_map的哈希表 . 您可以从documentation看到它需要设置策略来配置其中许多选项 . ）What about other trees?
与BST不同，红黑树提供快速查找和自我 balancer . 另一位用户指出其优于自 balancer AVL树的优势 .
亚历山大·斯捷潘诺夫（STL的创造者）说，如果他再次写一个B *树而不是红黑树，他会使用B *树，因为它对现代记忆缓存更友好 .
Should you always use a red black tree or B tree?*
在其他场合，Alex表示
std::vector几乎总是出于类似原因的最佳列表容器 . 即使对于我们在学校教授的情况（例如从列表中间删除元素），使用std::list或std::deque也很少有意义 .std::vector是如此之快以至于它击败了那些结构而不是大的N.应用这种推理，如果使用
std::vector只有少量元素（数百？）并且线性搜索可能比std::map的树实现更有效 . 根据插入的频率，排序的std::vector与std::binary_search结合可能是最快的选择 .它只是您实现的选择 - 它们可以作为任何 balancer 树实现 . 各种选择都与微小差异相当 . 因此，任何一个都是好的 .
可能两种最常见的自 balancer 树算法是Red-Black trees和AVL trees . 为了在插入/更新之后 balancer 树，两种算法都使用旋转的概念，其中树的节点被旋转以执行重新 balancer .
在两种算法中，插入/删除操作都是O（log n），在Red-Black树的情况下，重新 balancer 旋转是O(1)操作，而使用AVL这是一个O(log n)操作，使得Red-Black树更有效率 . 重新 balancer 阶段的这个方面以及更常用的可能原因之一 .
大多数集合库中都使用了红黑树，包括Java和Microsoft .NET Framework的产品 .
更新2017-06-14：webbertiger在评论后编辑了它的答案 . 我应该指出，现在它的答案对我来说好多了 . 但我保留了我的答案，就像其他信息一样......
由于我认为第一个答案是错误的（更正：不再两个），第三个答案是错误的肯定 . 我觉得我必须澄清一些事情......
最受欢迎的2棵树是AVL和Red Black（RB） . 主要区别在于利用率：
AVL：如果咨询（阅读）的比例大于操纵（修改），则更好 . 记忆足印小于RB（由于着色所需的位） .
RB：在咨询（阅读）和操纵（修改）之间存在 balancer 或者对咨询进行更多修改的一般情况下更好 . 由于红黑标志的存储，内存占用量略大 .
主要区别来自着色 . RB树中的重新 balancer 操作比AVL少，因为着色使您有时可以跳过或缩短具有相对高成本的重新 balancer 操作 . 由于着色，RB树也具有更高级别的节点，因为它可以接受黑色节点之间的红色节点（具有~2倍更多级别的可能性）使得搜索（读取）效率稍低......但是因为它是常数（2x），它保持在O（log n） .
如果你考虑修改树的性能（有意义的）VS树的咨询性能（几乎无关紧要），对于一般情况，更喜欢RB而不是AVL .