红黑树如何工作？

Question

关于红黑树有很多问题，但他们都没有回答他们如何工作。为什么叫做红黑色？这如何保持树平衡（从而提高不平衡的普通二叉搜索树的性能）？我只是在寻找如何和为什么它的作品的概述。

Answer 1

对于搜索和遍历，它与任何二叉树相同。

对于插入和删除操作，应用了更复杂的算法，旨在确保树不会太不平衡。这些保证了所有的单项操作总是在最差的O（log n）时间运行，而在一个简单的二叉树中，二叉树可能变得非常不平衡以至于它实际上是一个链表，给出了O（n）最坏情况下的性能每个单项操作。

红黑树的基本思想是模仿一个B树，每个节点最多3个密钥和4个孩子。 B树（或诸如B +树之类的变体）主要用于数据库索引和存储在硬盘上的数据。

每个二叉树节点都有一个“颜色” - 红色或黑色。在B树类比中，每个黑色节点是适合该B树节点的子树的子树根。如果此节点具有红色子节点，则它们也被视为同一个B树节点的一部分。所以有可能（虽然在实践中没有这样做）将红黑树转换为B树并返回，并保留（大部分）结构。唯一可能的原因是，当一个B树节点有两个键和三个子节点时，你可以选择在同等红黑树中的黑节点中选择哪个键。

例如，对于红黑树，从根到叶的每条线具有相同数量的黑节点。该规则是从所有叶节点处于相同深度的B树规则导出的。

尽管这是导出红黑树的基本思想，但在实践中用于插入和删除的算法被修改为强制执行所有B树规则（可能有一个小例外 - 我忘记了）更新，但是为二叉树形式量身定制。这意味着做一个红黑树插入或删除可能会给出一个不同于你期望的与做B树插入或删除比较的结果。

有关更多详细信息，请按照MigDus已提供的Wikipedia link。

Answer 2

红黑树是一个有序的二叉树，其中每个顶点都是红色或黑色。 直觉是红色顶点应该被看作与其父母处于同一高度（即红色顶点的边缘被认为是“水平”而不是“下降”）。

[我不相信维基百科条目说明了这一点清楚了。]

为红黑树通常的规则要求一个红色的顶点永远指向另一个红色顶点。这意味着对于以黑色顶点为根的任何子树（bbb，bbr，rbb，rbr - 对于[左边的子] [root] [右边的子]），可能的顶点排列对应于234棵树。

搜索红黑树就像搜索普通的二叉树一样。插入和删除是相似的，除了可能需要在某个点进行“修正”旋转以保留红黑不变。

干杯！