[C++] 红黑树的实现：原则和基本分析 - 红黑树概念
红黑树（Red-Black Tree）是一种自平衡的二叉搜索树，它通过在节点上附加额外的颜色属性（红色或黑色），并遵循一定的规则来确保树的高度尽可能小，确保没有一条路径会比其他路径长出2倍，从而在最坏的情况下保证 (O(log N)) 的操作效率。
红黑树的规则
红黑树的每个节点除了键值外，还存储一个颜色属性。要保持树的平衡性，必须满足以下规则：
- 每个节点要么是红色，要么是黑色。
- 根节点必须是黑色。
- 红色节点的两个子节点必须是黑色，即没有两个连续的红色节点。
-
从任意节点到其叶子节点的所有路径上，必须包含相同数量的黑色节点（这被称为黑高，Black Height，
bh）。
这些规则确保了红黑树的近似平衡。通过规则4，可以推导出红黑树的最长路径不会超过最短路径的两倍，这就意味着红黑树的高度维持在 (O(log N))，从而保证了查找、插入和删除的效率。
红黑树如何确保最长路径不超过最短路径的2倍
红黑树的一个重要特性是保持相对平衡，从而使得查找、插入和删除操作的时间复杂度都能保持在 (O(log N)) 的范围内。具体而言，红黑树的设计确保了最长路径的长度不会超过最短路径的2倍。这是通过红黑树的四条规则，尤其是规则2、3和4来实现的。
红黑树规则
为了更好地理解红黑树的平衡性，让我们复习一下红黑树的四条基本规则：
- 每个节点要么是红色，要么是黑色。
- 根节点必须是黑色。
- 红色节点的两个子节点必须是黑色，即没有连续的红色节点。
- 从任意节点到其叶子节点的所有路径上，必须包含相同数量的黑色节点。
其中，规则4 是红黑树平衡的核心，它直接限制了路径上的黑色节点数量，进而影响树的高度和路径长度。
最短路径与最长路径的分析
最短路径：全黑路径
根据规则4，从根节点到每一个叶子节点的路径上，黑色节点的数量是相同的。因此，最短路径就是只有黑色节点的路径。这种路径上没有任何红色节点，只有黑色节点。
我们用 bh（Black Height，黑高）来表示从根节点到叶子节点的黑色节点数量（不包括红色节点）。因此，最短路径的长度等于 bh。
最长路径：红黑交替路径
根据规则3，红色节点的子节点必须是黑色，意味着不可能有连续的红色节点。因此，在极端情况下，最长的路径是红黑交替的路径。
如果路径上的黑色节点数量为 bh，那么在最坏的情况下，每个黑色节点下面都有一个红色节点。因此，最长的路径将是交替排列的红黑节点的路径，其长度为 2 * bh。
结论：红黑树的平衡性如何保障操作效率
红黑树通过严格的颜色规则和旋转操作，确保了树的路径长度差异有限。通过保证黑色节点数目相等和没有连续的红色节点，红黑树确保了每一条从根到叶子的路径上的黑色节点数量相同，同时限制了红色节点的数量。
具体来说，红黑树的平衡性源于以下几个因素：
- 红色节点不能连续：这减少了极端情况下过多红色节点导致的树的不平衡。
- 路径上的黑色节点数相同：这意味着所有路径的黑色节点数量一致，保证了从根到叶子的路径差距不会太大。
- 旋转操作和变色：在插入或删除节点时，红黑树通过旋转和变色操作，动态维护这几个规则。
由于红黑树的这些规则，红黑树的最短路径和最长路径之间的长度差异不会超过2倍。也正是因为这一点，红黑树能够保证插入、删除和查找操作的时间复杂度为 (O(log N))，即便在最坏的情况下，红黑树的效率仍然能够得到保证。