红黑树的本质就是一棵二叉查找树，所以先从二叉查找树来了解起。
二叉查找树
二叉查找树又称有序二叉树，具有以下特性：
- 若节点的左子树不为空，则左子树上的所有节点的值都小于它根节点的值。
- 若节点的右子树不为空，则右子树上的所有节点的值都大于它根节点的值。
- 任意节点的左、右子树同样为二叉查找树。
- 没有键值相等的节点。
一般情况下，二叉查找树的操作执行时间为O(lgn)，但是，在二叉查找树中为有序的数据后，例如递增的全在右子树上，递减的都在左子树上，就会退化成一个具有n个节点的线性链，运行时间就会变成O(n)。红黑树的出现就会使树变的相对平衡，使之时间复杂度稳定在O(lgn)。
红黑树
红黑树的特性：
- 每个节点要么是红色要么就是黑色
- 根节点为黑色
- 每个叶子节点是黑色的（叶节点值树尾端NIL指针或者NULL节点）
- 如果一个节点为红色，那么它的两个儿子节点为黑色
- 对于任意节点，它到树尾端的NIL指针的每一条路径包含的黑色节点数目相同
红黑树图片.png
树的旋转
在红黑树进行基本的插入删除操作时，会对树进行修改，此时就需要对树进行平衡化操作使其满足平衡化。二叉树的旋转就可以保持红黑树的性质，旋转分为左旋转和右旋转。（为了更好演示，我在网上找了动图演示）
左旋转
左旋转.png
动画效果如下所示：
左旋.gif
右旋转
右旋.png
动画效果如下所示：
右旋.gif
红黑树的插入修复
插入修复的三种情况：
- 当前节点的父节点是红色且祖父节点的另一个子节点（叔叔节点）也是红色
- 当前节点的父亲节点是红色，叔叔节点是黑色，当前节点是其父节点的右子节点
- 当前节点的父亲节点是红色，叔叔节点是黑色，当前节点是其父节点的左子节点
接下来对三种情况进行分析：
情况一：
当前节点的父节点是红色且祖父节点的另一个子节点（叔叔节点）也是红色
p1.png
解决方法：将当前节点的父节点和叔叔节点变为黑色，祖父节点变为红色，把当前节点指向祖父节点，变为如下图样子，从新的当前节点开始算法。
2.png
如图修复情况一后的图示又变成了情况二，接下来解决情况二。
情况二：
当前节点的父节点是红色，叔叔节点为黑色，且本身为其父节点的右子节点
2.png
解决办法：将当前节点的父节点作为新的当前节点，以新的当前节点为支点左旋
3.png
如图修复情况二后的图示又变成了情况三，接下来解决情况三。
情况三：
当前节点的父节点是红色，叔叔节点为黑色，且本身为其父节点的左子节点
3.png
解决办法：父节点变为黑色，祖父节点变为红色，在祖父节点为支点右旋
4.png
红黑树的删除
红黑树的删除节点跟二叉查找树的删除节点一样，二叉查找树的节点删除几种情况如下：
二叉查找树的删除：
- 没有儿子，即为叶子节点，直接把父节点对应的儿子指针设为NULL，删除儿子节点
- 只有一个儿子，那么把父亲节点的相应的儿子指针指向这个儿子节点的独生子节点，删除儿子节点
- 有两个儿子，为了满足二叉查找树的结构不变，即左子树节点小于根节点，右子树节点大于根节点。我们可以找出左儿子中最大的元素节点或者右儿子中的最小的元素节点替代要删除的节点位置，然后删除节点。习惯性找左儿子中最大的元素节点，顺着左儿子不断搜索其右子树，找到最后一个没有右子树的节点就是最大的。
红黑树的删除修复：
删除后的四种修复情况：
- 当前节点是黑色，兄弟节点为红色，此时父节点和兄弟节点的子节点都为黑色
- 当前节点是黑色，兄弟节点为黑色，兄弟节点的两个子节点全为黑色
- 当前节点是黑色，兄弟节点是黑色，兄弟的左子是红色，右子是黑色
- 当前节点是黑色，兄弟节点是黑色，兄弟的右子是红色，左子任意色
接下来对上面四种情况进行分析：
情况一：
当前节点是黑色，兄弟节点为红色，此时父节点和兄弟节点的子节点都为黑色
d1.jpg
解决方法：父节点变红，兄弟节点变黑，以父节点左旋
d2.jpg
情况二：
当前节点是黑色，兄弟节点为黑色，兄弟节点的两个子节点全为黑色
d3.jpg
解决方法:奖父节点变为当前节点，兄弟节点变红，重新进入算法
d4.jpg
情况三：
当前节点是黑色，兄弟节点是黑色，兄弟的左子是红色，右子是黑色
d5.jpg
解决方法：把兄弟结点染红，兄弟左子结点染黑，之后再在兄弟结点为支点解右旋，之后重新进入算法，此是把当前的情况转化为情况4
d6.jpg
情况四：
当前节点是黑色，兄弟节点是黑色，兄弟的右子是红色，左子任意色
d7.jpg
解决方法：把兄弟结点染成当前结点父结点的颜色，把当前结点父结点染成黑色，兄弟结点右子染成黑色，之后以当前结点的父结点为支点进行左旋
d8.jpg
本文参考July大神的红黑树分析
网友评论