关于红黑树有很多问题，但没有一个能回答它们是如何工作的。为什么叫红黑？这如何保持树的平衡（从而提高性能超过一个不平衡的正常二进制搜索树）？我只是想了解一下它的工作原理。
最佳答案
对于搜索和遍历，它与任何二叉树相同。
对于插入和删除，应用了更复杂的算法，旨在确保树不会太不平衡。这些保证了所有的单项目操作总是在最坏的o（log n）时间运行，而在一个简单的二叉树中，二叉树可能变得非常不平衡，以至于它实际上是一个链表，为每个单项目操作提供了最坏的o（n）性能。
红黑树的基本思想是模拟一个b树，每个节点最多有3个键和4个子节点。b树（或b+树等变体）主要用于数据库索引和存储在硬盘上的数据。
每个二叉树节点都有一个“颜色”-红色或黑色。在b-tree类比中，每个黑色节点都是适合于该b-tree节点的子树的子树根。如果此节点具有红色子节点，则它们也被视为同一b树节点的一部分。因此，有可能（尽管在实践中没有这样做）将红黑树转换为b-树并返回，保留（大多数）结构。唯一可能的异常是，当一个b树节点有两个键和三个子节点时，您可以选择哪个键进入等价的红黑树中的黑色节点。
例如，对于红黑树，从根到叶的每一行都有相同数量的黑色节点。此规则是从所有叶节点都在同一深度的b树规则派生的。
虽然这是红黑树的基本思想，但是实际中用于插入和删除的算法经过修改，在更新期间强制执行所有的b树规则（可能有一个小的异常-我忘记了），但是是为二叉树形式定制的。这意味着，与执行b树插入或删除相比，执行红黑树插入或删除可能会为结果提供不同的结构。
有关更多详细信息，请遵循migdus已经提供的Wikipedia link。