红黑树

1. 历史

  • 是什么: 红黑树是一种自平衡二叉搜索树，用于快速存储和检索有序信息。
  • 怎么形成的:
    • 1972年，Rudolf Bayer发明了一种称为”对称二叉B树”的数据结构，后来被称为2-3-4树或2-3树。
    • 1978年，Leonidas J. Guibas 和 Robert Sedgewick 从对称二叉B树中衍生出了红黑树。
    • 1993年，Arne Andersson 引入了右倾红黑树的概念，简化了插入和删除操作。
    • 1999年，Chris Okasaki 展示了如何使插入操作完全函数化。
    • 2008年，Sedgewick提出了左倾红黑树，利用Andersson的想法简化了插入和删除操作。

2. 成因

普通二叉搜索树在最坏情况下可能会退化为线性链表，导致搜索时间复杂度变为 O(n)。红黑树通过引入颜色属性和一系列规则，确保树的高度始终保持平衡，从而保证了在最坏情况下也能保持 O(log n) 的搜索、插入和删除时间复杂度。

3. 解决方案

红黑树通过以下属性和规则来保持平衡：

  • 属性: 每个节点都有颜色，可以是红色或黑色。
  • 规则:
    1. 每个节点要么是红色，要么是黑色。
    2. 根节点是黑色。
    3. 所有叶子节点（NIL节点）都是黑色的。
    4. 如果一个节点是红色的，那么它的两个子节点都是黑色的。
    5. 对于每个节点，从该节点到其所有后代叶子节点的路径上，黑色节点的数量必须相同。

红黑树的平衡性目标是什么?

红黑树的平衡性目标不是像完全二叉树那样严格要求每个节点的左右子树高度完全相同，而是要求树的高度在一定程度上可控，避免出现极端不平衡的情况（例如，所有节点都只有左孩子，形成一个类似链表的结构）。

接下来，我们看看这五个规则如何共同作用来实现这个目标：

每个节点要么是红色，要么是黑色。 这个规则引入了“颜色”的概念，为红黑树的平衡性调整提供了操作空间。

根节点是黑色。 这个规则可以看作是一个约定，它简化了一些情况的讨论，对平衡性本身没有直接影响。

所有叶子节点（NIL节点）都是黑色的。 NIL 节点是红黑树中用于标记空节点的特殊节点。这个规则是为了方便算法描述和实现，同时也保证了从任何节点到其所有后代叶子节点的路径上都至少有一个黑色节点。

如果一个节点是红色的，那么它的两个子节点都是黑色的。 这个规则是最关键的规则之一。它限制了红色节点的出现位置，避免了树中出现连续的红色节点。这也就意味着，从根节点到任何叶子节点的路径上，黑色节点的数量至少是红色节点数量的一半。

对于每个节点，从该节点到其所有后代叶子节点的路径上，黑色节点的数量必须相同。 这个规则被称为“黑高”性质，它是红黑树平衡性的核心。它保证了从根节点到所有叶子节点的最长路径和最短路径的长度之比不会超过 2:1。

总结：

规则 4 和规则 5 共同作用，限制了红黑树的最长路径长度。规则 4 保证了黑色节点的数量至少是红色节点数量的一半，而规则 5 则保证了所有路径上的黑色节点数量相同。这两个规则结合起来，就保证了红黑树的最长路径长度不会超过最短路径长度的两倍。

最终效果：

由于红黑树的高度被限制在一定范围内，因此红黑树上的查找、插入和删除操作的时间复杂度都能保持在 O(log n) 级别，其中 n 是树中节点的数量。这使得红黑树成为了一种高效的数据结构，适用于各种需要维护有序数据的场景。

能不能增加一种或者n种颜色？

红黑树的设计目标是在保持树的平衡性的同时，尽量降低维护平衡性的开销。使用两种颜色是实现这一目标的最简洁高效的方式。红黑树通过颜色来表示节点之间的关系，并通过旋转和颜色变换来维护平衡性。

简洁性: 两种颜色足以表示红黑树所需的节点关系信息。引入更多颜色会增加规则的复杂度，使得实现和维护更加困难。 效率: 红黑树的操作（插入、删除、查找）复杂度都为 O(log n)，这已经是最优的渐进时间复杂度。引入更多颜色并不能在渐进意义上提升效率，反而可能因为更复杂的规则而降低实际性能。 如果使用更多颜色会怎么样？

更复杂的规则: 引入更多颜色意味着需要定义更多颜色规则来维持树的平衡性，这将大大增加算法的复杂度，使得实现和维护变得更加困难。 效率难以提升: 红黑树的效率已经接近理论最优，更多颜色带来的额外复杂度很可能抵消其带来的任何潜在效率提升，甚至可能降低实际性能。 没有必要: 红黑树的设计已经足够优雅和高效，能够满足绝大多数应用场景的需求，没有必要为了追求理论上的“完美平衡”而牺牲简洁性和效率。

4. 原理

红黑树通过在插入和删除节点时进行颜色翻转和旋转操作来保持上述属性和规则，从而保证树的平衡。

  • 颜色翻转: 改变节点的颜色，例如将红色节点变为黑色，或将黑色节点变为红色。
  • 旋转: 通过改变节点之间的父子关系来调整树的结构，保持树的平衡。

5. 总结

红黑树是一种高效的自平衡二叉搜索树，它保证了在最坏情况下也能保持对数级别的搜索、插入和删除时间复杂度。红黑树被广泛应用于各种数据结构和算法中，例如 Linux 内核、Java 集合框架等。

参考链接