有很多关于红黑树的问题，但没有一个能回答它们是如何工作的。为什么叫红黑？这如何保持树平衡(从而提高不平衡的正常二叉搜索树的性能)？我只是在寻找有关其工作原理和原因的概述。
最佳答案
对于搜索和遍历，它与任何二叉树相同。
对于插入和删除，应用了更复杂的算法，旨在确保树不会太不平衡。这些保证所有单项操作将始终在最坏的 O(log n) 时间内运行，而在简单的二叉树中，二叉树可能变得非常不平衡，以至于它实际上是一个链表，给出 O(n) 的最坏情况性能每个单项操作。
红黑树的基本思想是模仿B树，每个节点最多有3个键和4个 child 。 B 树(或 B+ 树等变体)主要用于数据库索引和存储在硬盘上的数据。
每个二叉树节点都有一种“颜色”——红色或黑色。在 B 树类比中，每个黑色节点是适合该 B 树节点的子树的子树根。如果这个节点有红色的 child ，他们也被认为是同一个 B 树节点的一部分。因此，将红黑树转换为 B 树并返回并保留(大部分)结构是可能的(尽管在实践中没有这样做)。唯一可能的异常是，当 B 树节点有两个键和三个子节点时，您可以选择将哪个键放入等效红黑树中的黑色节点。
例如，对于红黑树，从根到叶的每一行都有相同数量的黑色节点。该规则源自B树规则，即所有叶子节点都在同一深度。
尽管这是派生出红黑树的基本思想，但实际用于插入和删除的算法被修改为在更新期间强制执行所有 B 树规则(可能有一个小异常(exception) - 我忘记了) , 但是是为二叉树形式量身定做的。这意味着与执行 B 树插入或删除相比，执行红黑树插入或删除可能会给出不同的结果结构。
更多详情，关注Wikipedia link MigDus 已经提供。
关于algorithm - 红黑树是如何工作的？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/5813639/