输入平衡操作
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;
}
总结:
- 右旋操作是对当前节点进行逆时针旋转
- 将左子节点变为当前节点父节点,即父子关系互换,且当前节点是作为原左子节点的右子树(排序二叉树的特性:右比左及父节点大)
- 将左子节点的右子树作为当前节点的左子树(排序二叉树的特性:左比右及父节点大)
总的来说可以把右旋理解为把当前节点作为其左子节点的右子树,同时保持排序二叉树的特性
网友评论