红黑树是如何工作的？
关于红黑树有很多问题，但没有一个回答它们是如何工作的。为什么叫红黑呢？这如何保持树平衡（从而提高不平衡的普通二叉搜索树的性能）？我只是在寻找它如何以及为何工作的概述。
There are lots of questions around about red-black trees but none of them answer how they work. Why is it called red-black? How does this keep the tree balanced (thus increasing performance over an unbalanced normal binary search tree)? I'm just looking for an overview of how and why it works.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
对于搜索和遍历，它与任何二叉树相同。
对于插入和删除，应用了更复杂的算法，旨在确保树不会太不平衡。这些保证了所有单项操作总是在最坏的 O(log n) 时间内运行，而在简单的二叉树中，二叉树可能变得非常不平衡，以至于它实际上是一个链表，从而为 O(n) 最坏情况提供了性能每个单项操作。
红黑树的基本思想是模仿 B 树，每个节点最多有 3 个键和 4 个子节点。 B 树（或 B+ 树等变体）主要用于数据库索引和存储在硬盘上的数据。
每个二叉树节点都有一种“颜色”——红色或黑色。在 B 树类比中，每个黑色节点都是适合该 B 树节点的子树的子树根。如果该节点有红色子节点，则它们也被视为同一 B 树节点的一部分。因此，可以（尽管在实践中没有这样做）将红黑树转换为 B 树并返回，同时保留（大部分）结构。唯一可能的异常是，当 B 树节点有两个键和三个子节点时，您可以选择将哪个键放入等效红黑树的黑色节点中。
例如，对于红黑树，从根到叶的每行都具有相同数量的黑色节点。该规则源自 B 树规则，即所有叶节点都处于相同深度。
虽然这是红黑树派生的基本思想，但在实践中用于插入和删除的算法被修改为在更新期间强制执行所有 B 树规则（可能有一个小例外 - 我忘记了），但是为二叉树形式量身定制。这意味着与 B 树插入或删除相比，执行红黑树插入或删除可能会给出与您期望的结果不同的结构。
有关更多详细信息，请点击 MigDus 已提供的维基百科链接。
For searches and traversals, it's the same as any binary tree.
For inserts and deletes, more sophisticated algorithms are applied which aim to ensure that the tree cannot be too unbalanced. These guarantee that all single-item operations will always run in at worst O(log n) time, whereas in a simple binary tree the binary tree can become so unbalanced that it's effectively a linked list, giving O(n) worst case performance for each single-item operation.
The basic idea of the red-black tree is to imitate a B-tree with up to 3 keys and 4 children per node. B-trees (or variations such as B+ trees) are mainly used for database indexes and for data stored on hard disk.
Each binary tree node has a "colour" - red or black. Each black node is, in the B-tree analogy, the subtree root for the subtree that fits within that B-tree node. If this node has red children, they are also considered part of the same B-tree node. So it is possible (though not done in practice) to convert a red-black tree to a B-tree and back, with (most) structure preserved. The only possible anomoly is that when a B-tree node has two keys and three children, you have a choice of which key to goes in the black node in the equivalent red-black tree.
For example, with red-black trees, every line from root to leaf has the same number of black nodes. This rule is derived from the B-tree rule that all leaf nodes are at the same depth.
Although this is the basic idea from which red-black trees are derived, the algorithms used in practice for inserts and deletes are modified to enforce all the B-tree rules (there might be a minor exception - I forget) during updates, but are tailored for the binary tree form. This means that doing a red-black tree insert or delete may give a different structure for the result than that you'd expect comparing with doing the B-tree insert or delete.
For more detail, follow the Wikipedia link that MigDus already supplied.
红黑树是一个有序的二叉树，其中每个顶点的颜色为红色或黑色。 直觉是，红色顶点应该被视为与其父顶点处于相同高度（即，红色顶点的边被认为是“水平”而不是“下降”）。
[我不认为维基百科条目清楚地说明了这一点。]
红黑树的通常规则要求红色顶点永远不会指向另一个红色顶点。这意味着任何以黑色顶点为根的子树（bbb、bbr、rbb、rbr——对于[左子][根][右子]）可能的顶点排列对应于234棵树。
搜索红黑树和搜索普通二叉树是一样的。插入和删除是相似的，只是在某些时候可能需要“修复”旋转来保留红黑不变量。
干杯!
A red-black tree is an ordered binary tree where each vertex is coloured red or black. The intuition is that a red vertex should be seen as being at the same height as its parent (i.e., an edge to a red vertex is thought of as "horizontal" rather than "descending").
[I don't believe the Wikipedia entry makes this point clear.]
The usual rules for red-black trees require that a red vertex never point to another red vertex. This means that the possible vertex arrangements for any subtree rooted with a black vertex (bbb, bbr, rbb, rbr -- for [left child][root][right child]) correspond to 234 trees.
Searching a red-black tree is just the same as searching an ordinary binary tree. Insertion and deletion are similar, except that a "fix-up" rotation may be required at some point to preserve the red-black invariant.
Cheers!