algorithm - 红黑树是如何工作的？

Question

关于红黑树有很多问题，但没有一个回答它们是如何工作的。为什么叫红黑？这如何使树保持平衡（从而提高不平衡的正常二叉搜索树的性能）？我只是在寻找它如何工作以及为什么工作的概述。

Answer 1

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

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

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

每个二叉树节点都有一个“颜色”——红色或黑色。在 B 树的类比中，每个黑色节点都是适合该 B 树节点的子树的子树根。如果这个节点有红色的孩子，他们也被认为是同一个 B 树节点的一部分。因此，可以（尽管在实践中没有这样做）将红黑树转换为 B 树并返回，并保留（大多数）结构。唯一可能的异常情况是，当 B 树节点有两个键和三个子节点时，您可以选择将哪个键放入等效的红黑树中的黑色节点。

例如，对于红黑树，从根到叶的每一行都有相同数量的黑色节点。该规则源自所有叶节点处于相同深度的 B 树规则。

虽然这是派生红黑树的基本思想，但在实践中用于插入和删除的算法被修改为在更新期间强制执行所有 B 树规则（可能有一个小例外 - 我忘记了），但是为二叉树形式量身定制。这意味着与执行 B-tree 插入或删除相比，执行红黑树插入或删除可能会为结果提供不同的结构。

有关更多详细信息，请访问 MigDus 已经提供的Wikipedia 链接。

Answer 2

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

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

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

搜索红黑树与搜索普通二叉树是一样的。插入和删除是相似的，除了在某些时候可能需要“修复”旋转以保持红黑不变量。

干杯!