红黑树

参考文章：五分钟搞懂什么事红黑树（全程图解））

在JDK 1.8之后，HashMap中引入了红黑树，当Entry链表长度超过一个阈值（8）的时候，它就会进化成一颗红黑树。
红黑树其实就是一颗平衡的二叉查找树，所以在此之前需要先讲一下什么是二叉查找树：

二叉查找树有一下3个特性：

1. 左子树上所有节点的值均小于或等于他的根节点的值。
2. 右子树上所有节点的值均大于或等于他的根节点的值。

3. 左右子树也一定分别为二叉查找树。

   
   二叉查找树示例

有了二叉查找树，我们便可以以此来提高查找效率，但是如果碰到下面这样的二叉查找树，那么查找效率将会退化。

因此，为了保证二叉查找树的某一子树深度不要过深，便有了红黑树。红黑树除了需要满足二叉查找树的特性外，还需满足以下特性：

1. 节点是红色或者黑色。
2. 根节点是黑色。
3. 每个叶子节点都是黑色的空节点（null）。
4. 每个红色节点的两个子节点都是黑色的。
5. 从任意节点到其每个叶子的所有路径都包含相同的黑色节点。

例如下图就是一个典型的红黑树

当向树中插入或删除元素时，可能会破坏以上特性，那么这时就需要做出调整，调整的方式有变色和旋转，旋转又可分为左旋转和右旋转。

原文篇幅较长且多为图解，全搬过来没有什么意义，所以只记录这些许部分的东西吧，原文写的很好，留个链接在这里：五分钟搞懂什么事红黑树（全程图解））