什么是红黑树？
2026/1/14...大约 5 分钟Java八股文
注意
内容来源网络，仅供学习使用。
不要相信文档中的链接、联系方式等！！！
什么是红黑树？
典型回答
红黑树是一种自平衡的二叉查找树。
在红黑树中，每个节点是红色或黑色。通过一些规则和颜色的约束，红黑树确保了从根节点到叶子节点的最长路径不会超过最短路径的两倍，因此近似于平衡。这种近似平衡保证了红黑树操作的时间复杂度在最坏情况下仍为对数级别**（O(log n)），**使得红黑树在各种场景中，如关联数组、优先队列等数据结构中非常有用。
- 节点颜色：每个节点要么是红的，要么是黑的。
- 根节点：根节点总是黑色的。
- 红色节点规则：红色节点的子节点必须是黑色的（即红色节点不能相邻）。这条规则也被称为"红色节点不能有红色的孩子"或"红色节点必须有黑色的父节点和黑色的孩子"。
- 每个叶子节点（NIL节点，空节点）是黑色的：这里的叶子节点是指树末端的NIL指针，而不是树中的实际叶子节点。它们通常表示为空（null）。
- 从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点：这个性质保证了没有任何路径能够有两倍于其他路径的长度，从而保持了树的大致平衡。
红黑树有以下优点：
- 保证最坏情况下的性能：红黑树通过维持树的大致平衡，而不是完美平衡。这样确保了在插入、删除和查找操作中最坏情况下的时间复杂度均为 O(log n)。这比普通的二叉搜索树（在最坏情况下可能退化为链表，时间复杂度为 O(n)）要好得多。
- 自平衡：每次插入或删除操作后，红黑树通过旋转和重新着色的方法自动维持平衡，无需额外的操作或维护。
- 数据结构简洁：节点只需要额外存储一个颜色位，因此相比于其他平衡树（如AVL树）来说，内存的额外开销较小。
扩展知识
红黑树在插入和删除操作中通过旋转和重新着色来保持上述性质，以维护树的平衡。插入或删除节点可能会违反红黑树的性质，因此可能需要进行以下操作之一或组合：
- 颜色变更：改变某个节点的颜色来维持红黑树的性质。
- 左旋和右旋：通过旋转操作来重新组织树的结构，从而保持或恢复红黑树的性质。
插入过程
红黑树的插入操作首先按照二叉查找树的规则插入新节点，然后为了维护红黑树的性质，新插入的节点被着色为红色。之后可能需要进行以下一些调整：
- 情况1：新节点是根节点。
- 情况2：新节点的父节点是黑色。
- 情况3：新节点的父节点和叔叔节点都是红色。
1713610051460-8290fd73-a28c-42e7-bdf7-544589a0c07e.png
如此变化之后，需要将祖父节点设置为当前节点，继续插入动作，做自平衡处理。
如我们的例子，新节点是根节点了，那么就按照情况1，直接把他染色成黑色即可：
- 情况4：****
- 情况5：父节点是红色，叔叔节点是黑色或缺失，且新节点位于父节点的外侧。
