红黑树是如何工作的？

Question

有很多问题围绕着红黑树，但它们都没有回答它们是如何工作的。为什么叫做红黑树？它是如何保持树的平衡（从而提高性能，相较于不平衡的二叉搜索树）？我只是想知道它是如何以及为什么运作的概述。

- Pete

Answer 1

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

对于插入和删除，会应用更复杂的算法，旨在确保树不会过于不平衡。这些算法可以保证所有单个项操作始终以最坏情况下 O(log n) 的时间运行，在简单的二叉树中，二叉树可能变得非常不平衡，实际上成为一个链接列表，每个单个项操作都具有 O(n) 的最坏情况性能。

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

每个二叉树节点有一种“颜色” - 红色或黑色。每个黑色节点在 B 树类比中都是符合该 B 树节点内部的子树的根节点。如果此节点具有红色子节点，则它们也被视为同一 B 树节点的一部分。因此，理论上可以将红黑树转换为 B 树并返回，大多数结构得到保留。唯一可能出现的异常情况是当 B 树节点具有两个键和三个子节点时，您可以选择哪个键进入等效的红黑树中的黑色节点。

例如，对于红黑树，从根到叶子的每一条路径上都有相同数量的黑色节点。这个规则是从B树规则中推导出来的，即所有叶子节点都在相同的深度上。

虽然这是红黑树的基本思想，但实际上用于插入和删除的算法被修改以强制执行所有B树规则（可能有一个小例外-我忘了），但是它们是针对二叉树形式进行调整的。这意味着进行红黑树插入或删除可能会给出与进行B树插入或删除时预期不同的结果结构。

要了解更多详细信息，请参考MigDus已经提供的Wikipedia链接。

- user180247

Answer 2

红黑树是一种有序的二叉树，其中每个节点都被涂成红色或黑色。感性理解就是一个红色节点应该被看作与其父节点处于相同的高度（也就是说，指向红色节点的边被认为是“水平”而非“下降”的）。

通常规则要求红色节点不能指向另一个红色节点。这意味着任何以黑色节点为根节点的子树的可能顶点排列方式（bbb、bbr、rbb、rbr——代表[左孩子][根节点][右孩子]）对应着234种树形结构。

在红黑树中搜索与普通的二叉树搜索方法相同。插入和删除类似，但需要在某些时候进行“修复”旋转以保持红黑不变式。

干杯！

- Rafe

---

直觉上，应该将红色顶点视为与其父节点处于相同的高度（即，到红色顶点的边被视为“水平的”，而非“下降的”）。 恍然大悟，谢谢！ - Nathan Ridley