上文介绍了跟红黑树相关的知识点，尤其是左旋、右旋、自平衡等概念。本文开始结合源码对旋转和平衡进行深入分析。
- HashMap为什么从链表换成了树
- 从平衡二叉树到红黑树
- 红黑树的左旋和右旋（源码解析）
- 红黑树的插入自平衡（源码解析）
- 红黑树的删除自平衡（源码解析）
- HashMap中的红黑树（源码解析）
红黑树的左旋和右旋（源码解析）
1.红黑树节点的数据结构
在开始之前，我们先看一下红黑树的数据结构
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
TreeNode<K,V> parent; // 父节点
TreeNode<K,V> left; //左子节点
TreeNode<K,V> right; //右子节点
TreeNode<K,V> prev; // 前节点
boolean red; //是否为红色
}
我们注意到，TreeNode继承自LinkedHashMap.Entry<K,V>参看源码static class Entry<K,V> extends HashMap.Node<K,V> Entry又继承自HashMap.Node<K,V>，所以TreeNode也存在Node节点的成员变量，那么整体来看TreeNode的成员如下：
static final class TreeNode<K,V> {
TreeNode<K,V> parent; // 父节点
TreeNode<K,V> left; //左子节点
TreeNode<K,V> right; //右子节点
TreeNode<K,V> prev; // 前节点
boolean red; //是否为红色
final int hash;
final K key;
V value;
Node<K,V> next;
}
2. 左旋
上一篇文章已经介绍过左旋，我们来看一下示意图，挖掘其中的执行规律：
左旋示意图
左旋的时候，可以看作将pivot节点（18）向上拎起来，这样物理上原root节点（9）及root左子树下沉，变成pivot（18）的左子树，同时根据二叉搜索树的原则，pivot的左子树（10）会变成root节点（9）的右子树。
可见如果我们要写rotateLeft函数，首先要告诉它pivot节点是谁，我们来看远源码：
static <K,V> TreeNode<K,V> rotateLeft(TreeNode<K,V> root,
TreeNode<K,V> p) {
/*
root：整个树的root节点
p：pivot节点的parent节点（图中9）
r：parent的右节点（图中18），pp：parent的父节点（null），rl：pivot的左节点（图中10）
*/
TreeNode<K,V> r, pp, rl;
if (p != null && (r = p.right) != null) {
if ((rl = p.right = r.left) != null) //父节点（9）的右子节点指向pivot左子节点（10）
rl.parent = p; //相应的设置pivot的左子节（10）的父节点为pivot的父节点（9）
if ((pp = r.parent = p.parent) == null) //将pivot节点的父节点设置为之前的祖父节点
(root = r).red = false; //如果pivot节点在的父节点为null则表示它是新的root节点，所以将它赋值给root变量，同时将root节点的颜色变为黑色
else if (pp.left == p) //如果pivot的父节点是祖节点的左子树
pp.left = r; //那么让祖父节点的左子树从此指向pivot
else
pp.right = r; //如果pivot的父节点是祖父觉点的右子树，则让祖父节点的右节点从此指向piovt
r.left = p; //pivot左旋后成为新根节点，所以它的左子树指向原来的父节点
p.parent = r; //原来父节点的parent指向pivot
}
return root; //返回这棵树
}
通过阅读源码我们可以发现，实际的调整过程和我们上面分析的次序不同，在代码中是先将pivot节点的左子树移交到parent节点的右子树（双方互认父子）；对parent的父节点进行判断，如果为空说明parent节点就是root节点，左旋后pivot即为新root节点，如果不为空就让pivot和祖父节点互认父子；最后pivot节点和原parent节点互认父子。
3. 右旋
右旋的逻辑和左旋近似。
右旋
static <K,V> TreeNode<K,V> rotateRight(TreeNode<K,V> root,
TreeNode<K,V> p) {
/**
p：pivot的父节点（9）
l：pivot（7）
pp：pivot的祖父节点（null）
lr：pivot的右子树（8）
*/
TreeNode<K,V> l, pp, lr;
if (p != null && (l = p.left) != null) {
if ((lr = p.left = l.right) != null)
lr.parent = p; //pivot右子树和pivot父节点互认父子
if ((pp = l.parent = p.parent) == null) //如果pivot的祖父节点为空的时候，将pivot的父节点设为空
(root = l).red = false; //将pivot设为root节点，且颜色为黑色
else if (pp.right == p) //如果pivot的祖父节点存在，则pivot与祖父节点互认父子
pp.right = l;
else
pp.left = l;
l.right = p; //pivot节点与原root节点互认父子
p.parent = l;
}
return root;
}
3. 插入后平衡
插入后平衡指的是当进行插入操作后，因为新节点会默认为红色，所以可能违反红黑树原则而导致不平衡，需要通过自平衡算法进行再平衡。
函数声明：
static <K,V> TreeNode<K,V> balanceInsertion(TreeNode<K,V> root,
TreeNode<K,V> x)
root为整个树的根节点，x为插入的节点。首先我们看第一段代码：
x.red = true; //新插入的节点设置为红色
for (TreeNode<K,V> xp, xpp, xppl, xppr;;) { // ---point 1
if ((xp = x.parent) == null) { //xp为插入节点的父节点
x.red = false; //如果插入节点的父节点为空，意味着这是一个新树，插入的节点即为root节点，将其颜色变黑后，可直接返回
return x;
}
/**如果父节点为黑色，那么插入一个红色节点自然无碍，
或者xpp作为祖父节点为空（这种情况作者没有想到何时
会出现，感觉写的有问题，似乎想表达的意思是x的父节
点就是根节点，既然这样，那父节点一定是黑色）*/
else if (!xp.red || (xpp = xp.parent) == null)
return root;
这一段代码其实就是针对插入的两种情况，一是插入的是一个空树，则改变x的颜色为黑即可，二是插入节点的父节点为黑色，则可以直接插入。这里的for循环定义时没有设置跳出条件，不难分析出，这里是在以新节点为起点，进行递归，递归的方式是不断更改x变量指向的节点，最后递归的结束条件就是我们看到的这两个return的条件。接下来，对于另外3种场景进行处理（上文已提到总共有5种场景）
//进入这里说明父节点为红色（否则就直接return root了）
if (xp == (xppl = xpp.left)) { //父节点是祖父节点的左子树
if ((xppr = xpp.right) != null && xppr.red) { //祖父节点的右子树，也就是叔叔节点是红色
xppr.red = false; //叔叔节点变黑
xp.red = false; //父节点变黑
xpp.red = true; //祖父节点变红
x = xpp; 让当前节点指向祖父节点
}
else {
if (x == xp.right) { //黑叔叔且当前节点是右子节点
root = rotateLeft(root, x = xp); //将当前节点指向父节点，以父节点为轴心左旋
xpp = (xp = x.parent) == null ? null : xp.parent; //此时xp就是新插入的节点了，xpp还是原来的祖父节点
}
if (xp != null) {
xp.red = false; //将父节点置为黑色
if (xpp != null) {
xpp.red = true; //将爷爷节点置为红色
root = rotateRight(root, xpp); //以爷爷节点为轴心右旋
}
}
}
}
可见如果右插入新节点发现它有个左边的红爸爸和右边的黑叔叔，则以红爸爸为轴心进行左旋，完成后父子的位置调换，将新爸爸和祖父节点的颜色改变，再进行右旋就完成平衡，整个过程图解如下：
左右结构图解
看完左爸爸和右叔叔，再看一下爸爸居右叔叔居左，也就是后半段代码：
else {
if (xppl != null && xppl.red) {
//和上面一样，如果父节点和叔叔节点都为红色，则红变黑，且祖父节点变红
xppl.red = false;
xp.red = false;
xpp.red = true;
x = xpp;
}
else {
//如果是黑叔叔红爸爸，且爸爸是爷爷的右儿子，而我是爸爸的左儿子（右左结构）
if (x == xp.left) {
root = rotateRight(root, x = xp); //儿子当爸爸，且为基点右旋
xpp = (xp = x.parent) == null ? null : xp.parent;
}
if (xp != null) {
//与上面一样，当树结构为右右结构后，变色，左旋
xp.red = false;
if (xpp != null) {
xpp.red = true;
root = rotateLeft(root, xpp);
}
}
}
}
右左结构图解
网友评论