二叉查找树（Binary Search Tree）
-
特性：
1 左子树上所有结点的值均小于或等于它的根结点的值。
2 右子树上所有结点的值均大于或等于它的根结点的值。
3 左、右子树也分别为二叉排序树。
二叉查找树
优点：
查找所需的最大次数等同于二叉查找树的高度！
缺点：
多次插入新节点会导致不平衡！
失去平衡
红黑树（Red Black Tree）
-
自平衡的二叉查找树。
红黑树 附加特性：
1 节点是红色或黑色。
2 根节点是黑色。
3 每个叶子节点都是黑色的空节点（NIL节点）。
4 每个红色节点的两个子节点都是黑色（从每个叶子到根的所有路径上不能有两个连续的红色节点）。
5 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。红黑树从根到叶子的最长路径不会超过最短路径的两倍。
-
当插入或者删除节点的时候，红黑树的规则有可能被打破，需要做一些调整（【变色】和【旋转】（左旋和右旋））。
- 【变色】：红色节点变为黑色，或者把黑色节点变为红色。
-
【左旋转】：逆时针旋转红黑树的两个节点，使得父节点被自己的右孩子取代，而自己成为自己的左孩子。
左旋转 -
【右旋转】：顺时针旋转红黑树的两个节点，使得父节点被自己的左孩子取代，而自己成为自己的右孩子。
右旋转
demo1：向原红黑树插入值为14的新节点
向原红黑树插入值为14的新节点
- 由于父节点15是黑色节点，因此这种情况并不会破坏红黑树的规则，无需做任何调整。
demo2：向原红黑树插入值为21的新节点
step1
-
变色
step2
step3
step4 -
此时的样子
step5 -
左旋转
step5 -
变色
step6 - 其中两条路径(17 -> 8 -> 6 -> NIL)的黑色节点个数是4，其他路径的黑色节点个数是3，不符合规则5。
-
右旋转
step6 -
变色
step7 - 结束！
红黑树的应用场景：
JDK的集合类TreeMap和TreeSet底层用的红黑树。Java8中，HashMap也用到了红黑树。
针对大量数据，如果在内存中作业优先考虑红黑树(map,set之类多为RB-tree实现)，如果在硬盘中作业优先考虑B系列树(B+, B, B*)。
参考：
- 知乎：为啥 redis 使用跳表(skiplist)而不是使用 red-black？
- 微信公众号：程序员小灰
