概述
是不是看到各类树，心里有点慌？我也是，基础不牢，地动山摇啊，还是要回过头来看看各类树
二叉查找树
二叉查找树,Binary Search Tree(BST)
- 左子树上所有节点的值均 小于或等于 它根节点的值
- 右子树上所有节点的值均 大于或等于 它根节点的值
- 左右子树也都为二叉树
二叉查找树
上图就是一棵二叉查找树，那接下来我们 输入一个需要查找的数 10,那它的查询顺序如下:
- 根节点 9 , 10 > 9,查找它右边的数 13
- 10 < 13，查找它左边的数 11
- 10 < 11 ,查找它左边的数，找到了10
插入一个数也是按照以上的方式比较后，插入。
它的特点是，查询的次数最多等于这棵树的阶数
它的缺点是不会自动平衡，插入可能造成失衡，比如下图
不平衡的二叉树
接下来就引入红黑树。
红黑树
红黑树,Red Black Tree，它是一种自平衡的二叉查找树,除了有BST的特点外，它还有如下特点:
- 节点是红色或黑色。
- 根节点是黑色。
- 每个叶子节点都是黑色的空节点（NIL节点）。
- 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)
- 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。
红黑树
红黑树从根节点到子节点的最长路径不会超过最短路径的2倍。
红黑树插入数据，会有如下调整
- 变色
为了重新符合红黑树的规则，尝试把红色节点变为黑色，或者把黑色节点变为红色 - 左旋转
逆时针旋转红黑树的两个节点，使得父节点被自己的右节点取代，而原父节点成为自己的左节点
左旋转
- 右旋转
顺时针旋转红黑树的两个节点，使得父节点被自己的左节点取代，而原父节点成为自己的右节点
右旋转
比如在上边的红黑树中插入一个数 21,那么会是这样子
image.png
- 我们需要做的是变色，把节点25及其下方的节点变色：
image.png
此时节点17和节点25是连续的两个红色节点，那么把节点17变成黑色节点？恐怕不合适。这样一来不但打破了规则4，而且根据规则2（根节点是黑色），也不可能把节点13变成红色节点
- 变色已无法解决问题,那就选择左旋转
左旋转
- 旋转后,出现根节点为红色
左旋转
- 继续变色步骤,把17变黑色
变色
因为其中两条路径(17 -> 8 -> 6 -> NIL)的黑色节点个数是4，其他路径的黑色节点个数是3，不符合规则(从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点)
- 继续旋转,右旋转
右旋转
旋转后如下
右旋转
- 继续变色步骤
变色
13变黑，8变红,1变黑，最终达到了平衡
经历了【变色 -> 左旋转 -> 变色 -> 右旋转 -> 变色】，是挺绕的吧？可以查阅JDK中TreeMap、TreeSet、HashMap(java8)的源码，里边有红黑树的实现。
总结
红黑树的运用还是比较多的,关于红黑树自平衡的调整，插入和删除节点的时候都涉及到很多种情况，最好结合源码来理解。
