【Java】红黑树
1 平衡二叉树
平衡二叉树性质：
- 它的左右两个子树都是平衡数，且左右两个子树的高度差的绝对值不超过1
- 若将二叉树节点的平衡因子BF定义为该节点的左子树的深度减去它的右子树的深度，则平衡二叉树上所有节点的平衡因子只可能为-1,0,1。
- 只要二叉树上有一个节点的平衡因子的绝对值大于1，那么这颗平衡二叉树就失去了平衡。
平衡树示例图如图1.1所示：
图1.1 平衡二叉树
如上图所示，图（a）为平衡二叉树，图（b）不是平衡二叉树。
2 平衡二叉树的左旋与右旋
二叉树插入一个数后可能造成平衡因子大于1，导致二叉树不平衡，此时需要做平衡化处理。平衡化处理一般是进行左旋或者右旋。
2.1 左旋
图2.1为左旋动态示意图：
图2.1 左旋示意图
整个子树向左旋转，如果旋转后根节点原先有右节点，则断开重新连接到左子树的节点上，即图中S的左叶子节点本来连接到S节点上，旋转后连接到E节点的右叶子节点上。
2.2 右旋
图2.2为右旋转示意图：
图2.2 右旋转示意图
3 红黑树
3.1 红黑树简介
红黑树是一种自平衡的二叉查找树，是一种高效的查找树。红黑树具有良好的效率，它可在 O(logN) 时间内完成查找、增加、删除等操作。因此，红黑树在业界应用很广泛，比如 Java 中的 TreeMap，JDK 1.8 中的 HashMap、C++ STL 中的 map 均是基于红黑树结构实现的。
红黑树结构图如图3.1所示
图3.1 红黑树示意图
3.2 红黑树特性
红黑树的特性有以下几点
- 节点是红色或者黑色
- 根节点一定是黑色
- 每个红节点的两个子节点一定是黑色
- 从任一节点到其每个子节点的所有路径都有相同数量的黑色节点
- 每个叶子节点都是黑色的（叶子是NIL）
3.3 红黑树示例
图3.2为红黑树示例原树
图3.2 红黑树原树
- 向红黑树中插入节点14，一般默认插入节点是红色的，插入后结果如图3.3所示
图3.3 红黑树插入节点14
- 在原树上插入节点20，如图3.4所示
图3.4 红黑树插入节点20
如图3.4所示，插入后，树已经不是一个平衡的二叉树，需要进行以下几步处理。
1. 变色处理。
因为树已经不是一个平衡的二叉树，而且并不满足红黑树的要求，因为21和20均为红色这种情况下要对黑树进行变色。如图3.5所示，21需要变成黑色，22变成红色，17和25都变成黑色。
图3.5 红黑树变色
2. 左旋操作
如上图3.5所示，17变成黑色显然是不成立的，因为如果17变为黑色，那么13就会变为红色，不满足二叉树的规则，因此此处需要进行另一个操作——左旋处理。
左旋原理如图3.6所示
图3.6 左旋示意图
左旋结果如图3.7所示
图3.7 左旋结果图
进行左旋后，发现从根节点17，到1左子树的叶子节点经过了两个黑节点，而到6的左叶子节点或者右叶子节点要经历3个黑节点，很显然也不满足红黑树，因此还需要进行下一步操作，需要进行右旋操作
3. 右旋操作
右旋示意图如图3.8所示
图3.8 右旋示意图
由于是从13节点出现的不平衡，因此对13节点进行右旋，得到结果如图3.9所示
图3.9 右旋结果图
4. 变色操作
再对其节点进行变色，得到结果如图3.10所示
图3.10 最终结果图
4 参考文章
https://blog.csdn.net/q3244676719/article/details/81540830
https://segmentfault.com/a/1190000014037447
https://blog.csdn.net/qq_37934101/article/details/81160254
