前言
红黑树（Red Black Tree） 是一种自平衡二叉查找树，是在计算机科学中用到的一种数据结构，典型的用途是实现关联数组。红黑树和AVL树类似，都是在进行插入和删除操作时通过特定操作保持二叉查找树的平衡，从而获得较高的查找性能。它虽然是复杂的，但它的最坏情况运行时间也是非常良好的，并且在实践中是高效的： 它可以在O(log n)时间内做查找，插入和删除，这里的n 是树中元素的数目。第一次接触到红黑树是在上数据结构相关课程的时候，但是当时的理解比较片面，当后面看到HashMap源码实现的时候，其中也用到了红黑树的数据结构。至此，打算把红黑树整理一下。
一、二叉查找树
红黑树是一种特殊的二叉查找树，二叉查找树是一种比较简单数据结构，就简单的回顾一下。
1.二叉查找树的特征
- 左子树上所有结点的值均小于或等于它的根结点的值。
- 右子树上所有结点的值均大于或等于它的根结点的值。
- 左、右子树也分别为二叉排序树。
比如说这样的一棵树就叫做二叉查找树（二叉排序树）
2.二叉查找树的不足
一般的二叉查找树的查找是和二分查找类似的，所以查找的时间复杂度为O(log n)，最坏时间复杂度为O(n)，因为一般的二叉查找树没有做平衡，很容易产生插入的节点在一边的不平衡情况发生，这样会对查找的效率带来很大的影响。比如说有这么一颗二叉查找树
此时，插入5个点:3、4、5、6、7
此时就造成了这种线性的状态，查找的效率和遍历几乎没有区别。这时候为了解决这个问题，就提出了平衡二叉查找树的概念，也就是红黑树。
二、红黑树
1.红黑树的性质与定义
- 性质1：每个节点要么是黑色，要么是红色。
- 性质2：根节点是黑色。
- 性质3：每个叶子节点（NIL）是黑色。
- 性质4：每个红色结点的两个子结点一定都是黑色。
- 性质5：任意一结点到其每个叶子结点的路径都包含数量相同的黑结点。
比如说以下这颗二叉树就是红黑树，它除了满足二叉查找树的条件之外，还满足其他的一些条件。
2.红黑树自平衡的三种方式
红黑树有三种自平衡的方式，分别是：左旋、右旋、变色
左旋：以某个结点作为支点(旋转结点)，其右子结点变为旋转结点的父结点，右子结点的左子结点变为旋转结点的右子结点，左子结点保持不变。如下图。
右旋：以某个结点作为支点(旋转结点)，其左子结点变为旋转结点的父结点，左子结点的右子结点变为旋转结点的左子结点，右子结点保持不变。如下图。
变色：节点的颜色由红变黑或者由黑变红。
总结：可以这么理解，左旋的话是将右子树的节点拿到左子树，右旋的话是将左子树的节点拿到右子树。
3.红黑树的查找
红黑树的查找和二叉查找树基本类似，所以它的时间复杂度为O(log n)，由于红黑树是平衡二叉查找树，所以它的最坏时间复杂度为O(2log n)。
4.红黑树的插入
红黑树的插入和二叉查找树的插入差不多，通过类似于二分查找的方式找到插入的位置。但是在红黑树插入新节点之后需要做一些操作，来保持红黑树性质不被破坏，插入节点的颜色应该为红色。下面考虑几种红黑树插入的场景。
场景一：红黑树为空树
这是最简单的场景，只需要把插入节点作为根节点即可，但是由于红黑树的性质决定了根节点的颜色要为黑色，所以插入节点变色为黑色。
场景二：插入节点的key值已经存在
就像在HashMap中一样，插入节点的key已经存在了，只需要找到这个节点并更新节点的value即可。找到这个节点，将待插入节点的颜色设置和这个节点的颜色一致，再把节点的值进行更新，替换点原来的点。这就相当于完成了插入。
场景三：插入节点的父节点为黑色节点
当插入节点的父节点为黑节点不会违反红黑树的任何性质，直接插入即可，不需要做自平衡操作。
场景四：插入节点的父节点为红色节点，叔叔结点存在并且为红结点
从红黑树的性质可以知道，如果父节点为红色节点，那么祖父节点必然是黑节点，因为连续两个节点的颜色是红色的情况是不存在的。那么现在这颗树的情况是黑红红，因为插入的点颜色红色，所以最简单的一种方法是将黑红红改为红黑黑。所以处理总共分为三步，以下图为例
所以我们将pp节点设置为了红色，此时要考虑这几种情况：1.当pp节点的父节点为黑色，则不需要任何操作。2.如果pp节点的父节点为红色，则把pp节点当做新插入的节点，继续往上层做平衡操作。3.当pp节点已经是根节点的情况，则需要把pp节点再次变为黑色。如下图
插入一个节点后
也就是说，红黑树的更新可以看成是从底向上的更新。这个插入场景是所有插入场景中唯一一个能增加黑色节点数量的插入操作。
场景五：插入节点的父节点为红色节点，叔叔结点不存在。其中父节点为祖父节点的左节点还是右节点可以分如下情况。
- 父节点为祖父节点的左节点，插入节点是其父节点的左子节点
因为两个都是红色节点，所以并不会破坏平衡。其实还有另外一种做法就是将I节点和pp节点都变为黑色，P节点变为红色，但是这样的话还需要继续做平衡操作，因为我们不知道P节点的父节点是什么颜色，若其为红色，则还需要进一步平衡操作，若其为黑色，则不需要继续平衡。所以第一种方法是比较简单的方法。
- 父节点为祖父节点的右节点，插入节点是其父节点的右子节点
和上述操作相同，只要把右旋改为左旋即可。
场景六：插入节点的父节点为红色节点，叔叔结点不存在。其中父节点为祖父节点的左节点还是右节点可以分如下情况。
- 父节点为祖父节点的左节点，插入节点是其父节点的右子节点
注意这种情况要做两次的旋转。
- 父节点为祖父节点的右节点，插入节点是其父节点的左子节点
同样的，仍然需要做两次的旋转。
5.红黑树的删除
红黑树的删除操作主要有以下三种：
- 若删除结点无子结点，直接删除
- 若删除结点只有一个子结点，用子结点替换删除结点
- 若删除结点有两个子结点，用后继结点（大于删除结点的最小结点）或者前驱也行，替换删除结点
下面就分成几种情况来讨论一下
5.1要删除的节点为红色节点
情况一：删除的是红色的叶子节点
处理方式是直接删除即可，后续不影响红黑树的平衡。
情况二：删除的是红色的非叶子节点
这种情况下只可能存在红色节点的左右子树都存在的情况，并且左右孩子都是黑色节点，否则违反红黑树的性质。这种情况，需要找到删除节点的后继，用它替代掉要删除的节点，最后就转化为情况一，直接删除掉这个替代节点即可。
比如说这边要删除掉5这个节点
这边替代的节点可以选择它的前驱节点4，用4把5替代掉，最后删除4即可达到平衡。
5.2要删除的节点是黑色节点
5.2.1 删除黑色的叶子节点
情况一：待删除节点D的兄弟节点S为红色，D是左节点的情况。
做法是将父亲节点和兄弟节点的颜色互换，也就是p变成红色，S变成黑色，然后将P树进行左旋操作，结果如下图，这时候，D的兄弟节点变成了黑色，这样就成后面要讨论的情况。
情况二：与情况一类似的，待删除节点D的兄弟节点S为红色，D是右节点的情况。
类似的，将P与S互换颜色，并且右旋树。也变成了后面要讨论的操作。
情况三：兄弟节点为黑色，且远侄子节点为红色。D为左孩子对的情况，这时D的远侄子节点为S的右孩子。
从图上可以看到，删除了D节点之后，左边的黑色节点就少了一个，这样明显是不平衡的，这时候应该通过旋转操作来平衡左边的黑色节点。所以调整过程为，将P和S的颜色对调，然后对P树进行类似AVL树左旋的操作，最后把SR节点变成黑色，并删除D即可。SL节点只能为红色或者是NIL。
情况四：类似于情况三，兄弟节点为黑色，且远侄子节点为红色，D为右孩子的情况，此时D的远侄子为S的左孩子。
经过旋转和变色之后
情况五：兄弟节点S为黑色，远侄子节点为黑色，近侄子节点为红色，D为左孩子的情况，此时近侄子节点为S的左孩子
做法是，将SL右旋，并将S和SL的颜色互换，这个时候就变成了情况3。
相同的，当D在右边，和上述情况类似。
情况六：父亲节p为红色，兄弟节点和兄弟节点的两个孩子（只能是NULL节点）都为黑色的情况。
这种情况下删除D节点，左边的黑色节点数量就少了，那就把P变为黑色，但是P变为黑色以后，右边也会多一个黑色节点，再把右边的S变为红色即可。
情况七：父亲节点p，兄弟节点s和兄弟节点的两个孩子（只能为NULL节点）都为黑色的情况
删除了D节点，为了P到左右两边叶子节点的黑色节点数相同，把S变为红色节点即可。但是需要考虑到的一种情况是P不是根节点，此时经过P的黑色节点数量就少了一个，再继续向上层平衡调整即可。
5.2.2删除黑色的非叶子节点
情况一：删除的黑色节点左右子树都存在
首先找到被删除元素D的直接后继，用直接后继的值替换D的值，再对直接后继进行删除。我们可以知道，直接后继是不可能左右子树都存在的，这样就可以将左右子树都存在的情况转化为下面的情况。
情况二：删除的黑色节点仅有左子树或者仅有右子树。
即用D的左孩子或者右孩子替换D，并DR的颜色改成黑色即可。如下图：
最后，推荐一个工具，一些操作不清楚的可以用这个工具进行模拟。
三、总结
平衡二叉树和红黑树有什么区别呢？
虽然平衡树解决了二叉查找树退化为近似链表的缺点，能够把查找时间控制在 O(logn)，不过却不是最佳的，因为平衡树要求每个节点的左子树和右子树的高度差至多等于1，这个要求实在是太严了，导致每次进行插入/删除节点的时候，几乎都会破坏平衡树的第二个规则，进而我们都需要通过左旋和右旋来进行调整，使之再次成为一颗符合要求的平衡树。
显然，如果在那种插入、删除很频繁的场景中，平衡树需要频繁着进行调整，这会使平衡树的性能大打折扣，为了解决这个问题，于是有了红黑树。
一句话总结来说，如果插入删除不频繁，只是对查找要求较高，那么AVL是较优于红黑树的。如果插入删除较为频繁，红黑树维持平衡的代价要远小于AVL树，红黑树具有优势。
参考
https://segmentfault.com/a/1190000012728513?utm_source=tag-newest#articleHeader5