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