最近在撸Java8-Hashmap源码的时候遇到一个问题红黑树的存储结构，当时看的时候还是有点迷糊的，而且对于左旋还是右旋，直接就缴械投降了。现在花一篇文章来梳理一下自己对这个结构算法的理解。
红黑树也叫自平衡二叉查找树或者平衡二叉B树，
时间复杂度为O(log n)
高度h <= log2(n+1)
红黑树的特点
性质1. 节点是红色或黑色。
性质2. 根节点是黑色。
性质3 每个叶节点（NIL节点，空节点）是黑色的。
性质4 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)
性质5. 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。
注意：这里有一点需要解释的就是，插入节点一定是插入一个红色的节点，为什么呢？因为这样只是有可能违背性质4，其余四个性质都是符合的，可以减小复杂度。以下我们以HashMap的红黑树实现为例。
插入实现
/**
* Tree version of putVal.
*/
final TreeNode<K,V> putTreeVal(HashMap<K,V> map, Node<K,V>[] tab,
int h, K k, V v) {
Class<?> kc = null;
boolean searched = false;
TreeNode<K,V> root = (parent != null) ? root() : this;
for (TreeNode<K,V> p = root;;) {
int dir, ph; K pk;
// 比较要插入值 与 节点的 hash值等属性 的大小
// 确定大小之后然后选择 左右子树 循环继续比较
if ((ph = p.hash) > h)
dir = -1;
else if (ph < h)
dir = 1;
else if ((pk = p.key) == k || (k != null && k.equals(pk)))
return p;
else if ((kc == null &&
(kc = comparableClassFor(k)) == null) ||
(dir = compareComparables(kc, k, pk)) == 0) {
if (!searched) {
TreeNode<K,V> q, ch;
searched = true;
if (((ch = p.left) != null &&
(q = ch.find(h, k, kc)) != null) ||
((ch = p.right) != null &&
(q = ch.find(h, k, kc)) != null))
return q;
}
dir = tieBreakOrder(k, pk);
}
TreeNode<K,V> xp = p;
// 只有确认了 要插入的位置的 左子树 或者 右子树为空，即找到了要插入节点的位置
if ((p = (dir <= 0) ? p.left : p.right) == null) {
Node<K,V> xpn = xp.next;
// 创建新的 树的叶子节点
TreeNode<K,V> x = map.newTreeNode(h, k, v, xpn);
// 插入到指定的 分支上
if (dir <= 0)
xp.left = x;
else
xp.right = x;
xp.next = x;
x.parent = x.prev = xp;
if (xpn != null)
((TreeNode<K,V>)xpn).prev = x;
// 这里需要注意了 这有执行了两步操作，
// balanceInsertion这一步涉及到了 红黑树的平衡算法，我们只看它
moveRootToFront(tab, balanceInsertion(root, x));
return null;
}
}
}
在看平衡算法之前，我们需要对红黑树的特性进行详细说明，确保知道什么时候该旋转，什么时候采用什么旋转。
第一：插入的节点是红色的
第二：平衡、或者 旋转算法是对三层树形结构进行的。如果你站在整个树结构上看，你会发现无从下手
第三：什么时候该旋转，不满足h <= log2(n+1)，即前两层树形结构不是满二叉树
第四：在插入节点之前，树的结构是符合红黑树的（这个前提很重要）
balanceInsertion平衡算法
static <K,V> TreeNode<K,V> balanceInsertion(TreeNode<K,V> root, TreeNode<K,V> x) {
x.red = true;
for (TreeNode<K,V> xp, xpp, xppl, xppr;;) {
// 这是一层树形结构，也就是只有一个节点
// 直接进行着色操作
if ((xp = x.parent) == null) {
x.red = false;
return x;
}
// 这里是二层树形结构，xp 存在，或者xpp 为空
// 这里需要说明一下，有人会认为这不仅仅包含二层树形结构，可能还有三层
// 从条件上来说是的，可能包含三层，但是这里有一个我们上面说的前提，那就是插入之前必须是红黑树，
// 那也就是说!xp.red 意思就是 xp 为黑色节点，而且xp 是符合红黑树的，那么插入一个红色节点是不会改变它是红黑树的特性
// 反过来想插入之前的问题
// 这里我们把问题缩小一点，就插入点的三层树形结构。而且插入之前还必须符合红黑树
// 如果xp 插入之前是黑色的并且符合红黑树，这种特性是不是跟只有一个根节点是一样的
else if (!xp.red || (xpp = xp.parent) == null)
return root;
// 三层结构，如果是左分支
if (xp == (xppl = xpp.left)) {
// 这里是判断前两层是否是满二叉树，也就是是否满足h <= log2(n+1)
// 如果满足是不需要进行 旋转的，因为无法对其旋转（左旋，右旋），
// 也不需要旋转，只需要进行重新着色就可以满足红黑树的五大特性了
if ((xppr = xpp.right) != null && xppr.red) {
xppr.red = false;
xp.red = false;
xpp.red = true;
x = xpp;
}
else {
// 接下来就是 不满足满二叉树，或者说 不满足h <= log2(n+1)
// 这个时候我们就需要考虑旋转了，怎样旋转呢，这里我先说结果，后面分析原因，或者为什么
if (x == xp.right) {
// 树形结构是 L — R --> 左旋，变成 L— L树形结构
root = rotateLeft(root, x = xp);
// x、xp、xpp 重新赋值
xpp = (xp = x.parent) == null ? null : xp.parent;
}
if (xp != null) {
// xp 着色
xp.red = false;
if (xpp != null) {
// xpp 着色
xpp.red = true;
// L — L --> 右旋
// 将三层树形结构 右旋 变成一个 二层结构，满足 h <= log2(n+1) 特性
root = rotateRight(root, xpp);
}
}
}
}
else {
// 这里也是一样的
// 判断前两层是否是满二叉树，也就是是否满足h <= log2(n+1)
// 如果满足是不需要进行 旋转的，因为无法对其旋转（左旋，右旋），
// 也不需要旋转，只需要进行重新着色就可以满足红黑树的五大特性了
if (xppl != null && xppl.red) {
xppl.red = false;
xp.red = false;
xpp.red = true;
x = xpp;
}
else {
// 接下来也是 不满足满二叉树，或者说 不满足h <= log2(n+1)
if (x == xp.left) {
// 树形结构是 R — L --> 右旋，变成 R— R树形结构
root = rotateRight(root, x = xp);
// x、xp、xpp 重新赋值
xpp = (xp = x.parent) == null ? null : xp.parent;
}
if (xp != null) {
// xp 着色
xp.red = false;
if (xpp != null) {
// xpp 着色
xpp.red = true;
// R — R --> 右旋
// 将三层树形结构 左旋 变成一个 二层结构，满足 h <= log2(n+1) 特性
root = rotateLeft(root, xpp);
}
}
}
}
}
}
接下来我们重点说一下，左旋和右旋，首先不管是左旋还是右旋，都是只对两个节点进行修改，有一个节点的位置是不发生改变的。
- 第一什么时候需要进行旋转 ?，以及需要旋转几次 ？
判断树的结构是否满足h <= log2(n+1)，如果不满足则需要进行旋转，如果满足只需要重新进行着色即可。
- 第二是什么叫做左旋，还是右旋 ？
判断采用左旋，还是右旋，就是当前这两个节点的位置关系，是左分支，还是右分支，则相应的旋转之后是相反的分支，例如：现有是 左分支的关系， 旋转之后就是右分支，则是进行了右旋操作，同样现有关系是右分支的关系，旋转之后就是左分支，则是进行了 左旋操作。
把上面balanceInsertion平衡算法统计一下，我们可以得到下面
L（左分支）——L（左分支） → R (右旋）
L（左分支）——R（右分支）→ L（左旋）——R (右旋）
R（右分支）——R（右分支）→ L（左旋）
R（右分支）——L（左分支）→ R (右旋）——L（左旋）
下面我们以图来看一看包含两步的旋转过程来，对照一下
L（左分支）——R（右分支）→ L（左旋）——R (右旋）
R（右分支）——L（左分支）→ R (右旋）——L（左旋）
- 第三：如何确定我该做左旋，还是右旋
个人理解，如果原来的树曲曲折折，需要先掰直了下面部分，如果是直线的树了 再把上面部分掰弯，形成一个倒V型。这个只是方面理解，真正的原因是，如果不采用上面的步骤进行旋转，旋转顺序换掉，都会得到一种结果那就是，整个二叉树不成立了，失去了二叉树的意义了。当然我们也可以一步到位，以空间换时间，这是没有问题的，从复杂度来讲左旋和右旋是最精炼的，最基础的，可以完美适配的。
rotateLeft（左旋）
static <K,V> TreeNode<K,V> rotateLeft(TreeNode<K,V> root, TreeNode<K,V> p) {
TreeNode<K,V> r, pp, rl;
if (p != null && (r = p.right) != null) {
if ((rl = p.right = r.left) != null)
rl.parent = p;
if ((pp = r.parent = p.parent) == null)
// 只有当p 已经探到了树的底部的时候，左旋，会改变根的指向，所以这里需要修改掉root 的指向
(root = r).red = false;
else if (pp.left == p)
pp.left = r;
else
pp.right = r;
r.left = p;
p.parent = r;
}
return root;
}
rotateRight（右旋）
static <K,V> TreeNode<K,V> rotateRight(TreeNode<K,V> root, TreeNode<K,V> p) {
TreeNode<K,V> l, pp, lr;
if (p != null && (l = p.left) != null) {
if ((lr = p.left = l.right) != null)
lr.parent = p;
if ((pp = l.parent = p.parent) == null)
// 只有当p 已经探到了树的底部的时候，左旋，会改变根的指向，所以这里需要修改掉root 的指向
(root = l).red = false;
else if (pp.right == p)
pp.right = l;
else
pp.left = l;
l.right = p;
p.parent = l;
}
return root;
}
我相信看完上面的解释，你对左旋和右旋的实现会有了一个更为清晰的认知了。
好了，分析到这里了。
