AVL樹詳解
- 1. 簡介
- 2. 插入
-
- 2.1 單向右旋平衡處理LL
- 2.2 單向左旋平衡處理RR
- 2.3 雙向旋轉（先左後右）平衡處理LR
- 2.4 雙向旋轉（先右後左）平衡處理RL
- 3. 删除
- 4 java代碼例子
相關文章連結：
相關文章連結 第2節 資料結構
觀前提示：
本文所使用的Eclipse版本為Photon Release (4.8.0)，IDEA版本為ultimate 2019.1，JDK版本為1.8.0_141，Tomcat版本為9.0.12。
1. 簡介
AVL樹是最先發明的自平衡二叉查找樹。在AVL樹中任何節點的兩個子樹的高度最大差别為1，是以它也被稱為高度平衡樹。
特點
- 本身首先是一棵二叉搜尋樹。
- 帶有平衡條件：每個結點的左右子樹的高度之差的絕對值（平衡因子）最多為1。
平衡因子： 某結點的左子樹與右子樹的高度(深度)差即為該結點的平衡因子（BF,Balance Factor）。平衡二叉樹上所有結點的平衡因子隻可能是 -1，0 或 1。
2. 插入
這裡隻介紹插入節點後破壞平衡所做的旋轉操作。
2.1 單向右旋平衡處理LL
在左子樹（L）的左孩子（L）插入節點失衡，需要進行單向右旋平衡處理LL。
2.2 單向左旋平衡處理RR
在右子樹（R）的右孩子（R）插入節點失衡，需要進行單向左旋平衡處理RR。
2.3 雙向旋轉（先左後右）平衡處理LR
在左子樹（L）的右孩子（R）插入節點失衡，需要進行雙向旋轉（先左後右）平衡處理LR。
2.4 雙向旋轉（先右後左）平衡處理RL
在右子樹（R）的左孩子（L）插入節點失衡，需要進行雙向旋轉（先右後左）平衡處理RL。
3. 删除
AVL樹删除操作步驟如下
- 搜尋給定的key，确定其是否在樹中。
- 如果不在樹中，傳回null；如果在樹中，執行标準的BST删除操作，并傳回該删除的結點。
- 檢查被删除結點的所有祖先結點是否平衡，如果不平衡，則執行重平衡操作。
BST删除操作三種情況
- 當該節點為葉子節點，則讓該節點的父節點指向其變為NULL，然後釋放節點。
-
當該節點不是葉子節點，但左子樹或者右子樹為空，則：
（1）若左子樹為空，則讓該節點父節點指向其右節點。
（2）若右子樹為空，則讓該節點父節點指向其左節點。
-
當該節點不是葉子節點，且左子樹和右子樹都不為空，則：
（1）在該節點的左子樹中找到最大節點Lmax（該節點必然是一個葉子節點）或者右子樹中的最小節點Rmin，取出節點的值value，并删除該節點。
（2）将value的值賦到要删除的節點。
4 java代碼例子
AVL樹 AVLTree.java
package TestTree.AVL;
public class AVLTree {
private Integer root;
private AVLTree left;
private AVLTree right;
private Integer height;
public AVLTree(Integer root) {
this.root = root;
}
public Integer getRoot() {
return root;
}
public void setRoot(Integer root) {
this.root = root;
}
public AVLTree getLeft() {
return left;
}
public void setLeft(AVLTree left) {
this.left = left;
}
public AVLTree getRight() {
return right;
}
public void setRight(AVLTree right) {
this.right = right;
}
public Integer getHeight() {
return height;
}
/**
* 擷取指定節點深度
* @param node
* @return
*/
public static Integer getHeight(AVLTree node){
if(node == null){
return 0;
}
return node.height;
}
public void setHeight(Integer height) {
this.height = height;
}
/**
* 指定節點深度指派
* @param node
* @param height
*/
public static void setHeight(AVLTree node, Integer height) {
if(node == null){
return;
}
node.height = height;
}
/**
* 擷取最小節點
* @param node
* @return
*/
public static AVLTree getMinNode(AVLTree node){
if(node != null && node.getLeft() == null){
return node;
}
return getMinNode(node.getLeft());
}
}
樹操作工具類 TreeOperateUtil.java
package TestTree.AVL;
/**
* 樹操作工具類
* @author jjy
* @date 2020-10-19
*/
public class TreeOperateUtil {
/**
* 插入節點
* @param node
* @param data
* @return
*/
public static AVLTree insert(AVLTree node, int data){
// 根節點沒有資料，直接插入
if(node == null || node.getRoot() == null){
node = new AVLTree(data);
node.setHeight(1);
return node;
}
if(node.getRoot() > data){
node.setLeft(insert(node.getLeft(), data));
} else {
node.setRight(insert(node.getRight(), data));
}
// 更新深度
node.setHeight(1 + Math.max(AVLTree.getHeight(node.getLeft()), AVLTree.getHeight(node.getRight())));
int balanceFactor = getBalanceFactor(node);
// LL
if(balanceFactor == 2 && getBalanceFactor(node.getLeft()) > 0 ){
System.out.println("-------------LL旋轉-------------");
return LLRotate(node);
}
// LR
if(balanceFactor == 2 && getBalanceFactor(node.getLeft()) < 0){
System.out.println("-------------LR旋轉-------------");
return LRRotate(node);
}
// RR
if(balanceFactor == -2 && getBalanceFactor(node.getRight()) < 0){
System.out.println("-------------RR旋轉-------------");
return RRRotate(node);
}
// RL
if(balanceFactor == -2 && getBalanceFactor(node.getRight()) > 0){
System.out.println("-------------RL旋轉-------------");
return RLRotate(node);
}
return node;
}
/**
* 删除節點
* @param node
* @param data
* @return
*/
public static AVLTree remove(AVLTree node, int data){
if(node == null){
return null;
}
if(node.getRoot() > data){
node.setLeft(remove(node.getLeft(), data));
} else if( node.getRoot() < data){
node.setRight(remove(node.getRight(), data));
} else {
if(node.getLeft() == null) {
// 沒有左子樹
node = node.getRight();
} else if(node.getRight() == null) {
// 沒有右子樹
node = node.getLeft();
} else {
// 左右子樹均不為空，取右子樹最小值（或者左子樹最大值），替換目前要删除的節點
AVLTree minNode = AVLTree.getMinNode(node.getRight());
node.setRight(remove(node.getRight(), minNode.getRoot()));
node.setRoot(minNode.getRoot());
}
}
// 隻有根節點，删除後為空
if(node == null){
return null;
}
// 更新深度
node.setHeight(1 + Math.max(AVLTree.getHeight(node.getLeft()), AVLTree.getHeight(node.getRight())));
int balanceFactor = getBalanceFactor(node);
// LL
if(balanceFactor == 2 && getBalanceFactor(node.getLeft()) > 0 ){
System.out.println("-------------LL旋轉-------------");
return LLRotate(node);
}
// LR
if(balanceFactor == 2 && getBalanceFactor(node.getLeft()) < 0){
System.out.println("-------------LR旋轉-------------");
return LRRotate(node);
}
// RR
if(balanceFactor == -2 && getBalanceFactor(node.getRight()) < 0){
System.out.println("-------------RR旋轉-------------");
return RRRotate(node);
}
// RL
if(balanceFactor == -2 && getBalanceFactor(node.getRight()) > 0){
System.out.println("-------------RL旋轉-------------");
return RLRotate(node);
}
return node;
}
/**
* LL旋轉
* @param node
* @return
*/
private static AVLTree LLRotate(AVLTree node){
AVLTree result = node.getLeft();
node.setLeft(result.getRight());
result.setRight(node);
AVLTree.setHeight(result.getLeft(), getTreeDepth(result.getLeft()));
AVLTree.setHeight(result.getRight(), getTreeDepth(result.getRight()));
AVLTree.setHeight(result, getTreeDepth(result));
return result;
}
/**
* RR旋轉
* @param node
* @return
*/
private static AVLTree RRRotate(AVLTree node){
AVLTree result = node.getRight();
node.setRight(result.getLeft());
result.setLeft(node);
AVLTree.setHeight(result.getLeft(), getTreeDepth(result.getLeft()));
AVLTree.setHeight(result.getRight(), getTreeDepth(result.getRight()));
AVLTree.setHeight(result, getTreeDepth(result));
return result;
}
/**
* LR旋轉
* @param node
* @return
*/
private static AVLTree LRRotate(AVLTree node){
node.setLeft(RRRotate(node.getLeft()));
return LLRotate(node);
}
/**
* RL旋轉
* @param node
* @return
*/
private static AVLTree RLRotate(AVLTree node){
node.setRight(LLRotate(node.getRight()));
return RRRotate(node);
}
/**
* 擷取平衡因子
* @param node
* @return
*/
private static int getBalanceFactor(AVLTree node){
return AVLTree.getHeight(node.getLeft()) - AVLTree.getHeight(node.getRight());
}
/**
* 擷取樹的深度
* @param node
* @return
*/
private static int getTreeDepth(AVLTree node){
if(node == null || node.getRoot() == null){
return 0;
}
AVLTree left = node.getLeft();
AVLTree right = node.getRight();
return Math.max(getTreeDepth(left), getTreeDepth(right)) + 1;
}
}
測試類 TestAVL.java
package TestTree.AVL;
import java.util.Arrays;
import java.util.List;
public class TestAVL {
public static void main(String[] args) {
System.out.println("-------------插入操作-------------");
testInsert();
System.out.println("-------------第一組删除操作-------------");
testDelete();
System.out.println("-------------第二組删除操作-------------");
testDelete2();
}
/**
* 測試插入節點
*/
private static void testInsert(){
AVLTree t1 = getTestData();
System.out.println("-------------插入前-------------");
TraversalUtil.init();
List<Integer> preList = TraversalUtil.preOrder(t1);
System.out.println("先序排列結果為：");
System.out.println(Arrays.toString(preList.toArray()));
TraversalUtil.init();
List<Integer> inList = TraversalUtil.inOrder(t1);
System.out.println("中序排列結果為：");
System.out.println(Arrays.toString(inList.toArray()));
TraversalUtil.init();
List<Integer> postList = TraversalUtil.postOrder(t1);
System.out.println("後序排列結果為：");
System.out.println(Arrays.toString(postList.toArray()));
System.out.println("-------------1.插入70-------------");
t1 = TreeOperateUtil.insert(t1, 70);
TraversalUtil.init();
preList = TraversalUtil.preOrder(t1);
System.out.println("先序排列結果為：");
System.out.println(Arrays.toString(preList.toArray()));
TraversalUtil.init();
inList = TraversalUtil.inOrder(t1);
System.out.println("中序排列結果為：");
System.out.println(Arrays.toString(inList.toArray()));
TraversalUtil.init();
postList = TraversalUtil.postOrder(t1);
System.out.println("後序排列結果為：");
System.out.println(Arrays.toString(postList.toArray()));
t1 = getTestData();
System.out.println("-------------2.插入130-------------");
t1 = TreeOperateUtil.insert(t1, 130);
TraversalUtil.init();
preList = TraversalUtil.preOrder(t1);
System.out.println("先序排列結果為：");
System.out.println(Arrays.toString(preList.toArray()));
TraversalUtil.init();
inList = TraversalUtil.inOrder(t1);
System.out.println("中序排列結果為：");
System.out.println(Arrays.toString(inList.toArray()));
TraversalUtil.init();
postList = TraversalUtil.postOrder(t1);
System.out.println("後序排列結果為：");
System.out.println(Arrays.toString(postList.toArray()));
t1 = getTestData();
System.out.println("-------------3.插入85-------------");
t1 = TreeOperateUtil.insert(t1, 85);
TraversalUtil.init();
preList = TraversalUtil.preOrder(t1);
System.out.println("先序排列結果為：");
System.out.println(Arrays.toString(preList.toArray()));
TraversalUtil.init();
inList = TraversalUtil.inOrder(t1);
System.out.println("中序排列結果為：");
System.out.println(Arrays.toString(inList.toArray()));
TraversalUtil.init();
postList = TraversalUtil.postOrder(t1);
System.out.println("後序排列結果為：");
System.out.println(Arrays.toString(postList.toArray()));
t1 = getTestData();
System.out.println("-------------4.插入115-------------");
t1 = TreeOperateUtil.insert(t1, 115);
TraversalUtil.init();
preList = TraversalUtil.preOrder(t1);
System.out.println("先序排列結果為：");
System.out.println(Arrays.toString(preList.toArray()));
TraversalUtil.init();
inList = TraversalUtil.inOrder(t1);
System.out.println("中序排列結果為：");
System.out.println(Arrays.toString(inList.toArray()));
TraversalUtil.init();
postList = TraversalUtil.postOrder(t1);
System.out.println("後序排列結果為：");
System.out.println(Arrays.toString(postList.toArray()));
}
/**
* 測試資料
* 100
* / \
* 90 110
* / \
* 80 120
* @return
*/
private static AVLTree getTestData(){
AVLTree t1 = new AVLTree(100);
AVLTree t2 = new AVLTree(90);
AVLTree t3 = new AVLTree(110);
AVLTree t4 = new AVLTree(80);
AVLTree t5 = new AVLTree(120);
t3.setHeight(1);
t4.setHeight(1);
t5.setHeight(1);
t2.setLeft(t4);
t2.setHeight(2);
t3.setRight(t5);
t2.setHeight(2);
t1.setLeft(t2);
t1.setRight(t3);
t1.setHeight(3);
return t1;
}
/**
* 測試删除節點
*/
private static void testDelete(){
AVLTree t1 = getTestDeleteData1();
System.out.println("-------------删除前-------------");
TraversalUtil.init();
List<Integer> preList = TraversalUtil.preOrder(t1);
System.out.println("先序排列結果為：");
System.out.println(Arrays.toString(preList.toArray()));
TraversalUtil.init();
List<Integer> inList = TraversalUtil.inOrder(t1);
System.out.println("中序排列結果為：");
System.out.println(Arrays.toString(inList.toArray()));
TraversalUtil.init();
List<Integer> postList = TraversalUtil.postOrder(t1);
System.out.println("後序排列結果為：");
System.out.println(Arrays.toString(postList.toArray()));
System.out.println("-------------1.删除80-------------");
t1 = TreeOperateUtil.remove(t1, 80);
TraversalUtil.init();
preList = TraversalUtil.preOrder(t1);
System.out.println("先序排列結果為：");
System.out.println(Arrays.toString(preList.toArray()));
TraversalUtil.init();
inList = TraversalUtil.inOrder(t1);
System.out.println("中序排列結果為：");
System.out.println(Arrays.toString(inList.toArray()));
TraversalUtil.init();
postList = TraversalUtil.postOrder(t1);
System.out.println("後序排列結果為：");
System.out.println(Arrays.toString(postList.toArray()));
t1 = getTestDeleteData1();
System.out.println("-------------2.删除120-------------");
t1 = TreeOperateUtil.remove(t1, 120);
TraversalUtil.init();
preList = TraversalUtil.preOrder(t1);
System.out.println("先序排列結果為：");
System.out.println(Arrays.toString(preList.toArray()));
TraversalUtil.init();
inList = TraversalUtil.inOrder(t1);
System.out.println("中序排列結果為：");
System.out.println(Arrays.toString(inList.toArray()));
TraversalUtil.init();
postList = TraversalUtil.postOrder(t1);
System.out.println("後序排列結果為：");
System.out.println(Arrays.toString(postList.toArray()));
t1 = getTestDeleteData1();
System.out.println("-------------3.删除95-------------");
t1 = TreeOperateUtil.remove(t1, 95);
TraversalUtil.init();
preList = TraversalUtil.preOrder(t1);
System.out.println("先序排列結果為：");
System.out.println(Arrays.toString(preList.toArray()));
TraversalUtil.init();
inList = TraversalUtil.inOrder(t1);
System.out.println("中序排列結果為：");
System.out.println(Arrays.toString(inList.toArray()));
TraversalUtil.init();
postList = TraversalUtil.postOrder(t1);
System.out.println("後序排列結果為：");
System.out.println(Arrays.toString(postList.toArray()));
t1 = getTestDeleteData1();
System.out.println("-------------4.删除105-------------");
t1 = TreeOperateUtil.remove(t1, 105);
TraversalUtil.init();
preList = TraversalUtil.preOrder(t1);
System.out.println("先序排列結果為：");
System.out.println(Arrays.toString(preList.toArray()));
TraversalUtil.init();
inList = TraversalUtil.inOrder(t1);
System.out.println("中序排列結果為：");
System.out.println(Arrays.toString(inList.toArray()));
TraversalUtil.init();
postList = TraversalUtil.postOrder(t1);
System.out.println("後序排列結果為：");
System.out.println(Arrays.toString(postList.toArray()));
t1 = getTestDeleteData1();
System.out.println("-------------5.删除100-------------");
t1 = TreeOperateUtil.remove(t1, 100);
TraversalUtil.init();
preList = TraversalUtil.preOrder(t1);
System.out.println("先序排列結果為：");
System.out.println(Arrays.toString(preList.toArray()));
TraversalUtil.init();
inList = TraversalUtil.inOrder(t1);
System.out.println("中序排列結果為：");
System.out.println(Arrays.toString(inList.toArray()));
TraversalUtil.init();
postList = TraversalUtil.postOrder(t1);
System.out.println("後序排列結果為：");
System.out.println(Arrays.toString(postList.toArray()));
}
/**
* 測試資料
* 100
* / \
* 90 110
* / \ / \
* 80 95 105 120
* / \
* 70 130
* @return
*/
private static AVLTree getTestDeleteData1(){
AVLTree t1 = new AVLTree(100);
AVLTree t2 = new AVLTree(90);
AVLTree t3 = new AVLTree(110);
AVLTree t4 = new AVLTree(80);
AVLTree t5 = new AVLTree(95);
AVLTree t6 = new AVLTree(105);
AVLTree t7 = new AVLTree(120);
AVLTree t8 = new AVLTree(70);
AVLTree t9 = new AVLTree(130);
t5.setHeight(1);
t6.setHeight(1);
t8.setHeight(1);
t9.setHeight(1);
t4.setLeft(t8);
t4.setHeight(2);
t7.setRight(t9);
t7.setHeight(2);
t2.setLeft(t4);
t2.setRight(t5);
t2.setHeight(3);
t3.setLeft(t6);
t3.setRight(t7);
t3.setHeight(3);
t1.setLeft(t2);
t1.setRight(t3);
t1.setHeight(4);
return t1;
}
/**
* 測試删除節點
*/
private static void testDelete2(){
AVLTree t1 = getTestDeleteData2();
System.out.println("-------------删除前-------------");
TraversalUtil.init();
List<Integer> preList = TraversalUtil.preOrder(t1);
System.out.println("先序排列結果為：");
System.out.println(Arrays.toString(preList.toArray()));
TraversalUtil.init();
List<Integer> inList = TraversalUtil.inOrder(t1);
System.out.println("中序排列結果為：");
System.out.println(Arrays.toString(inList.toArray()));
TraversalUtil.init();
List<Integer> postList = TraversalUtil.postOrder(t1);
System.out.println("後序排列結果為：");
System.out.println(Arrays.toString(postList.toArray()));
System.out.println("-------------1.删除95-------------");
t1 = TreeOperateUtil.remove(t1, 95);
TraversalUtil.init();
preList = TraversalUtil.preOrder(t1);
System.out.println("先序排列結果為：");
System.out.println(Arrays.toString(preList.toArray()));
TraversalUtil.init();
inList = TraversalUtil.inOrder(t1);
System.out.println("中序排列結果為：");
System.out.println(Arrays.toString(inList.toArray()));
TraversalUtil.init();
postList = TraversalUtil.postOrder(t1);
System.out.println("後序排列結果為：");
System.out.println(Arrays.toString(postList.toArray()));
t1 = getTestDeleteData2();
System.out.println("-------------2.删除105-------------");
t1 = TreeOperateUtil.remove(t1, 105);
TraversalUtil.init();
preList = TraversalUtil.preOrder(t1);
System.out.println("先序排列結果為：");
System.out.println(Arrays.toString(preList.toArray()));
TraversalUtil.init();
inList = TraversalUtil.inOrder(t1);
System.out.println("中序排列結果為：");
System.out.println(Arrays.toString(inList.toArray()));
TraversalUtil.init();
postList = TraversalUtil.postOrder(t1);
System.out.println("後序排列結果為：");
System.out.println(Arrays.toString(postList.toArray()));
}
/**
* 測試資料
* 100
* / \
* 90 110
* / \ / \
* 80 95 105 120
* \ /
* 85 115
* @return
*/
private static AVLTree getTestDeleteData2(){
AVLTree t1 = new AVLTree(100);
AVLTree t2 = new AVLTree(90);
AVLTree t3 = new AVLTree(110);
AVLTree t4 = new AVLTree(80);
AVLTree t5 = new AVLTree(95);
AVLTree t6 = new AVLTree(105);
AVLTree t7 = new AVLTree(120);
AVLTree t8 = new AVLTree(85);
AVLTree t9 = new AVLTree(115);
t5.setHeight(1);
t6.setHeight(1);
t8.setHeight(1);
t9.setHeight(1);
t4.setRight(t8);
t4.setHeight(2);
t7.setLeft(t9);
t7.setHeight(2);
t2.setLeft(t4);
t2.setRight(t5);
t2.setHeight(3);
t3.setLeft(t6);
t3.setRight(t7);
t3.setHeight(3);
t1.setLeft(t2);
t1.setRight(t3);
t1.setHeight(4);
return t1;
}
}
測試結果為