【Java】红黑树的删除操作概述和代码实现
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了【Java】红黑树的删除操作概述和代码实现，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含5403字，纯文字阅读大概需要8分钟。
内容图文
删除操作概述：
红黑树的删除操作相比于它的插入操作还是比较复杂的，一共涉及到了四种调整的情况，其核心就是因为删除了节点（黑），要保持每条路径上的黑色节点个数相等。
当删除节点为红色时，不用做任何调整；当删除节点时黑色，但它的孩子为红色时，直接把它的孩子变成黑色补上去。
删除情况调整（看兄弟）：
1、删除的时黑色节点，它的孩子也是黑色（或null），它的兄弟节点也是黑色：把兄弟节点变成黑色，指针指向父节点，向上回溯，如果父节点为红色，直接将他变成黑色；
2、删的是黑色节点，该节点的孩子皆为黑色，兄弟也为黑色，但兄弟的右孩子未红色：兄弟的颜色和父节点的颜色交换后，将兄弟红孩的颜色变黑然后以父节点做左旋操作；
3、删的是黑色节点，该节点的孩子皆为黑色，兄弟也为黑色，但兄弟的左孩子为红色：将兄弟的红孩颜色于兄弟的颜色交换，然后以兄弟做右旋操作，然后再如同情况2的方式处理；
4、删除节点时黑色，兄弟是红色：将兄弟和父节点的颜色交换，然后以父节点做左旋操作；
代码实现：
删除操作
private void remove(T data) {
if (this.root == null)
return;
RBNode<T> cur = this.root;
while (cur != null) {
if (cur.getData().compareTo(data) > 0) {
cur = cur.getLeft();
} else if (cur.getData().compareTo(data) < 0) {
cur = cur.getRight();
} else {
break;
}
}
if (cur == null) {
return;
}
if (cur.getLeft() != null && cur.getRight() != null) {
RBNode<T> old = cur;
cur = cur.getLeft();
while (cur.getRight() != null) {
cur = cur.getRight();
}
old.setData(cur.getData());
}
// 删除cur指向的节点
RBNode<T> child = cur.getLeft();
if (child == null) {
child = cur.getRight();
}
if (child != null) {
child.setParent(cur.getParent());
if (cur.getParent() == null) {
this.root = child;
} else {
if (cur.getParent().getLeft() == cur) {
cur.getParent().setLeft(child);
} else {
cur.getParent().setRight(child);
}
}
if (color(cur) == Color.BLACK) {
fixAfterRemove(child);
} else
{
if (cur.getParent() == null) {
this.root = null;
} else {
if (color(cur) == Color.BLACK) {
fixAfterRemove(cur);
}
if (cur.getParent().getLeft() == cur) {
cur.getParent().setLeft(null);
} else {
cur.getParent().setRight(null);
}
}
}
}
}
删除调整：
private void fixAfterRemove(RBNode<T> node) {
while(color(node) == Color.BLACK){//当删除的节点为黑色时 为红色时直接删除 没有影响
if(node == left(parent(node))) { // 左子树删除黑色节点
RBNode<T> brother = right(parent(node));//当前节点在左，那他的兄弟则在右
if(color(brother) == Color.RED){ // 情况4 兄弟时红色 兄弟的孩子时黑色
setColor(brother, Color.BLACK);//交换父兄颜色
setColor(parent(node), Color.RED);
leftRotate(parent(node));//以父亲为根节点左旋
brother = right(parent(node));//更新兄弟节点的指针
}
if(color(left(brother)) == Color.BLACK // 情况1 兄弟的两个孩子是黑色 兄弟黑色
&& color(right(brother)) == Color.BLACK){
setColor(brother, Color.RED);//把兄弟弄成红色 继续向上回溯
node = parent(node);//当前指针更新到父亲
} else {
// 情况3的前半段
if(color(right(brother)) != Color.RED){
setColor(brother, Color.RED);
setColor(left(brother), Color.BLACK);
rightRotate(brother);
brother = right(parent(node));
}
// 统一处理情况2
setColor(brother, color(parent(node)));//父兄颜色交换
setColor(parent(node), Color.BLACK);
setColor(right(brother), Color.BLACK);
leftRotate(parent(node));
break;
}
} else {
// 右子树删除黑色节点
RBNode<T> brother = left(parent(node));
if(color(brother) == Color.RED){ // 情况4
setColor(brother, Color.BLACK);
setColor(parent(node), Color.RED);
rightRotate(parent(node));
brother = left(parent(node));
}
if(color(left(brother)) == Color.BLACK // 情况1
&& color(right(brother)) == Color.BLACK){
setColor(brother, Color.RED);
node = parent(node);
} else {
// 情况3的前半段
if(color(left(brother)) != Color.RED){
setColor(brother, Color.RED);
setColor(right(brother), Color.BLACK);
leftRotate(brother);
brother = left(parent(node));
}
// 统一处理情况2
setColor(brother, color(parent(node)));
setColor(parent(node), Color.BLACK);
setColor(left(brother), Color.BLACK);
rightRotate(parent(node));
break;
}
}
if(node == right(parent(node))){ // 右子树删除黑色节点
RBNode<T> brother =left(parent(node));
if(color(brother) == Color.RED){ // 情况4 兄弟时红色 兄弟的孩子时黑色
setColor(brother, Color.BLACK);//交换父兄颜色
setColor(parent(node), Color.RED);
rightRotate(parent(node));//以父亲为根节点左旋
brother = left(parent(node));//更新兄弟节点的指针
}
if(color(left(brother)) == Color.BLACK // 情况1 兄弟的两个孩子是黑色 兄弟黑色
&& color(right(brother)) == Color.BLACK){
setColor(brother, Color.RED);//把兄弟弄成红色 继续向上回溯
node = parent(node);//当前指针更新到父亲
} else {
// 情况3的前半段
if(color(left(brother)) != Color.RED){
setColor(brother, Color.RED);
setColor(left(brother), Color.BLACK);
leftRotate(brother);
brother =left(parent(node));
}
// 统一处理情况2
setColor(brother, color(parent(node)));//父兄颜色交换
setColor(parent(node), Color.BLACK);
setColor(left(brother), Color.BLACK);
rightRotate(parent(node));
break;
}
} else {
// 右子树删除黑色节点
RBNode<T> brother = right(parent(node));
if(color(brother) == Color.RED){ // 情况4
setColor(brother, Color.BLACK);
setColor(parent(node), Color.RED);
leftRotate(parent(node));
brother = right(parent(node));
}
if(color(left(brother)) == Color.BLACK // 情况1
&& color(right(brother)) == Color.BLACK){
setColor(brother, Color.RED);
node = parent(node);
} else {
// 情况3的前半段
if(color(right(brother)) != Color.RED){
setColor(brother, Color.RED);
setColor(right(brother), Color.BLACK);
rightRotate(brother);
brother = right(parent(node));
}
// 统一处理情况2
setColor(brother, color(parent(node)));
setColor(parent(node), Color.BLACK);
setColor(right(brother), Color.BLACK);
leftRotate(parent(node));
break;
}
}
}
// 在当前这一路遇见红色节点，直接补一个黑色节点
setColor(node, Color.BLACK);
}
内容总结
以上是互联网集市为您收集整理的【Java】红黑树的删除操作概述和代码实现全部内容，希望文章能够帮你解决【Java】红黑树的删除操作概述和代码实现所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。
来源：【匿名】