阅读本文的前提
1、知道二叉查找树的概念，插入、删除和查找操作；
2、知道二叉树的左旋和右旋。
3、了解二叉平衡树（AVL树）的概念
红黑树的概念
红黑树是一种自平衡的二叉查找树，查找、插入和删除的平均时间复杂度是O(logN)。红黑树的每个节点都有一个颜色值（红或黑），具有以下性质：
1、每个节点不是黑色就是红色；
2、根节点是黑色；
3、如果一个节点是红色，则该节点的左、右孩子节点必须是黑色；
4、每一个null叶子节点是黑色；
5、从任一个节点到null叶子节点的所有路径上必须包含相同数量的黑色节点。
null叶子节点
在红黑树里，存在两种叶子节点，一种叶子节点是我们常说的叶子节点——左右孩子节点都为null，另外一种是null叶子节点，如下图的红黑树：
blob.jpg
插入操作
红黑树的插入操作分两步：插入、调整。
插入操作和二叉查找树的操作一样，找到合适的位置创建节点插入；
由于插入新节点后，可能会违背红黑树的性质，因此需要做调整处理。
规定插入节点为红色
原因：如果新插入的节点为红色，首先肯定不会违背性质5，方便接下来的调整。
调整规则
定义：
【当前节点】：插入节点
【父亲节点】：【当前节点】的父亲节点
【叔叔节点】：【当前节点】的父亲节点的兄弟节点
【祖父节点】：【当前节点】的父亲节点的父亲节点
注：1、【当前节点】的值可能在调整过程中发生变化，不一定是开始的插入节点，【父亲节点】、【叔叔节点】、【祖父节点】的值依赖于【当前节点】。
2、【叔叔节点】可以是NULL节点
case 1 : 【父亲节点】是黑色
处 理：无须处理
case 2 : 【父亲节点】是红色，【叔叔节点】节点是红色
处 理：【父亲节点】和【叔叔节点】变黑，【祖父节点】变红，将【祖父节点】设为【当前节点】，继续按规则反复调整。
image
case 3 : 【父亲节点】是红色，【叔叔节点】节点是黑色
处 理：这种情况又分4种小情况来处理
3-1-1【父亲节点】是【祖父节点】的左孩子节点，【当前节点】是【父亲节点】的左孩子节点
处 理：【父亲节点】变黑，【祖父节点】变红，以【祖父节点】右旋；
image
3-1-2【父亲节点】是【祖父节点】的左孩子节点，【当前节点】是【父亲节点】的右孩子节点
处 理：以【父亲节点】左旋，变成上述3-1-1情形，旋转后的【父亲节点】设为【当前节点】，继续调整；
image
3-2-1 【父亲节点】是【祖父节点】的右孩子节点、【当前节点】是【父亲节点】的左孩子节点
处 理：以【父亲节点】右旋，变成下述3-2-2情形，旋转后的【父亲节点】设为【当前节点】，继续调整;
image
3-2-2【父亲节点】是【祖父节点】的右孩子节点、【当前节点】是【父亲节点】的右孩子节点
处 理：以【祖父节点】左旋，【祖父节点】变红，【父亲节点】变黑；
image
删除操作
首先要明白二叉查找树的删除规则：
1、删除节点是叶子节点，直接删除；
2、删除节点存在一个非空的子节点，删除节点后，将子节点移至删除节点位置；
3、删除节点左右孩子节点均非空，则要从左或右子树中查找到后继节点【后续节点的概念请看二叉查找树】，用后继节点替换删除节点，此时后继节点成为新的删除节点，后继节点最多只有一个非空的子节点，此时转化为情况2。
红黑树的删除规则和二叉查找树一致，关键要把握住一点，下面所说的删除节点不一定是指一开始要删除的节点，可能是情况3中的后续节点。
删除操作是否要调整
如果删除节点是红色，按二叉排序树的删除规则删除即可，不需要做任何调整；
原因：删除节点是红色，删除后，不会违背红黑树的任一条性质。
如果删除节点是黑色，按二叉排序树的删除规则册除后需要做调整；
原因：会违背性质5，即从任一个节点到null叶子节点的所有路径上的黑色节点的数量会不一样。
调整规则
定义：
【当前节点】x： 删除节点
【父亲节点】p：【当前节点】的父亲节点
【兄弟节点】b：【当前节点】的兄弟节点
注：【当前节点】的值可能在调整过程中发生变化，不一定是删除节点。
只分析【当前节点】是【父亲节点】的左孩子节点的情况，【当前节点】是【父亲节点】的右孩子节点的情况的调整规则和前者类似，只是镜像操作。
case 1 : 【兄弟节点】是红色
处 理：【兄弟节点】变黑，【父亲节点】变红，以【父亲节点】左旋，将【父亲节点】的当前右孩子节点设为【兄弟节点】,继续调整
image
case 2 : 【兄弟节点】是黑色且【兄弟节点】的左、右孩子节点均是黑色
处 理：【兄弟节点】变红,将【父亲节点】设为【当前节点】,继续调整
image
case 3 : 【兄弟节点】是黑色且【兄弟节点】的左孩子节点是红，右孩子节点是黑
处 理：将【兄弟节点】的左孩子节点变黑，【兄弟节点】变红，以【兄弟节点】右旋，将【父亲节点】的当前右孩子节点设为【兄弟节点】,继续调整
image
case 4 : 【兄弟节点】是黑色且【兄弟节点】的右孩子节点是红，左孩子节点颜色随意
处 理：【兄弟节点】染成【父亲节点】的颜色，【父亲节点】变黑，【兄弟节点】的右孩子节点变黑，以【父亲节点】左旋，算法结束
image
注：上述图只是演示操作过程，并不是显示一颗完整的红黑树。
红黑树的用途
Java中的TreeMap和TreeSet都是用红黑树实现。在Java8后,HashMap在解决哈希冲突时使用的链表长度大于8时会转化为红黑树。
代码实现
https://github.com/melodylzl/DataStructAndAlgorithms/blob/master/RBTree/RBTree.java
网友评论