性质：
红黑树(Red Black Tree)是一种自平衡的二叉查找树。除了符合二叉查找树的基本特性外，它还具有下列的附加特性:
1.节点是红色或黑丝。
2.根节点是黑色。
3.每个叶子节点都是黑色的空节点（null节点）
4.每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)
5.从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。
下图中这棵树，就是一颗典型的红黑树：
image
这些规则保证了红黑树的自平衡。红黑树从根节点到叶子的最长路径不会超过最短路径的2倍。
没有这些规则，二叉查找树可能变成一个“瘸子”
image
但插入或删除节点的时候，红黑树的规则有可能被打破。这时候需要做出一些调整，来继续维持我们的规则。
红黑树调整有两种方法：
1.变色：为了重新符合红黑树的规则，尝试把红色节点变为黑色，或者把黑色节点变为红色。
为了重新符合红黑树的规则，尝试把红色节点变为黑色，或者把黑色节点变为红色。
下图所表示的是红黑树的一部分，需要注意节点25并非根节点。因为节点21和节点22连续出现了红色，不符合规则4，所以把节点22从红色变成黑色：
image
但这样并不算完，因为凭空多出的黑色节点打破了规则5，所以发生连锁反应，需要继续把节点25从黑色变成红色：
image
此时仍然没有结束，因为节点25和节点27又形成了两个连续的红色节点，需要继续把节点27从红色变成黑色：
image
2.旋转
左旋转：逆时针旋转红黑树的两个节点，使得父节点被自己的右孩子取代，而自己成为自己的左孩子。
图片.png
右旋转：顺时针旋转红黑树的两个节点，使得父节点被自己的左孩子取代，而自己成为自己的右孩子。
image
hash虽然是一种O(1)的搜索,但是当如果数据量比较大而Hash桶比较小，哈希冲突就很严重,在jdk1.8版本后，java对HashMap做了改进，在链表长度大于8的时候，将后面的数据存在红黑树中，以加快检索速度。
既然红黑树那么好，为啥hashmap不直接采用红黑树，而是当大于8个的时候才转换红黑树？
当个数不多的时候，直接链表遍历更方便，实现起来也简单。而红黑树的实现要复杂的多。
因为红黑树需要进行左旋，右旋操作， 而单链表不需要。
网友评论