红黑树原理分析

参考书目: 《算法(第四版)》 Robert Sedgewick

红黑树的起源

红黑树的起源来源于一个叫做 2-3查找树的东西

2-3查找树

2-3 查找树中拥有两种结点，2度结点和3度结点，这两种结点同时构成了2-3查找树，这种查找树具有一定的平衡性

2-3查找树的例子

拿3度结点EJ举例，其中的3度结点的最左的孩子AC表示其下面的结点小于E，H表示在EJ之间，L表示大于J

2-3查找树的构造

向2度结点中插入元素

这种情况比较简单，只需要根据大小关系把原来的2度结点变成三度结点即可

向3度结点中插入元素

向3度结点插入元素的核心就是先将这个元素按照位置大小关系插入到三度结点中去，变成一个4度结点(拥有三个元素，且有四个孩子结点)，然后将4度结点进行分解
那么分解4度结点我分为几步：

1. 将4度结点中间的元素提取出来
2. 将4度结点另外两个结点分离出来作为其孩子

那么就会产生一个问题，如果其父亲是2度结点还比较好，只需要将这个提取出来的元素加入到2度结点中变成一个3度结点

那么如果父亲是三度结点怎么办

这个问题的解决就是向上传递这个分离出来的结点，把他看作一个插入到3度结点的新节点，这个向上传递很重要，是解决问题的关键
那么，如果这个结点是根节点呢，只需要将这个结点的中间元素分离，作为新的根结点，然后使树的高度加一

插入总结

1. 先构造一个临时的4度结点
2. 分解这个四度结点
3. 向上传递分离出来的父节点

2-3查找树和红黑树的关系

如果我们对红黑树的要求改的更加严苛一点，如下：

1. 红结点均为左孩子
2. 没有任何一组父子结点都是红色
3. 任意空结点到根结点路径上的黑结点数量相同

这样约定有一个巧妙之处，就是任意带有红子结点的父亲都可以转化为一个2-3查找树中的3度结点。
例如

这两者之间是有联系的，红黑树的操作基础就建立在这种联系之上

向红黑树中插入一个结点

插入结点主要分为以下几种

向一个黑色结点插入

插入到黑色结点左边

例如我们把0按照二叉排序树的规则插入到1的左边，然后直接将这个结点置为红色，并不用进行其他操作，这是红黑树的操作
按照我刚刚说的，一个黑色结点的红色左子结点相当于这个黑色结点是一个3度结点，那么按照2-3树的插入操作，直接把该2度结点变成一个3度结点即可

插入到黑色结点右边

这种情况下，相当于2-3查找树中，插入一个比父节点大的结点，我们应该向上合并，变成

2-3查找树的情况比较好理解，我们回顾一个红黑树中是怎么做的，因为我们规定了红黑树的黑色结点的右子结点不能为红色，那么理应进行红黑树的旋转，将1左旋（左旋操作的讲解在红黑树博客里），如下所示

这样就和2-3查找树中的情况一致了
但由此我们可以看出，2-3查找树中的3度结点的较大元素在红黑树中是黑色并作为父亲的那个结点

向一个红色结点插入

在红黑树中向红色结点插入分为以下几种情况

插入作为红色结点的左孩子

在红黑树中的处理方式是把3右旋

但是这违反了我们在这里定义的红黑树规则，1的右孩子不能是红色结点，这种情况对应到2-3查找树中如下

这使其变成了一个4度结点，我们应该分解这个4度结点，回到分解4度结点，我们把1提出来加入到其父节点中去

这个操作在红黑树中也有相对应的操作，在上次的博客中仅在插入结点的兄弟结点是红色才进行这种操作，变色操作，这种操作具有向上传递的性质，这种性质和2-3查找树的构造方式是非常相似的，当传递到根节点时结束，根节点根据情况分解

插入作为红色结点的右孩子

这种情况是作为红色结点的左孩子的一种镜像

这种情况下只需要对1进行左旋操作就可以变成插入作为红色结点左孩子的情况

红黑树的删除操作

红黑树的删除操作可以简单地进行概括，删除最小值和删除底部结点

删除最小值

2-3查找树中的删除

在2-3查找树中的删除最小值的一个关键点就是尽量不让被删除结点是一个2度结点，所以为了达成这个目的，我们需要进行一系列操作，此操作可以允许4度结点的存在

左子结点不是2度结点

这种情况不需要操作

父亲是二度结点

1. 如果兄弟是2度结点

   该节点和父亲，兄弟一起合成一个4度结点

   此情况对应的是删除红黑树中的黑色结点且其兄弟也是黑色且无子节点的情况
   
   这种情况下，在红黑树中我们要做的就是删除该结点，假设要删除其父节点然后一直向上传递到根结点。
   在2-3树中，直接删除即可

2. 如果兄弟是3度结点

   和兄弟借一个结点，和父亲进行转换操作，并最终将该结点变成一个3度结点

   此情况对应的是删除红黑树中的黑色结点且其兄弟结点有一个红色子节点
   
   在2-3树中，我们会去和兄弟借一个结点，进行转换，如果进行对比，要达到的效果是比较相似的
   那么如何去借这个结点呢，我们将父亲结点和该结点合成，将兄弟结点的较大值作为其父节点，此时的兄弟结点的情况多样，可能比较灵活，可以按照具体情况进行调整

父亲是三度结点

这种情况的转化过程如下

1. 选取其最近的一个兄弟结点，如果这个兄弟结点是2度结点，直接提取出来，如果是3度结点，提取其最小的元素加入其父亲结点，将父亲结点的最小值提取出来
2. 将这个提取出来的值加入到我们要删除的结点中去，让其变成一个3度结点

这个转化对应红黑树的情况有两种，一个是黑色结点且其兄弟结点有一个红色子节点，另一个是黑色节点的兄弟结点是黑色并无子节点其父亲是红色节点，第二种情况在红黑树中的操作是将父亲和兄弟的颜色进行交换，在我们现在的定义中，还需要对父亲进行一个额外的左旋。

最后，删除要删除的节点

删除树底的元素

进行和删除最小值相同的变换，保证其不是一个2度节点，然后进行删除即可

删除的元素不是叶子

我们将要寻找它的后继，然后进行删除其后继的操作，然后让其后继取代要删除元素的位置
那么，如何找到它要删除的后继，按照二叉排序树的删除有两个孩子的节点的规则，我们要找到大于它的节点中的最小节点，代替它即可
在删除的最后，我们要将原来生成的临时4度节点全部要进行删除