Java红黑树小知识

什么是红黑树？

性质

1. 每个节点不是红色就是黑色
2. 不可能有连在一起的红色节点
3. 根节点都是黑色 root
4. 每个红色节点的两个子节点都是黑色。叶子节点都是黑色：出度为0

满足了性质就可以近似的平衡，不一定要红黑，可以为其他的

为了满足红黑树的性质，因此出现了旋转：

三种变换：

1. 改变颜色：最简单 红变黑 黑变红
2. 左旋：针对于点旋
3. 右旋

旋转和颜色变换规则：所有插入的点默认为红色

变颜色的情况：

当前节点的父亲是红色，且它的祖父节点的另一个子节点也是红色（叔叔节点）：

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

左旋

当前父节点是红色，叔叔是黑色的时候，且当前的节点是右子树，左旋以父节点作为左旋。

右旋

当前父节点是红色，叔叔是黑色的时候，且当前的节点是左子树，右旋

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

红黑树的应用：

1. HashMap ： JDK8：数据+链表+红黑树（8）
2. TreeMap:set底层
3. Windows:MySQL btree
4. 各种底层系统数据结构：JDK，Linux进程调度
5. Nginx等等