今天我们接着上面继续分析HashMap的源码，JDK8中我们引入了红黑树，这一章节，我们主要来探讨下红黑树。 在引入红黑树之前，我们先了解下二叉查找树（Binary Search Tree BST）。
1. 二叉查找树
BST具备的特性：
（1）左侧树值小于等于它的根节点值。
（2）右侧树大于等于它的根节点值。
（3）左右侧数都是二叉查找树。
BST具备的优点：
（1）通过上面的特征描述，相比线型存储，它优化了查找的性能，比如说：下面就是一个典型的二叉树查找，如果我们要查找数值为10的节点，只需要3步，9->13->11->10。
BST具备的缺陷：
1.糟糕情况下会变成线型结构，这样会大大降低性能。（这种情况比如说：插入节点总是小于根节点或者大于根节点），如下图所示：
2. 二叉查找树
基于二叉查找树存在这种缺陷，红黑树的出现就是解决这种问题，它是二叉查找树的典型，又叫做平衡二叉查找树，接下来具体讲讲红黑树的一些特征。
红黑树的特征：
（1）根节点是黑色
（2）顾名思义，节点的颜色分为红色或者黑色
（3）空节点为黑色
（4）每个红色节点的子节点都是黑色节点（不能有两个连续的红色节点）
（5）从任意节点到每个叶子的所有路径黑色节点个数相同
由于红黑树具有上面这些特征的约束，我们在对红黑树进行插入，删除操作时可能会破坏原有红黑树的树结构，这个时候需要对数结构重新作出调整，红黑数调整的方式有有两种：变色和旋转（左旋转、右旋转）。
- 左旋转
对于当前结点而言，如果右子结点为红色，左子结点为黑色，则执行左旋转，如下图：
- 右旋转
对于当前结点而言，如果左子、左孙子结点均为红色，则执行右旋转，如下图：
- 变色
对于当前结点而言，如果左、右子结点均为红色，则执行变色，如下图：