输入平衡操作
static <K,V> TreeNode<K,V> balanceInsertion(TreeNode<K,V> root,
TreeNode<K,V> x) {
//root是根节点
//x是已经插入的节点
//刚插入节点设置为红节点
x.red = true;
//xp是父节点，xpp是祖父节点，xppl是左叔父节点，xppr是右叔父节点
for (TreeNode<K,V> xp, xpp, xppl, xppr;;) {
//循环进行平衡操作
if ((xp = x.parent) == null) {
//如果父节点 为空，代表x是根节点，直接设置为黑节点，并返回
x.red = false;
return x;
}
else if (!xp.red || (xpp = xp.parent) == null)
//如果父节点是黑节点，或者祖父节点为空代表父节点是根节点，直接返回
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) {
//如果插入的节点x是父节点的右子节点，则：
//需要对父节点进行左旋转
root = rotateLeft(root, x = xp);
//旋转之后，重新去祖父节点
xpp = (xp = x.parent) == null ? null : xp.parent;
}
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);
}
}
}
}
}
}
平衡操作：
- 当前的节点标间为红节点（原因：）
- 如果当前节点是根节点 ，改为黑节点，并作为根节点返回
- 如果当前节点的父节点是黑节点或者根节点，则直接返回根节点，没有操作不平衡
- 如果当前节点的叔父节点（不了是左叔父或者右叔父节点）不为空且是红色节点，代表父节点是黑色，则直接进行变色处理：父节点和叔父节点变为黑节点，同时祖父节点变为红色节点，将祖父节点作为当前节点继续进行一样的平衡操作
- 如果叔父节点为空或者是黑色节点，那么父节点很大可能是红节点，那就可能存在连续两个红节点破坏红黑二叉树特性，就需要进行选择操作：
- 如果当前节点是其父节点的右子树，代表右子树深度可能比左子树还深，需要先将当前节点进行左旋转，将当前节点变为其右子节点的左子树，同时其右子节点提升为当前节点的父节点，这样可以减少右子树的深度，左旋转之后将父节点变为黑节点，祖父节点变为红节点，祖父节点不为空的情况下再对祖父节点进行右旋转，接着继续下一步的平衡操作
- 如果当前节点是父节点的左子树，代表左子树深度可能比右子树还深，需要先将当前节点进行右旋转，将当前节点变为其左子节点的右子树，同时其右子树提升为当前节点的父节点，这样可以减少左子树的深度，右旋转之后将父节点变为黑节点，祖父节点变为红节点，祖父节点不为空的情况下再对祖父节点进行左旋转，接着继续下一步的平衡操作
总结：
- 平衡操作是让树保持红黑二叉树的特性，如果发现不满足红黑二叉树的特性就需要变色、左旋、右旋，左旋或者右旋操作可以降低深度
- 发生旋转的条件：
- 叔父节点为空或者是黑节点
- 如果当前节点是祖父节点的左子孙树，同时是父节点的右子树，则对先对其父节点进行左旋再对其祖父节点进行右旋操作；如果当前节点是祖父节点的右子孙树，同时是父节点的左子树，则对先对父节点进行右旋操作，再对其祖父节点做左旋操作
左旋
static <K,V> TreeNode<K,V> rotateLeft(TreeNode<K,V> root,
TreeNode<K,V> p) {
//r是当前节点的右子节点，rl是右子节点的左子节点，pp是当前节点的父节点
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)
//原右子节点的父节点指向当前节点的父节点
//同时设置原右子节点为黑节点，同时将根节点设置为原右子节点
(root = r).red = false;
else if (pp.left == p)
//父节点的左子节点 == 当前节点
//父节点的左子节点改为原右子节点
pp.left = r;
else
//父节点的右子节点 == 当前节点
//父节点的右子节点改为原右子节点
pp.right = r;
//原右子节点的左子节点指向当前节点
r.left = p;
//当前节点的父节点指向原右子节点
p.parent = r;
}
返回根节点
return root;
}
总结：
- 左旋操作是对当前节点进行顺时针旋转
- 将右子节点变为当前节点父节点，即父子关系互换，且当前节点是作为原右子节点的左子树（排序二叉树的特性：右比左及父节点大）
- 将右子节点的左子树作为当前节点的右子树（排序二叉树的特性：右比左及父节点大）
总的来说可以把左旋理解为把当前节点作为其右子节点的左子树，同时保持排序二叉树的特性
右旋
static <K,V> TreeNode<K,V> rotateRight(TreeNode<K,V> root,
TreeNode<K,V> p) {
//l是当前节点的左子节点，lr是左子节点的右子节点，pp是当前节点的父节点
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)
//如果父节点为空，代表是根节点，则设置为黑节点同时作为根节点
(root = l).red = false;
else if (pp.right == p)
//如果当前节点是父节点的右子节点，则：
//父节点的右子节点指向原左子节点，即原子节点作为当前节点父节点
pp.right = l;
else
//如果当前节点是父节点的左子节点，则：
//父节点的左子节点指向原子节点，即原子节点作为当前节点的父节点
pp.left = l;
//原左子节点的右子节点指向当前节点，即原当前节点作为原左子节点的右子节点
l.right = p;
//当前节点的父子节点指向原左子节点
p.parent = l;
}
//返回根节点
return root;
}
总结：
- 右旋操作是对当前节点进行逆时针旋转
- 将左子节点变为当前节点父节点，即父子关系互换，且当前节点是作为原左子节点的右子树（排序二叉树的特性：右比左及父节点大）
- 将左子节点的右子树作为当前节点的左子树（排序二叉树的特性：左比右及父节点大）
总的来说可以把右旋理解为把当前节点作为其左子节点的右子树，同时保持排序二叉树的特性
网友评论