红黑树原理分析（图解）

一.为什么要有红黑树这种数据结构？

   学过二叉查找树的同学都知道，普通的二叉查找树在极端情况下可退化成链表，此时的增删查O(n)效率都会比较低下。为了避免这种情况，就出现了一些自平衡的查找树，比如 AVL。

　ALV树是一种严格按照定义来实现的平衡二叉查找树，所以它查找的效率非常稳定，为O(log n),由于其严格按照左右子树高度差不大于1的规则，插入和删除操作中需要大量且复杂的操作来保持ALV树的平衡（左旋和右旋），因此ALV树适用于大量查询，少量插入和删除的场景中。

  现在假设有这样一种场景：大量查询，插入和删除，使用ALV树就不太合适了，因为ALV树大量的插入和删除会非常耗时间，那么我们是否可以降低ALV树对平衡性的要求从而达到快速的插入和删除呢？

  答案肯定是有的，红黑树这种数据结构就应运而生了（因为ALV树是高度平衡的，所以查找起来肯定比红黑树快，但是红黑树在插入和删除方面的性能就远远不是ALV树所能比的了）。

二.红黑树的性质

 红黑树通过如下的性质定义实现自平衡：

1.节点是红色或黑色。
2.根是黑色。
3.所有叶子都是黑色（叶子是NIL节点）。
4.每个红色节点必须有两个黑色的子节点。（从每个叶子到根的所有路径上不能有两个连续的红色节点。）
5.从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点（简称黑高）。

　有了上面的几个性质作为限制，即可避免二叉查找树退化成单链表的情况。但是，仅仅避免这种情况还不够，这里还要考虑某个节点到其每个叶子节点路径长度的问题。如果某些路径长度过长，那么，在对这些路径上的及诶单进行增删查操作时，效率也会大大降低。这个时候性质4和性质5用途就凸显了，有了这两个性质作为约束，即可保证任意节点到其每个叶子节点路径最长不会超过最短路径的2倍。

　当某条路径最短时，这条路径必然都是由黑色节点构成。当某条路径长度最长时，这条路径必然是由红色和黑色节点相间构成（性质4限定了不能出现两个连续的红色节点）。而性质5又限定了从任一节点到其每个叶子节点的所有路径必须包含相同数量的黑色节点。此时，在路径最长的情况下，路径上红色节点数量 = 黑色节点数量。该路径长度为两倍黑色节点数量，也就是最短路径长度的2倍。举例说明一下，请看下图：

三.红黑树的基本操作之旋转

 旋转操作分为左旋和右旋，左旋是将某个节点旋转为其右孩子的左孩子，而右旋是节点旋转为其左孩子的右孩子。这话听起来有点绕，所以还是请看下图：

上图包含了左旋和右旋的示意图，这里以右旋为例进行说明，右旋节点 M 的步骤如下：

1. 将节点 M 的左孩子引用指向节点 E 的右孩子
2. 将节点 E 的右孩子引用指向节点 M，完成旋转

四.红黑树的基本操作之添加元素

 　红黑树的插入过程和二叉查找树插入过程基本类似，不同的地方在于，红黑树插入新节点后，需要进行调整，以满足红黑树的性质。性质1规定红黑树节点的颜色要么是红色要么是黑色，那么在插入新节点时，这个节点应该是红色还是黑色呢？答案是红色，原因也不难理解。如果插入的节点是黑色，那么这个节点所在路径比其他路径多出一个黑色节点，这个调整起来会比较麻烦（参考红黑树的删除操作，就知道为啥多一个或少一个黑色节点时，调整起来这么麻烦了）。如果插入的节点是红色，此时所有路径上的黑色节点数量不变，仅可能会出现两个连续的红色节点的情况。这种情况下，通过变色和旋转进行调整即可，比之前的简单多了。

　现在我们来分析一下新增的节点（红色）插入之后可能面临的几种情况，以及他们的处理措施：

1.插入的节点为根节点

　新插入的红色节点变成黑色节点，满足根节点为黑色节点的要求

2.父亲节点为黑色节点

　这个时候不需要进行任何调整操作，此时的树仍然是一颗标准的红黑树

3.父亲节点为红色节点的情况下，叔叔节点为红色节点（不用考虑左右）

　解决方案：将叔叔和父亲节点改为黑色，爷爷节点改为红色，然后又将爷爷节点当作插入节点看待，一直进行上面的操作，直到当前节点为根节点，然后将根节点变成黑色

4.父亲节点为红色，叔叔节点为黑色

1）父亲节点为爷爷节点的左孩子，新插入节点为父节点的左孩子（左左）

　解决方案：将父亲节点和爷爷节点颜色互换（父节点变为黑色，爷爷节点变为红色），然后对爷爷节点进行一次右旋

　注：上图叔叔是空叶子节点，所以也是黑色

2）父亲节点为爷爷节点的右孩子，新插入节点为父节点的右孩子（右右）

　解决方案：将父亲节点和爷爷节点颜色互换（父节点变为黑色，爷爷节点变为红色），然后对爷爷节点进行一次左旋

3）父亲节点为爷爷节点的左孩子，新插入节点为父节点的右孩子（左右）

　解决方案：对父亲节点进行一次左旋，然后就变成了情况1，按照情况1再进行处理

4）父亲节点为爷爷节点的右孩子，新插入节点为父节点的左孩子（右左）

　解决方案：对父亲节点进行一次右旋，然后就变成了情况2，按照情况2再进行处理

五.红黑树的基本操作之删除元素

 　相较于插入操作，红黑树的删除操作则要更为复杂一些。删除操作首先要确定待删除节点有几个孩子，如果有两个孩子，不能直接删除该节点。而是要先找到该节点的前驱（该节点左子树中最大的节点）或者后继（该节点右子树中最小的节点），然后将前驱或者后继的值复制到要删除的节点中，最后再将前驱或后继删除。由于前驱和后继至多只有一个孩子节点，这样我们就把原来要删除的节点有两个孩子的问题转化为只有一个孩子节点的问题，问题被简化了一些。

删除一个节点有以下四种情况：

　1.删除的节点没有孩子

　2.删除的节点只有左子树

   3.删除的节点只有右子树

   *4.删除的节点拥有左子树和右子树

　其实只有上面前三种情况，对于第四种情况，可以找到待删除节点的直接后继节点，用这个节点的值替代待删除节点，接着情况转变为删除这个直接后继节点，情况也变为前三种之一。

1.删除的节点只有左子树或只有右子树

     　　或者　　 

　只有上面两种情况会存在于红黑树中，直接用DL/DR的元素值代替D的元素，再把DL/DR直接删去就好。

2.删除的节点没有孩子

1）待删除节点是红色的，直接删去这个节点。

2）父节点P是红色节点

　解决方案：把P节点染成黑色，兄弟节点染成红色，删除节点D。

3）兄弟节点S是红色节点

　　或者　　

　解决方案：把P染成红色，S染成黑色，然后以P为轴做相应的旋转操作（D为P的左子树则左旋，否则右旋），变成了情况2（父节点为红色），按照情况2进行操作。

4）节点D的远亲侄子为红色节点的情况（父节点P可红可黑）

　解决方案：交换P和S的颜色，然后把远亲侄子节点SR/SL设置为黑色，再已P为轴做相应的旋转操作（D为P的左子树则左旋，否则右旋），删除节点D。

5）节点D的近亲侄子为红色节点的情况（父节点P可红可黑）

　解决方案：把S染成红色，把近亲侄子节点SR/SL染成黑色，然后以节点S为轴做相应的旋转操作（D为P的左子树则右旋，否则左旋），变成了情况4，按照情况4进行操作。

6）节点D，P，S均为黑色节点

　解决方案：把D删去，然后把节点S染成红色。

　　①从节点P往上依然是全黑的情况

　　②从节点P往上是其他情况

参考博客1：https://segmentfault.com/a/1190000012728513

参考博客2：https://www.cnblogs.com/yinbiao/p/10732600.html

参考博客3：https://www.cnblogs.com/GNLin0820/p/9668378.html

参考博客4：https://blog.csdn.net/tanrui519521/article/details/80980135