多说无益! 直接看图
后文 会给出 Java 的代码实现 (完整代码 结合之前的插入)
普通人都能看懂的图解---AVL树(删除) 代码实现
package structure.AVLTree;
public class AVLTree {
private TreeNode root = null; //根节点
public boolean add(int value) {
return add(new TreeNode(value));
}
private boolean add(TreeNode node) {
if (root == null) {
root = node;
return true;
}
TreeNode indexNode = root; //找插入点
TreeNode parentNode = root;
while (indexNode != null) {
parentNode = indexNode; //记录前一个
if (node.value < indexNode.value) {
indexNode = indexNode.leftNode;
} else if (node.value > indexNode.value) {
indexNode = indexNode.rightNode;
} else { //为了简单方便- -就不插入重复元素了
return false;
}
}
//parentNode 就是插入的地方
node.parentNode = parentNode;
if (node.value > parentNode.value) {
parentNode.rightNode = node;
} else parentNode.leftNode = node;
//调节平衡
while (parentNode != null) {
if (parentNode.value > node.value) { //左边插入了
parentNode.bf++;
} else parentNode.bf--; //插在右边
if (parentNode.bf == 0) break; //当前节点左右都有..新插入的点没有造成高度的变化 因此整体是平衡的
if (Math.abs(parentNode.bf) == 2) { //调整完了 也是平衡的
adjustBalance(parentNode);
break;
}
parentNode = parentNode.parentNode; //传递上去
}
return true;
}
private boolean delete(int value) {
TreeNode index = root;
TreeNode next = null; //后继节点
while (index != null) {
if (value < index.value) {
index = index.leftNode;
} else if (value > index.value) {
index = index.rightNode;
} else break; //找到了
}
//index 为 当前要被删除的点
if (index == null) return false; //不存在该点
//分类3
if (index.leftNode != null && index.rightNode != null) {
//同时拥有左右子树 分类3 转为 分类1 或者分类2 (不过这一切的前提 是先将目标转移为后继节点上)
next = findNextNode(index.rightNode);//后继 一定存在 不会为 null
index.value = next.value;
index = next; //目标转移了
}
//是否是分类1呢
if (index.leftNode == null && index.rightNode == null) {
if (index.parentNode == null) { //index为root
root = null;
return true; //当前删除的点是root节点- - 没有值了
}
//叶子节点 (正常删除 调节平衡)
adjustBFForDelete(index);
if (index == index.parentNode.leftNode) index.parentNode.leftNode = null;
else index.parentNode.rightNode = null;
index.parentNode = null; //删除
} else { //分类2
TreeNode kidNode = index.leftNode == null ? index.rightNode : index.leftNode; //起码有一个不为空
//先看index 是不是 root 节点
if (index.parentNode == null) {
this.root = kidNode; //该节点 BF 一定为 0
return true;
}
kidNode.parentNode = index.parentNode;
if (index == index.parentNode.leftNode) { //被删除的点的右节点继承了这个点的位置
kidNode.parentNode.leftNode = kidNode;
} else {
kidNode.parentNode.rightNode = kidNode;
}
index.parentNode = index.leftNode = index.rightNode = null; //删掉了
adjustBFForDelete(kidNode);
}
return true;
}
/**
* 向上计算BF值的变化
*/
private void adjustBFForDelete(TreeNode index) {
TreeNode parent = index.parentNode; //获得其父亲
boolean heightChange = true; //高度变化了
while (parent != null && heightChange) {
//因为之前有个赋值动作...所以可能产生相等..但是默认是后继 所以 只可能是父节点小于等于子节点
if (parent.value <= index.value) { //右边被移除了
parent.bf++;
} else parent.bf--; //左边被移除了
if (Math.abs(parent.bf) == 1) break; //这说明 原本是左右节点都有的,现在虽然移除了一个 但是高度没有发生变化,是平衡的
if (Math.abs(parent.bf) == 2) { //失去平衡了
//因为删除之后会出现2种插入不会出现的不平衡情况...所以对 fixRight 和 left 做了一些调整
heightChange = adjustBalance(parent);
}
parent = parent.parentNode;
}
}
//找到第最后一个比 node 小的点
private TreeNode findNextNode(TreeNode node) {
while (node.leftNode != null) {
node = node.leftNode;
}
return node;
}
//调整平衡
private boolean adjustBalance(TreeNode unBalanceNode) {
if (unBalanceNode.bf == 2) return fixLeftLost(unBalanceNode);
else return fixRightLost(unBalanceNode);
}
/**
* 右旋
*/
private void rightRotate(TreeNode unBalanceNode) {
final TreeNode leftNode = unBalanceNode.leftNode; //先拿出左边的节点
// left节点先变成顶替 unbal的位置
leftNode.parentNode = unBalanceNode.parentNode;
if (leftNode.parentNode != null) {
if (leftNode.parentNode.value > leftNode.value) {
leftNode.parentNode.leftNode = leftNode;
} else leftNode.parentNode.rightNode = leftNode;
} else root = leftNode; //新的头节点
//调整 unbal 和 left 的右节点的关系
unBalanceNode.leftNode = leftNode.rightNode;
if (unBalanceNode.leftNode != null) unBalanceNode.leftNode.parentNode = unBalanceNode; //调整关系
//调整 left 和 unbal的关系
unBalanceNode.parentNode = leftNode;
leftNode.rightNode = unBalanceNode;
}
/**
* 左旋
*/
private void leftRotate(TreeNode unBalanceNode) {
final TreeNode rightNode = unBalanceNode.rightNode; //先拿出左边的节点
// right节点先变成顶替 unbal的位置
rightNode.parentNode = unBalanceNode.parentNode;
if (rightNode.parentNode != null) {
if (rightNode.parentNode.value > rightNode.value) {
rightNode.parentNode.leftNode = rightNode;
} else rightNode.parentNode.rightNode = rightNode;
} else root = rightNode; //新的头节点
//调整 unbal 和 right 的左节点的关系
unBalanceNode.rightNode = rightNode.leftNode;
if (unBalanceNode.rightNode != null) unBalanceNode.rightNode.parentNode = unBalanceNode; //调整关系
//调整 right 和 unbal的关系
unBalanceNode.parentNode = rightNode;
rightNode.leftNode = unBalanceNode;
}
/**
* 第一个 L (左边失平衡)
*/
private boolean fixLeftLost(TreeNode unBalanceNode) {
//先处理最简单的 LL
final TreeNode leftNode = unBalanceNode.leftNode;
if (leftNode.bf == 1) { //LL
rightRotate(unBalanceNode); //右旋处理
//最后的因子变化
unBalanceNode.bf = leftNode.bf = 0; //都平衡了
} else if (leftNode.bf == -1) { //LR
//操作都一样 最后的因子变化 会有区别 (先左后右)
leftRotate(leftNode);
rightRotate(unBalanceNode);
//调整完了之后 需要做判断的点 3种情况都是 unBalance的父节点
switch (unBalanceNode.parentNode.bf) {
case 0:
unBalanceNode.bf = leftNode.bf = 0;
break;
case 1:
unBalanceNode.bf = -1;
leftNode.bf = 0;
break;
case -1:
unBalanceNode.bf = 0;
leftNode.bf = 1;
break;
}
unBalanceNode.parentNode.bf = 0;
} else { //这种情况 只会在删除之后出现 且leftNode 一定有 左右节点
unBalanceNode.bf = 1;
leftNode.bf = -1;
rightRotate(unBalanceNode);
return false;
}
return true;
}
/**
* 第一个 R (右边失平衡)
*/
private boolean fixRightLost(TreeNode unBalanceNode) {
final TreeNode rightNode = unBalanceNode.rightNode;
if (rightNode.bf == -1) { //RR
leftRotate(unBalanceNode); //进行左旋转
//调整因子
unBalanceNode.bf = rightNode.bf = 0;
} else if (rightNode.bf == 1) { //RL
//操作都一样 最后的因子变化 会有区别 (先右后左)
rightRotate(rightNode);
leftRotate(unBalanceNode);
//调整完了之后 需要做判断的点 3种情况都是 unBalance的父节点
switch (unBalanceNode.parentNode.bf) {
case 0:
unBalanceNode.bf = rightNode.bf = 0;
break;
case 1:
unBalanceNode.bf = 0;
rightNode.bf = -1;
break;
case -1:
unBalanceNode.bf = 1;
rightNode.bf = 0;
break;
}
unBalanceNode.parentNode.bf = 0;
} else { //这种情况 只会在删除之后出现 且leftNode 一定有 左右节点
unBalanceNode.bf = -1;
rightNode.bf = 1;
leftRotate(unBalanceNode);
return false;
}
return true;
}
/**
* 获得树的中序遍历
*/
public void printMidOrder() {
printMidOrder(root);
System.out.println();
}
private void printMidOrder(TreeNode treeNode) {
if (treeNode == null) return;
printMidOrder(treeNode.leftNode);
System.out.print(" " + treeNode.value);
printMidOrder(treeNode.rightNode);
}
private static class TreeNode {
public TreeNode rightNode;
public TreeNode leftNode;
public TreeNode parentNode;
public int bf;
public int value;
public TreeNode(int value) {
this.value = value;
}
}
public static void main(String[] args) {
final AVLTree root = new AVLTree();
root.add(10);
root.add(20);
root.add(30);
root.add(50);
root.add(60);
root.add(9);
root.add(8);
root.add(7);
root.add(6);
root.printMidOrder();
root.delete(20);
root.printMidOrder();
root.delete(10);
root.printMidOrder();
root.add(35);
root.printMidOrder();
root.delete(50);
root.printMidOrder();
root.delete(60);
root.printMidOrder();
root.delete(8);
root.printMidOrder();
root.delete(30);
root.printMidOrder();
root.delete(6);
root.printMidOrder();
}
}
感谢观看 (如果有的话…)
如有错误…请指出 …
![Java String.format方法的简单使用[图]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)