红黑树（）：-EW帮帮网

1. 红黑树：

红黑树从根节点开始的最长的路径不会超过最短路径的2倍。

红黑树的话，他的结点的分布没有我们的AVL树的结点的分布均衡，但是效率也不错，AVL树的结点分布的那么均匀，其实也是在进行了旋转，付出了代价换来的绝对的均衡。

那么红黑树的“红黑树从根节点开始的最长的路径不会超过最短路径的2倍”是怎么被维持的呢？

这两个是我们的红黑树，第一个红黑树的左边全黑的路径就是最短路径，右边一黑一红的是最长的路径，最长路径<=最短路径的2倍；

那我们来数一下我们的这两个红黑树的路径有多少跳呢？

我们的第一个红黑树的路径有8条，第二个有10条。（我们数路径一定要数到空结点，我们的第一个二叉树的10结点下面还有两个空的结点）

这个二叉树不是我们的红黑树，他的最短的路径是最左边的，只有一个黑节点，但是我们的右边的最长的路径有两个黑节点，这就不符合我们的红黑树的规则。

最短和最长路径：

在我们的红黑树里面，全黑的那条路径就是最短的路径，一红一黑的路径是最长的路径；

红黑树没有AVL树那样的绝对的平衡，但是效率也不错，红黑树的旋转次数更少；

2. 红黑树的插入：

我们给红黑树里面插入新节点的时候，我们可以是插入黑色结点，也可以是插入红色结点，但是如果插入黑色结点的话，这个黑色结点影响了这条路径的黑色结点的数量，我们的每条路径的黑色结点的数量可能都会发生变化来保持他们每条路径的黑色结点的数量的相等，这个是很难控制的。

所以我们必须要插入红色结点，当然，如果这个树连根都没有的话，根节点要求是黑结点，我们就插入一个黑结点。

uncle结点的情况的划分：

插入红结点，我们的叔叔结点分为三种情况，我们先看第三种情况：uncle结点存在且为红：

uncle结点存在且为红：

看这个图片，当我们给parent结点的下面插入一个红结点的时候，这时候我们的parent结点和cur结点都是我们的红色的结点，（因为我们的红黑树的规则说明，我们是不能有两个红色结点同时在的）。

常规的处理办法：（变色）

这时候我们看我们的uncle结点，uncle结点是红色结点，这时候我们就把parent结点和uncle结点都变成黑色结点，然后把grandparent结点变成红色结点。（这个就是我们一般变色的方法）。

这时候我们看我们的圈出来的部分就变正常了，然后每条路径的黑色结点的数量也是一样的。但是出现了新的问题，那就是我们的红黑树又出现了两个红色结点连接的情况。

这时候我们就再来一次我们刚才的操作，我们把之前的grandparent结点看成我们的新的cur结点，然后找到新的parent，uncle，grandparent结点。

这时候我们重复刚才的操作，我们看我们的uncle结点，这个时候的话，我们的uncle结点就来到了我们的第二种情况，那就是我们的uncle结点存在且为黑色节点。

我们的第二种的uncle结点存在且为黑色结点的这种情况的话，他只会出现在我们的下面的子树的根节点由黑色变成红色上来的，不然的话，直接插入红色结点的话，uncle结点是不可能为黑色的，不然不符合红黑树的规定。

就好比这种情况，我们给插入一个红色结点后，红色结点cur的叔叔结点uncle直接就是黑色结点，这种情况要是有的话，说明这个红黑树还没有插入结点的时候，这就是一个错误的红黑树。

这种情况只会是我们变了一层以后，继续的往上面去找，然后再往上层的uncle可能会有的情况；

我们往回来看：

uncle结点存在且为黑：

我们现在的叔叔uncle结点现在是黑色结点，这时候我们的刚才的常规的处理的方法就不行了，但是我们还是要想办法来处理他，因为他的最长了路径已经超过了我们的最短路径的长度了。

这时候我们的刚才的常规的变色的处理方法已经不够用了，我们这时候就要使用旋转来解决了。

旋转的话，我们分为单旋和双旋，我们看情况使用这两个旋转方式。

旋转：

//这个是我们的单旋：

我们看这个，这时候我们的uncle结点为黑色结点，我们的两个红色结点相连接，左边的结点比较冗余，我们就进行一个右单旋，parent结点作为我们的根节点，然后grandparent结点变成红色结点作为我们的parent结点的右孩子结点。

//核心是旋转完后我们把parent结点的颜色变成黑色，然后把grandparent结点的颜色变成红色。

下面的是我们的双旋：

旋转的话，我们已经比较熟悉了，我们看上面的，我们要把cur结点作为我们的最上面的结点，我们把cur的左孩子作为parent的右孩子，然后把cur的右孩子变成grandparent的左孩子。

旋转结束以后，我们的cur结点就变成了我们的这颗树的根，这个节点有可能是我们的整棵树的根节点，也有可能只是一个子树的根，但是不管怎样，我们都把cur结点的colour置为BLACK。

然后把grandparent的colour置为RED。

uncle结点不存在：

当我们的uncle结点不存在的话，我们的cur结点一定是新增的，不可能是由下面的黑结点演变过来的，因为当我们的uncle结点不存在的时候，我们的parent这边的话，他是不能有黑色结点的，所以不可能是演变来的。

这种情况的话，我们是一定要想办法处理掉的，因为后面的路径有两个红结点是相连的，并且的这条路径已经超过了我们的最短路径的长度。

这时候我们的变色就解决不了这个问题了，我们就要使用旋转来解决；

这个是我们的单旋：

比如上面的这个，我们就使用一个右单旋就可以解决，然后把我们的parent结点变成黑色结点，然后grandparent结点变成红色结点，parent有可能是整颗红黑树的根，也有可能只是一颗普通红黑树的子树的根，但是最后我们都要把它置为黑节点。

下面的是我们的双旋：

这个红黑树没有uncle结点，然后他是左边高的右边高，我们就要使用一个双旋来解决，使用一个左右双旋来解决。（我们之前学习的双旋，我们可以灵巧的记忆一下，我们的cur结点要做到我们的最高的结点，然后cur结点的左孩子给parent的右孩子，cur结点的右孩子做成我们的grandparent的左孩子）。