为什么std :: map实现为红黑树？
为什么std :: map实现为红黑树 ？
有几个平衡的二叉search树 （BST）。 在select红黑树时，什么是devise权衡？
可能两种最常见的自平衡树algorithm是红黑树和AVL树 。 为了在插入/更新之后平衡树，两种algorithm都使用旋转的概念，其中树的节点被旋转以执行重新平衡。
在两种algorithm中，插入/删除操作都是O（log n），在红黑树重新平衡旋转的情况下是O（1）操作，而在AVL中这是O（log n）操作，使得红黑树在再平衡阶段的这个方面更有效率，并且是更常用的可能原因之一。
红黑树被用在大多数收集库中，包括来自Java和Microsoft .NET Framework的产品。
这真的取决于使用情况。 AVL树通常有更多的重新平衡旋转。 所以，如果你的应用程序没有太多的插入和删除操作，但是重视search，那么AVL树可能是一个不错的select。
std::map使用红黑树，因为它在节点插入/删除和search速度之间取得合理的折衷。
AVL树的最大高度为1.44logn，而RB树的最大值为2logn。 在AVL中插入元素可能意味着树中某一点的重新平衡。 重新平衡完成插入。 在插入新叶子之后，更新该叶子的祖先必须完成到根，或者直到两个子树具有相同深度的点。 不得不更新k个节点的概率是1/3 ^ k。 再平衡是O（1）。 去除一个元素可能意味着不止一次的重新平衡（高达树的一半深度）。
RB树是以二叉search树表示的4阶B树。 B树中的4节点在等效的BST中产生两个等级。 在最坏的情况下，树的所有节点都是2个节点，只有一个3节点的链向下。 那个叶子将在根目录的2logn处。
从根节点到插入点，必须将4节点转换为2节点，以确保任何插入都不会使树叶饱和。 从插入回来，所有这些节点必须进行分析，以确保它们正确代表4节点。 这也可以在树上进行。 全球成本将是一样的。 天下没有免费的午餐！ 从树中移除一个元素的顺序是相同的。
所有这些树要求节点携带有关身高，体重，颜色等的信息。只有Splay树没有这些附加信息。 但是大多数人都害怕Splay树，因为它们的结构太过分了！
最后，树还可以在节点中携带重量信息，从而实现重量平衡。 可以应用各种scheme。 当一个子树包含超过其他子树元素数量的3倍时，应该重新平衡。 通过一次或两次轮换再次平衡。 这意味着2.4logn的最坏情况。 人们可以用2次而不是3次来获得，这个比例要好得多，但这可能意味着在这里和那里不平衡的子树的数量less于1％。 整蛊！
哪种树是最好的？ AVL肯定。 他们是最简单的代码，并有最接近login的最差的高度。 对于100万个元素的树，AVL将最多是高度29，RB 40，以及权重平衡36或50，具体取决于比例。
还有很多其他variables：随机性，添加比例，删除，search等。
这只是您实现的select – 它们可以作为任何平衡树来实现。 各种各样的select都可以与小的差异相媲美。 因此，任何事情都是一样的。
更新2017-06-14：webbertiger在我评论后编辑其答案。 我应该指出，现在的答案现在好多了。 但我保留我的答案，只是作为额外的信息…
由于我认为第一个答案是错误的（纠正：不是两个），第三个错误的确认。 我觉得我必须澄清事情…
最受欢迎的两种树是AVL和红黑（RB）。 主要区别在于利用率：
- AVL：如果咨询（阅读）的比例大于操纵（修改），则更好。 内存脚印比RB略小（由于着色需要的位）。
- RB：在咨询（阅读）和操纵（修改）之间取得平衡或对咨询进行更多修改的一般情况下更好。 由于存储红黑旗，存储器占用空间稍大。
主要的区别来自于着色。 RB树中的重新平衡操作比AVLless，因为着色使您有时可以跳过或缩短具有相对高成本的重新平衡操作。 由于着色，RB树也有更高层次的节点，因为如果可以接受黑色节点之间的红色节点（有可能达到更多层次的2倍），使得search（读取）效率稍低一点…但是因为它是一个常数（2x），它保持在O（log n）。
如果考虑到树的修改（有意义的）与树的协商的性能下降（几乎无关紧要），那么在一般情况下，优先考虑RB比AVL更自然。
