因为集合类用到了红黑树，所以，顺便学习下红黑树的原理
- 二叉树，每个节点最多有两个子节点的树
- 二叉查找树，可以二分查找的二叉树
- 红黑树，是一个近似平衡的二叉查找树
二叉查找树
入门：https://www.sohu.com/a/201923614_466939
Binary Search Tree(BST)——二叉查找树具备什么特性呢？
1.左子树上所有结点的值均小于或等于它的根结点的值。
2.右子树上所有结点的值均大于或等于它的根结点的值。
3.左、右子树也分别为二叉排序树。
下图中这棵树，就是一颗典型的二叉查找树：
图片.png
二叉查找树的查找使用的是二分查找的思想，查找效率很高。
但是缺陷也很明显：
假设初始的二叉查找树只有三个节点，根节点值为9，左孩子值为8，右孩子值为12
图片.png
接下来我们依次插入如下五个节点：7,6,5,4,3。依照二叉查找树的特性，结果会变成一颗畸形的树，查找从二分查找变成了线性查找，速度会随着树的变深而变慢。
图片.png
红黑树
红黑树（Red Black Tree）是一种近似平衡的二叉查找树，它能够确保任何一个节点的左右子树的高度差不会超过二者中较低那个的1倍。
红黑树必须满足：
- 节点是红色或黑色。
- 根节点是黑色。
- 每个叶子节点都是黑色的空节点（NIL节点）。
- 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)
- 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。
（规则5可以推出，新插入的节点，颜色一定是红色）
当红黑树的结构发生改变时（插入、删除节点），都会进行自调整（变色 -> 左旋转 -> 变色 -> 右旋转 -> 变色），使得整颗树符合上面5个特性，也正是因为这些规则的限制，红黑树才能保持自平衡。
调整有两种方式：
- 颜色调整，就是改变节点的颜色（红<->黑）
- 旋转，包括左旋和右旋
左旋：
左旋的过程是将x的右子树绕x逆时针旋转，使得x的右子树成为x的父亲，同时修改相关节点的引用。旋转之后，二叉查找树的属性仍然满足。
图片.png
右旋：
右旋的过程是将x的左子树绕x顺时针旋转，使得x的左子树成为x的父亲，同时修改相关节点的引用。旋转之后，二叉查找树的属性仍然满足。
图片.png
Java的TreeMap、TreeSet底层就是用红黑树实现的。在Java8中，HashMap也改造用了红黑树。
网友评论