肝了几天我算是理解了红黑树

1.二叉排序树

在学习红黑树之前我们需要了解一下二叉排序树，所谓二叉排序树就是一种特殊的二叉树，首先满足二叉树的性质，然后它存储数据的方式是左边节点比父节点的数据小，而右边节点比父节点数据大。这样当我们查询一个数据时，比如我们要找数据8，先从根节点开始，8比12小所以去左子树找，然后与5比较发现比5大那么去右子节点此时就找到了我们需要的数据8。是不是类似于二分查找呢？只需要O(logn)就能找到数据。

二叉搜索树（二叉排序树，二叉树查找树），他的时间复杂度取决于树的高度，理想情况下为O(logn)，但是某些情况下会退化为O(n)，比如我们插入的数据为10,9,8,7,6或者是1,2,3,4,5这种情况下二叉排序树将会退化为斜树，相当于一个链表，此时查询的时间复杂度就会变为O(n)，如下图所示。

2.红黑树

通过上面的例子我们可以看到即便是二叉排序树十分的优秀，但是在某些情况下二叉排序树的效率会大打折扣，针对这种情况科学家们衍生除了红黑树，只要能满足以下性质就能让二叉排序树到达自平衡。

性质1：每个节点要么是黑色，要么是红色。

性质2：根节点是黑色。

性质3：每个叶子节点（NIL）是黑色。

性质4：相邻节点不能同时为红色，此处的相邻是指父节点和左右任意一个子节点不能同时为红色，从而可以推出性质5

性质5：每个红色节点的两个子节点一定都是黑色。

ps:红黑树是一个黑色平衡的树，但是却不是一个完美平衡的二叉排序树，所谓的完美平衡二叉树就是指平衡因子的绝对值小于等于1，而所谓的平衡因子指的是该节点的左子树层数减去右子树层数的绝对值。黑色平衡是当我们将红黑树中的红色节点全部删除时，此时你会发现都平衡因子为小于1的。红色节点删除之后，有些节点就没有父节点了，它们会直接拿这些节点的祖父节点（父节点的父节点）作为父节点。所以，之前的二叉树就变成了四叉树。

3.红黑树的插入

由于场景1、2、3都比较简单，所以就就没有细讲，可以对照着上图的思维导图进行了解，下面主要介绍的是场景4的，场景4都涉及到左旋，右旋以及变色的处理；首先我们要知道红黑树在插入节点时默认插入的节点为红色，这是因为如果我们默认插入为黑色，那么就会导致不满足性质5，也就是任意节点到每个叶子节点经历的黑色节点一致。

插入场景4.1

插入节点的父为红色且叔叔节点存在，并且叔叔为红色节点。

处理：我们只需要将父节点和叔叔节点变为黑色，同时祖父节点变为红色，如果将祖父节点变为红色后，此时可能出现祖父节点和自己的父节点又不平衡，所以我们还需要继续调整。

注意: 如果祖父节点为根节点，此时不需要改变为红色，如果改变那么就不满足红黑树的性质。

插入场景4.2.1

插入节点的父为红色，且插入节点的叔叔节点不存在或为叶子节点（NIL）时，且插入节点为父节点的左子树，插入节点的父节点为祖父节点的左子树。

处理：将插入节点的父改为黑色，同时祖父节点改为红色，然后对父节点进行右旋，那么我们可不可把父节点变为红色，插入节点和祖父节点变为黑色，然后对父节点进行旋转，实际上是可以的，但是由于把父变为了红色，那么又会导致上面的节点可能和红色发成冲突，那样又要自底向上进行调整。

插入场景4.2.2

插入节点的父为红色，且插入节点的叔叔节点不存在或为叶子节点（NIL）时，且插入节点为父节点的右子树，插入节点的父节点为祖父节点的左子树。

处理：首先插入节点为父节点的右子树时，我们可以得出插入的节点肯定是比父节点大的，实际上我们可以进行转换，将插入节点的父节点变为插入节点的左子树，然后我们可以得到4.2.1的场景，然后也就是可以直接再把插入节点变为黑色，然后左子树和父变为红色进行右旋。

插入场景4.3.1

插入节点的父节点为红色，且叔叔节点不存在或者叔叔节点为叶子节点（NIL），且插入节点是父节点的右子树，父节点是祖父节点的右子树。

处理：将父节点设置为黑色，祖父节点和插入节点设置为红色，然后进行左旋。

插入场景4.3.2

插入节点的父节点为红色，且叔叔节点不存在或者叔叔节点为叶子节点（NIL），且插入节点是父节点的左子树，父节点是祖父节点的右子树。

处理：首先当我们插入的节点在父节点的右边时，我们可以得知父节点大于插入节点，那么我们可以将父节点变为插入节点的右子树，然后此时插入节点就变成了原来父节点的父节点，也就得到了4.3.1的场景，此时只需要将插入节点变为黑色，右子树变为红色，插入节点的父节点变为红色，再进行左旋。

4.红黑树的删除

红黑树的插入相对而言比删除操作要简单，真正难的是红黑树的删除操作，因为涉及到查找到节点，然后要找到删除后的位置有人来替代，以及替代后的调整。首先我们来看看二叉树的删除，二叉树的删除分为三种情况。

1.删除的节点没有子节点，直接删除。

2.删除的节点只有一个子节点，将删除节点的子节点替换成删除节点，此时因为我们替换掉了删除的节点，相当于覆盖了，那么直接再删除掉我们刚刚移动的节点的多余节点，这里不太好理解，可以参考下面的图1所示，图中为删除7节点时

3.删除的节点有左右子树，找到删除节点的后继，然后将后继替换为删除节点，再删除需要删除的节点，这里的后继就是指删除节点右子树中最小的叶子节点值，当然我们也可以用左子树中最大的叶子节点值。可以参考如下图2所示，图中为删除5节点时。

基于上述的删除特点有可以我们将二叉树转换为如下场景

当为场景2的时候，也就是删除节点只有一个子节点时，将删除节点替换为子节点，然后此时我们要删除的就是替换后的子节点，此时子节点还有左右子节点，那么我们又可以转换为场景3的情况，如果只有一个节点相当于有是场景2的情况，然后一直自顶向下进行处理

当为场景3的时候，也就是删除节点有左右子节点时，找到删除节点的后继，然后替换掉要删除的节点，然后再删除替换后重复的那个节点，但是如果重复的那个节点又存在右子节点，我们相当于又转换成了场景2或者场景1的情况；需要注意的是重复节点是肯定没有左子节点的，只有右子节点，因为我们找的是后继。

下面我们就来看看红黑树删除时的10种情况，如下图所示。

删除场景1

需要替换的节点为红色节点

处理：由于我们替换后我们要删除红色节点，但是由于删除红色节点并不会影响平衡，所以可以直接删除，删除前需要将要删除的值和要替换的值进行覆盖，然后把覆盖后的颜色变为要之前的颜色，最后再删除重复的值。下面图中在删除有左右子节点的数据时，实际上找的并不是后继，而是我们前面提到的找左子树中最大的叶子节点，后面涉及两个删除带有左右子树节点情况时，所有动图都是按照这种模式。

删除场景2

删除节点为黑色，且兄弟节点也为黑色节点，父节点为红节点，兄弟节点没有子节点时

处理：将删除节点直接删除，然后父节点与兄弟节点交换颜色。

删除场景3

删除节点为黑色节点，且兄弟节点也为黑色节点，父节点为红色节点，兄弟节点的左子节点为红色节点。

处理：将删除节点删除，然后兄弟节点进行右旋，同时交换兄弟和兄弟节点左子节点的颜色，然后在对父节点进行左旋操作。

删除场景4

删除节点为黑色节点，且兄弟节点也为黑色节点，父节点为红色节点，兄弟节点的右子节点为红色节点。

处理：将删除节点删除，然后对父节点进行左旋操作。

删除场景5

删除节点为黑色节点，且兄弟节点也为黑色节点，父节点为红色节点，兄弟节点的左右子节点都为红色节点。

处理：将删除节点删除，对父节点进行左旋，然后再把父节点的颜色和左右子树的节点颜色进行交换。

删除场景6

删除节点为黑色节点，兄弟节点为红色节点，父节点为黑色节点，兄弟节点的两个子节点为黑色节点。

处理：将删除节点删除，对父节点进行左旋，删除节点的兄弟节点颜色和父节点进行交换，然后再把父节点和兄弟节点的左子节点进行颜色交换。

删除场景7

删除节点为黑色节点，兄弟节点也为黑色节点，父节点为黑色节点，且兄弟节点没有子节点。

处理：将删除节点删除，然后把兄弟节点变为红色。

删除场景8

删除节点为黑色节点，兄弟节点也为黑色节点，父节点为黑色节点，且兄弟节点的子节点包含两个红色节点。

处理：将删除节点删除，对父节点进行左旋，再将兄弟节点右子树变为黑色。

删除场景9

删除节点为黑色节点，兄弟节点也为黑色节点，父节点为黑色节点，且兄弟节点的子节点有一个左红色节点。

处理：将删除节点删除，对兄弟节点进行右旋，同时交换兄弟节点与兄弟节点左子树颜色，然后再进行左旋。左旋后再将兄弟节点变为黑色。

删除场景10

删除节点为黑色节点，兄弟节点也为黑色节点，父节点为黑色节点，且兄弟节点的子节点有一个右红色节点。

处理：将删除节点删除，对父节点进行左旋，然后对兄弟节点的右子节点变为黑色。

最后需要说明一点，上面的删除情况只是针对不需要从下向上继续调整的情况，如果需要从下向上再次调整的第一步肯定不是删除，而是直到调整完毕以后才删除，例如下面这个我们要删除的就是左下角的节点，然后我们调整后并不满足，所以要继续调整自己的父，直到全部调整完毕后才删除。