红黑树的原理

红黑树的原理

红黑树（Red-Black Tree）是一种自平衡的二叉搜索树，它在计算机科学中被广泛应用于实现有序集合和映射等数据结构。它通过引入颜色标记和一些特定的操作规则，保持了树的平衡性，从而确保了高效的插入、删除和查找操作。

红黑树的原理可以通过以下几个规则来解释：

节点颜色：每个节点被标记为红色或黑色。

根节点和叶子节点：根节点是黑色的，叶子节点（NIL节点或空节点）是黑色的。叶子节点不存储数据，只用作树的结束标志。

节点路径：从每个节点到其每个叶子节点的路径上，包含相同数量的黑色节点。这个规则确保了树的黑色平衡，即任意路径上的黑色节点数量是相同的。

红色节点规则：不能有两个相邻的红色节点。这个规则确保了树的红色平衡，即红色节点在树中分布均匀。

插入操作：当插入一个新节点时，首先按照二叉搜索树的插入规则将节点插入到合适的位置，并将节点标记为红色。然后，根据红黑树的规则进行必要的调整，以保持红黑树的性质。调整包括以下几种情况：（1）变色：如果父节点和叔节点都是红色，将父节点和叔节点变为黑色，祖父节点变为红色。（2）旋转：如果父节点是红色，但叔节点是黑色或缺失（NIL节点），且新节点是父节点的右子节点，或者父节点是祖父节点的左子节点且新节点是父节点的左子节点，进行相应的旋转操作来调整节点位置。

删除操作：当删除一个节点时，首先按照二叉搜索树的删除规则删除节点，并用其后继节点或前驱节点来替代被删除的节点。然后，根据红黑树的规则进行必要的调整，以保持红黑树的性质。调整包括以下几种情况：（1）兄弟节点为红色：通过旋转操作将兄弟节点变为黑色，然后重新调整。（2）兄弟节点为黑色且其子节点都为黑色（包括NIL节点）：将兄弟节点变为红色，然后将当前节点上移作为新的当前节点。（3）兄弟节点为黑色且至少有一个子节点为红色：通过旋转操作调整节点位置。

通过这些规则和调整操作，红黑树保持了平衡性，确保了树的高度始终保持在较小的范围内，使得插入、删除和查找操作的时间复杂度保持在O(log n)级别。这使得红黑树在许多应用中成为一种高效的数据结构选择，如C++ STL中的map和set就是基于红黑树实现的。

红黑树的定义

定义 — 是每个节点都带有颜色属性（颜色为红色或黑色）的自平衡二叉查找树，满足下列性质：
1）节点是红色或黑色；
2）根节点是黑色；
3）所有叶子节点都是黑色节点(NULL)；
4）每个红色节点必须有两个黑色的子节点。(从每个叶子到根的所有路径上不能有两个连
续的红色节点。)
5）从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。

为什么会有红黑树

在有些时候,二叉树就已经能够达到很高的效率了,但是有一种情况会导致效率下降

15 13 16 11 9 7 5 3
按照二叉搜索树构建构建的方式，我们将得到下面这样一棵树：

如果我们查找值为 3 的节点，9 个节点需要比较的次数是 7 次

9 5 13 7 3 11 16 15
同样的数据，如果我们按照以下顺序构造一棵二叉排序树：

则查找值为 3 的节点，9 个节点需要比较的次数是 3 次. 为什么两者达到了如此之大的差距，原因是第一棵树左右不够平衡，导致出现比较极端的情况。

解决方案： 红黑树
红黑树是一种自平衡二叉查找树，从上面红黑树的图可以看到，根结点右子树显然比左子树高，但左子树和右子树的黑结
点的层数是相等的，也即任意一个结点到到每个叶子结点的路径都包含数量相同的黑结点。所以我们叫红黑树这种平衡为
黑色完美平衡

红黑树构建

第一步：使用第一个元素 15 创建根节点，根节点一定是黑色，如图:

第二步：将 13 加入到红黑树，按照二叉搜索树的规则,13 应插入到 15 的左子节点上面，此时插入红色节点不会破坏红黑树的平衡，直接插入即可,如图:

第三步：将 16 加入到红黑树，16 应插入到 15 的右子节点上面，此时插入红色节点不会破坏红黑树的平衡，直接插入即可，如图所示

第四步：将 11 加入到红黑树，11 应插入到 13 的左子节点上面，此时继续插入红色节点会破坏红黑树的平衡规则，红色
节点下必须是一对黑色子节点，而插入黑色节点也违背了规则 5（从任一节点到其每个叶子的所有简单路径都包含相同数
目的黑色节点）,所以必须进行如下特殊处理:
1.将 11 的父节点 13 和叔父节点都设置为黑色

第五步 将 9 加入到红黑树，9 应插入到 11 的左子节点上面，此时无论插入红色节点或黑色节点都会破坏规则，必须对节
点做乾坤大挪移处理：

第五步 将 7 加入到红黑树，7 应插入到 9 的左子节点上面，此时无论插入红色节点或黑色节点都会破坏规则，必须对节
点做变色处理：

第六步 将 5 加入到红黑树，5 应插入到 7 的左子节点上面，此时无论插入红色节点或黑色节点都会破坏规则，必须对节
点做旋转处理：

第七步 将 3 加入到红黑树，3 应插入到 5 的左子节点上面，此时无论插入红色节点或黑色节点都会破坏规则，我们先对
父节点和叔叔节点做变色处理：

但这样破坏了红色节点 11 必须有两个黑色子节点的规则，因此还得进一步向上调整，此时，要保障红黑树的平衡，我们需
要对根节点进行右旋