多說無益! 直接看圖
後文 會給出 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=)