红黑树
红黑树的特点
-
节点是红色或黑色。
-
根节点是黑色。
-
每个叶子节点都是黑色的空节点（NIL节点）。
4 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)
- 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。
下图中这棵树，就是一颗典型的红黑树：
以上规则保证了红黑树从root到leaf的最长路程不会超过最短路径的2倍
插入
红黑树在插入时平衡性会被破坏，需要重新平衡
1.向原红黑树插入值为14的新节点：
2.向原红黑树插入值为21的新节点：
由于父节点22是红色节点，因此这种情况打破了红黑树的规则4（每个红色节点的两个子节点都是黑色），必须进行调整，使之重新符合红黑树的规则。
变色
为了重新符合红黑树的规则，尝试把红色节点变为黑色，或者把黑色节点变为红色。
下图所表示的是红黑树的一部分，需要注意节点25并非根节点。因为节点21和节点22连续出现了红色，不符合规则4，所以把节点22从红色变成黑色：
但这样并不算完，因为凭空多出的黑色节点打破了规则5，所以发生连锁反应，需要继续把节点25从黑色变成红色：
此时仍然没有结束，因为节点25和节点27又形成了两个连续的红色节点，需要继续把节点27从红色变成黑色：
旋转
左旋转
逆时针旋转红黑树的两个节点，使得父节点被自己的右孩子取代，而自己成为自己的左孩子。
图中，身为右孩子的Y取代了X的位置，而X变成了自己的左孩子。此为左旋转。
右旋转
顺时针旋转红黑树的两个节点，使得父节点被自己的左孩子取代，而自己成为自己的右孩子。大家看下图：
身为左孩子的Y取代了X的位置，而X变成了自己的右孩子。此为右旋转。
红黑树的用处
JDK中， TreeMap, TreeSet底层为红黑树实现
1.8中的HashMap也用到了红黑树
总结
关键要懂得红黑树自平衡调整的主体思想