红黑树学习

作者: 盼旺 | 来源:发表于2019-08-17 12:31 被阅读0次

红黑树必须说的东西

当在10亿数据中只需要进行10几次比较就能查找到目标时，不禁感叹编程之魅力！人类之伟大呀！ —— 学红黑树有感。

红黑树定义和性质

红黑树是一种含有红黑节点并能自平衡的二叉查找树。它必须满足下面性质：

1.节点是红色或黑色。
2.根是黑色。
3.所有叶子都是黑色（叶子是NIL节点或NULL）。
4.每个红色节点必须有两个黑色的子节点。（从每个叶子到根的所有路径上不能有两个连续的红色节点。）
5.从任一节点到其每个叶子的所有简单路径(一个没有重复顶点的道路称为简单道路,注意树是有方向的哦不能反着走)都包含相同数目的黑色节点。
从性质5又可以推出：
性质5.1：如果一个节点是黑色节点（除开叶子），那么该节点肯定有两个子节点

典型的用途是实现 -关联数组- 它可以在 O(log n)时间内完成查找，插入和删除，这里的 n是树中元素的数目。
下面是一个具体的红黑树的图例：

我们使用nil叶子或空（null）叶子，如上图所示，它不包含数据而只充当树在此结束的指示。这些节点在绘图中经常被省略，导致了这些树好像同上述原则相矛盾，而实际上不是这样的。

红黑树插入操作

在红黑树上进行插入操作和删除操作会导致不再符合红黑树的性质。恢复红黑树的性质需要少量O(log n)的颜色变更（实际是非常快速的）和不超过三次树旋转（对于插入操作是两次）。虽然插入和删除很复杂，但操作时间仍可以保持为 O(log n)。

插入操作包括两部分工作

一.查找插入的位置（这个没啥说的，和二叉查找树的查找一样）
二.插入后自平衡。

插入节点是应该是什么颜色呢？
答案是 $\color{red}{红色}$ 。理由:
如果设为黑色，就会导致根到叶子的路径上有一条路上，多一个额外的黑节点，这个是很难调整的。但是设为红色节点后，可能会导致出现两个连续红色节点的冲突，那么可以通过颜色调换和树旋转来调整

所有插入情景如图所示。

说明约定
I表示插入节点，P表示插入节点的父节点，S表示插入节点的叔叔节点，PP表示插入节点的祖父节点。

详细介绍情景4的情况

如果插入的父节点为红节点，那么该父节点不可能为根节点，所以插入节点总是存在黑色祖父节点

插入情景4.1：叔叔节点存在并且为红节点

可以看到，我们把PP节点设为红色了，如果PP的父节点是黑色，那么无需再做任何处理；但如果PP的父节点是红色，根据性质4，此时红黑树已不平衡了，所以还需要把PP当作新的插入节点，继续做插入操作自平衡处理，直到平衡为止。

如果PP刚好为根节点时，那么根据性质2，我们必须把PP重新设为黑色，那么树的红黑结构变为：黑黑红(这是可以的哦)。换句话说，从根节点到叶子节点的路径中，黑色节点增加了。这也是唯一一种会增加红黑树黑色节点层数的插入情景。

插入情景4.2.1：叔叔节点不存在或为黑节点，并且插入节点的父亲节点是祖父节点的左子节点,且插入节点是父节点的左子节点

插入情景4.2.2：叔叔节点不存在或为黑节点，并且插入节点的父亲节点是祖父节点的左子节点，且插入节点是其父节点的右子节点

插入情景4.3：叔叔节点不存在或为黑节点，并且插入节点的父亲节点是祖父节点的右子节点

插入情景4.3.2：插入节点是其父节点的右子节点

红黑树删除操作

红黑树的删除操作也包括两部分工作

一.查找目标节点
二.删除后自平衡

删除了节点后我们还需要找节点来替代删除节点的位置，不然子树跟父辈节点断开了，除非删除节点刚好没子节点，那么就不需要替代。

二叉树删除节点找替代节点有3种情情景：

情景1：若删除节点无子节点，直接删除
情景2：若删除节点只有一个子节点，用子节点替换删除节点
情景3：若删除节点有两个子节点，用后继节点（大于删除节点的最小节点）替换删除节点

补充说明下，情景3的后继节点是大于删除节点的最小节点，也是删除节点的右子树种最左节点。那么可以拿前继节点（删除节点的左子树最左节点）替代吗？可以的。但习惯上大多都是拿后继节点来替代，后文的讲解也是用后继节点来替代。一种找前继和后继节点的直观的方法：把二叉树所有节点投射在X轴上，所有节点都是从左到右排好序的，所有目标节点的前后节点就是对应前继和后继节点。如图所示。

M的前继是K,后继是P

删除节点被替代后，在不考虑节点的键值的情况下，对于树来说，可以认为删除的是替代节点！

基于此，上面所说的3种二叉树的删除情景可以相互转换并且最终都是转换为情景1

情景2：删除节点用其唯一的子节点替换，子节点替换为删除节点后，可以认为删除的是子节点
若子节点又有两个子节点，那么相当于转换为情景3(现在去看情景3)，一直自顶向下转换，总是能转换为情景1。
情景3：删除节点相当于删除后继节点（这个后继节点肯定不存在左节点，因为后继的定义是值最小），如果后继节点有右子节点，那么相当于转换为情景2，否则转为为情景1。

删除节点情景关系图

删除操作的所有情景

说明约定
R表示替代节点，P表示替代节点的父节点，S表示替代节点的兄弟节点，SL表示兄弟节点的左子节点，SR表示兄弟节点的右子节点。灰色节点表示它可以是红色也可以是黑色。

值得特别提醒的是，R是即将被替换到删除节点的位置的替代节点，在删除前，它还在原来所在位置参与树的子平衡，平衡后再替换到删除节点的位置，才算删除完成。

删除情景1：替换节点是红色节点
我们把替换节点换到了删除节点的位置时，由于替换节点时红色，在原位置删除也了不会影响红黑树的平衡，只要把替换节点的颜色设为删除的节点的颜色即可重新平衡。
删除情景2：替换节点是黑节点
当替换节点是黑色时，我们就不得不进行自平衡处理了。我们必须还得考虑替换节点是其父节点的左子节点还是右子节点，来做不同的旋转操作，使树重新平衡。
情景2有以下多种情况
㈠ $\color{red}{2.1}$ 替换节点(黑)是其父节点的左子节点
$\color{red}{2.1.1}$ 替换节点(黑)是其父节点的左子节点且替换节点的兄弟节点是红节点
若兄弟节点是红节点，那么根据性质4（每个红色节点必须有两个黑色的子节点），兄弟节点的父节点和子节点肯定为黑色

上图得到删除情景2.1.2.3（后面会说明。这里先记住，此时R仍然是替代节点，它的新的兄弟节点SL和兄弟节点的子节点都是黑色）。
$\color{red}{2.1.2}$ 替换节点(黑)是其父节点的左子节点且替换节点的兄弟节点是黑节点：
当兄弟节点为黑时，其父节点和子节点的具体颜色也无法确定
$\color{red}{2.1.2.1}$ 节点(黑)是其父节点的左子节点且替换节点的兄弟节点的右子节点是红节点，左子节点任意颜色
即将删除的左子树的一个黑色节点（因为替换节点是黑色的），显然左子树的黑色节点少1了，然而右子树又有红色节点，那么我们直接向右子树“借”个红节点来补充黑节点就好啦，此时肯定需要用旋转处理了。
灰色表示颜色不确定
上图需要说明的是:平衡后的图怎么不满足红黑树的性质？前文提醒过，R是即将替换的，它还参与树的自平衡，平衡后再替换到删除节点的位置，所以R最终可以看作是删除的
$\color{red}{2.1.2.2}$ 替换节点(黑)是其父节点的左子节点且替换节点的兄弟节点的右子节点为黑节点，左子节点为红节点
兄弟节点所在的子树有红节点，我们总是可以向兄弟子树借个红节点过来，显然该情景可以转换为情景2.1.2.1

$\color{red}{2.1.2.3}$ 替换节点(黑)是其父节点的左子节点且替换节点的兄弟节点的子节点都为黑节点
此次兄弟子树都没红节点“借”了，兄弟帮忙不了，找父母呗!
这种情景我们把替换节点的兄弟节点设为红色，再把父节点当作替代节点，自底向上处理，去找父节点的兄弟节点去“借”。但为什么需要把兄弟节点设为红色呢？显然是为了在P所在的子树中保证平衡（R即将删除，少了一个黑色节点，子树也需要少一个）