红黑树

红黑树的特征如下

每个结点不是红色就是黑色 不可能有连在一起的红色结点 根结点都是黑色 每个红色结点的两个子结点都是黑色 任一结点到其子树中每个叶子节点的路径都有相同数量的黑色结点

在这里插入图片描述

那么问题来了，如何在删除和插入数据的时候保证以上性质呢，红黑树的策略就是改变颜色和旋转，改变颜色很好理解，那么旋转是什么呢？

旋转分为左旋和右旋

左旋

如下图所示左图为旋转前，右图是旋转后，是以5为根结点从左向右旋转，就是逆时针旋转

在这里插入图片描述

右旋

如下图所示左图为旋转前，右图是旋转后，是以5为根结点从右向左旋转，就是顺时针旋转

在这里插入图片描述

旋转和颜色变换规则

1.变颜色的情况：当前结点的父亲是红色，且它的祖父结点的另一个子结点（叔叔结点）也是红色。

（1）把父节点设为黑色 （2）把叔叔也设为黑色 （3）把祖父也就是父亲的父亲设为红色 （4）把指针定义到祖父结点设为当前要操作的

2.左旋：当前父结点是红色，叔叔是黑色的时候，且当前的结点是右子树，以父结点作为左旋。不需要改变颜色。

3.右旋：当前父结点是红色，叔叔是黑色的时候，且当前的结点是左子树。

（1）把父结点变为黑色 （2）把祖父结点变为红色 （爷爷） （3）以祖父结点旋转（爷爷）

插入数据示例

假设有如下的红黑树，符合红黑树的特征

在这里插入图片描述

现在插入数据6，颜色假设为红色，这样就不符合红黑树的特征，所以就要对其进行变换

在这里插入图片描述

变换过程如下：

1.因为父结点7和叔叔结点10都是红色，所以首先颜色变换，将父结点7和叔叔结点10变为黑色，祖父结点8变为红色，当前结点变为祖父结点8，依然不符合红黑树特征，继续变换

2.因为父结点5为红色，叔叔结点20为黑色，且当前结点为右子树，那么对父结点5进行左旋操作，并且当前结点设置为父结点5，依然不符合红黑，继续变换

3.因为父结点8为红色，叔叔结点20为黑色，当前结点为左子树，那么先将父结点8变为黑色，祖父结点15变为红色，那么再对祖父结点15进行右旋操作，同样当前结点变为祖父结点15，至此现在的红黑树已经符合特征，变换完成

可以看出变换完的红黑树结构依然稳定，所以红黑树就解决了插入和删除的问题

在这里插入图片描述

红黑树的应用

JDK HashMap JDK TreeMap JDK TreeSet Windows文件搜索