Java詳解AVL樹的應用
一.什麼是AVL樹
在認識AVL樹之前我們先認識一下什麼是二叉搜索樹:
1.二叉搜索樹
二叉搜索樹又稱為二叉排序樹,二叉搜索樹滿足所有的左孩子節點都小於其根節點的值,所有的右孩子節點都大於其根節點的值,二叉搜索樹上的每一棵子樹都是一棵二叉搜索樹,因此二叉搜索樹通過中序遍歷可以獲得一個有序的序列(由小到大);
類似於這樣的樹就是一棵二叉搜索樹;
2.為什麼引入瞭AVL樹
二叉搜索樹看似很美好,但其卻有一些缺陷.對於二叉搜索樹而言,是和查找相關的，而不論是查找還是刪除,都需要先進行查找,也就是對整棵樹來進行遍歷,而對有n個結點的二叉搜索樹，若每個元素查找的概率相等，則二叉搜索樹平均查找長度是結點在二叉搜索樹的深度函數,也就是結點越深，則比較次數越多.最優的情況下是：二叉搜索樹為完全二叉樹，其平均比較次數為： l o g 2 n log_2{n} log2n,但是如果二叉搜索樹退化成瞭一棵單分支的樹,其平均比較次數為：n/2,就是最差的情況瞭
這就相當於是一個順序表的查找瞭,這樣二叉搜索樹的優勢就完全消失瞭,因此就引入瞭AVL樹!
3.什麼是AVL樹
AVL樹又稱自平衡二叉查找樹,是高度平衡的二叉搜索樹,就是在二叉搜索樹的基礎上進行瞭優化,既當向二叉搜索樹中插入新結點後，保證每個結點的左右子樹高度之差的絕對值不超過1(需要對樹中的結點進行調整),也就是降低樹的高度,這樣就可以減少平均搜索長度瞭,因此AVL樹滿足它的左右子樹都是AVL樹,左右子樹高度之差(簡稱平衡因子)的絕對值不超過1(-1/0/1),這就是AVL樹的優勢所在,因此如果一棵二叉搜索樹是高度平衡的，它就是AVL樹。如果它有n個結點，其高度可保持在 ，搜索時間復雜度O( l o g 2 n log_2{n} log2n)!!!
平衡因子 = 右子樹的高度 – 左子樹的高度
二.自己構造AVL樹
這裡的構造還是和二叉搜索樹的構造差不多的，隻不過在這裡插入元素的話就需要考慮平衡因子的事情瞭，因為一定要保證插入元素後此樹還是一棵AVL樹，就需要進行相關調整，這裡就先不過多介紹瞭，下面再詳細介紹，先來構造一棵簡單的AVL樹：
public class AVLTree {
static class TreeNode{
//內部類，表示AVL樹的每個節點
//val值
public int val;
//左孩子的引用
public TreeNode left;
//右孩子的引用
public TreeNode right;
//父親節點的引用
public TreeNode parent;
//平衡因子(每個節點都有）
public int bf;
public TreeNode(int val){
this.val = val;
}
}
//根節點
public TreeNode root;
public boolean insert(int val){
}
}
這樣一棵簡單的AVL樹就構造好瞭，下面就來寫一下AVL樹的插入！
三.AVL樹的插入和刪除
1.插入
首先就是將節點插進來，和二叉搜索樹一樣，先隻看位置在哪，不關註平衡因子
這個為要插入節點：
TreeNode node = new TreeNode(val);
if(root == null){
//沒有根節點，要插入的就是根節點
root = node;
return true;
}
//記錄每個節點的父節點
TreeNode parent = null;
//要移動的代節點
TreeNode cur = root;
//根據val的值和root進行比較來確定應該插入節點的位置
while (cur != null){
if(cur.val > val){
//大於證明此節點應在左子樹
parent = cur;
cur = cur.left;
}else if(cur.val < val){
//大於證明此節點應在右子樹
parent = cur;
cur = cur.right;
}else {
//不能有值一樣的節點
return false;
}
}
//此時cur為空，需要找到對應的位置
if(parent.val > val){
parent.left = node;
}else{
parent.right = node;
}
此時節點就已經插進來瞭，此時就需要看其每個節點的平衡因子瞭
//而此時就需要對樹進行平衡因子的調整瞭，保證樹是高度平衡的
//再反著回去寫
node.parent = parent;
cur = node;
//當父親節點一直存在的時候，就表示沒有調到根節點就需要繼續調整
while(parent != null){
if(cur == parent.right){
//在右邊右樹高度加一，因此bf+1
parent.bf++;
}else{
//再左邊，左樹高度加一，因此bf-1
parent.bf--;
}
//在這裡就要進行判斷瞭，如果此時的父親節點如果平衡因子為0瞭，那麼就不需要再往上走瞭，因為上面的都是平衡的
if(parent.bf == 0){
return true;
}else if(parent.bf == -1 || parent.bf == 1){
//此時父親節點的平衡因子為1、-1
//此時表示當前樹平衡瞭，但是不表示整棵樹都平衡瞭，因此還需要繼續往上走
cur = parent;
parent = cur.parent;
}else{
//此時父親節點的平衡因子為2、-2
if(parent.bf == 2){
//此時右樹高 需要降低右樹的高度
if(cur.bf == 1){
//左單旋
rotateLeft(parent);
}else{
//右左雙旋
rotateRL(parent);
}
}else{
//此時左樹高，需要降低左樹的高度
if(cur.bf == 1){
//左右雙旋
rotateLR(parent);
}else{
//右單旋
rotateRight(parent);
}
}
//調整完就平衡瞭
break;
}
}
這是當前會出現的問題：
先來討論一下調整平衡因子會出現的一些情況，來分別看一下：
首先是平衡因子調整為0瞭，那麼就不需要再往上走瞭，因為上面的都是平衡的，當前的父親節點的平衡因子為0瞭表示插入的這個元素隻影響到瞭這一棵樹，上面是沒有影響的，因此是0的話就結束瞭
因此是0的話就表示當前已經結束瞭，不需要再往上瞭，其他變為0 的情況也是一樣的這裡就不細畫瞭
而如果是1或者-1的話，表示當前樹平衡瞭，但是不表示整棵樹平衡瞭，因此需要再往上走；
而如果是2或者-2的話，會以下四種情況，再來分別看一下：
1.1.右單旋
此時左樹高，需要降低左樹的高度，也就是右旋（parent.bf = -2,cur.bf = -1）：
也就是如下的效果：
也就是這樣的調整過程：
下面寫一下代碼：
private void rotateRight(TreeNode parent){
//右單旋
//此時parent的平衡因子為-2，cur的平衡因子為-1
TreeNode cur = parent.left;
//記錄cur的右節點
TreeNode curR = cur.right;
parent.left = curR;
cur.right = parent;
//如果cur有右節點需要賦給parent的左節點，但是沒有就不需要給瞭
if(curR != null){
curR.parent = parent;
}
//然後將cur的右孩子改變為parent
//需要記錄parent的根節點
TreeNode pParent = parent.parent;
parent.parent = cur;
//檢查當前是不是根節點，不是根節點需要看是左子樹，還是右子樹
if(pParent != null){
//改變之前的指向
cur.parent = pParent;
if(parent == pParent.right){
pParent.right = cur;
}else{
pParent.left = cur;
}
}else{
//此時parent就是root，因為沒有根節點
root = cur;
root.parent = null;
}
//最後記得一定要修改平衡因子
parent.bf = 0;
cur.bf = 0;
}
這樣一個“簡單”的右單旋就結束瞭~
1.2.左單旋
這種情況就是最開始的情況瞭
此時右樹高，需要降低右樹的高度，也就是左旋（parent.bf = 2,cur.bf = 1）：
也就是如下的效果：
也就是這樣的調整過程：
代碼如下：
private void rotateLeft(TreeNode parent){
//左單旋
//此時parent平衡因子為2，cur的平衡因子為1
//需要記錄父親節點
TreeNode pParent = parent.parent;
TreeNode cur = parent.right;
//記錄cur的左節點
TreeNode curL = cur.left;
parent.right = curL;
cur.left = parent;
//判斷左節點是不是空的，如果是空的就不需要管瞭，不是空的就需要將parent右節點指向它，並且它的父親節點為parent
if(curL != null){
//改變指向
curL.parent = parent;
}
//改變cur的指向
parent.parent = cur;
//判斷如果pParent不為空，就表示parent不是root，就需要看其是左孩子還是右孩子
if(pParent != null){
cur.parent = pParent;
if(parent == pParent.right){
pParent.right = cur;
}else{
pParent.left = cur;
}
}else{
//是根節點
root = cur;
root.parent = null;
}
cur.bf = 0;
parent.bf = 0;
}
這樣一個“簡單”的左單旋就結束瞭~
1.3.左右雙旋
此時左樹高，需要降低左樹的高度，（parent.bf = -2,cur.bf = 1）：
而此時僅通過單旋是無法完成的，需要通過兩種旋轉才能完成：
上面左單旋和右單旋已經介紹過瞭，這裡就不詳細介紹瞭，
先左旋：
此時修改的平衡因子是沒有用的
再右旋：
兩次旋轉之後隻需要進行平衡因子的改變就可以瞭，
通過觀察curR的平衡因子，會決定最後其他節點的平衡因子
代碼如下：
private void rotateLR(TreeNode parent){
//左右雙旋
TreeNode cur = parent.left;
TreeNode curR = cur.right;
//此時就需要看curR的平衡因子，再決定最後其他節點的平衡因子
int bf = curR.bf;
//先調用左旋再右旋
rotateLeft(cur);
rotateRight(parent);
//這裡通過規律可以得到當curR的bf值不同的時候，其需要改變的bf值也是不同的，因此裡就需要做出修改
if(bf == -1){
//當bf為-1時，其應修改的如下
curR.bf = 0;
cur.bf = 0;
parent.bf = 1;
}else if(bf == 1){
//當bf為1時，其應修改的如下
curR.bf = 0;
cur.bf = -1;
parent.bf = 0;
}
//另外當bf為0的時候就已經平衡瞭，就不需要改瞭，因為在兩次旋轉的時候就已經將其改為0瞭
}
這樣一個左右雙旋就結束瞭~
1.4.右左雙旋
此時右樹高，需要降低右樹的高度（parent.bf = 2,cur.bf = -1）：
而此時僅通過單旋是無法完成的，需要通過兩種旋轉才能完成：
先右旋：
再左旋：
通過觀察發現其需要改變的平衡因子和curL有關系：
因此
代碼如下：
private void rotateRL(TreeNode parent) {
//右左雙旋
TreeNode cur = parent.right;
TreeNode curL = cur.left;
//此時就需要看curL的平衡因子瞭，再決定最後其他節點的平衡因子
int bf = curL.bf;
rotateRight(cur);
rotateLeft(parent);
//這裡通過規律可以得到當curR的bf值不同的時候，其需要改變的bf值也是不同的，因此裡就需要做出修改
if(bf == -1){
//當bf為-1時，其應修改的如下
parent.bf = 0;
cur.bf = 0;
curL.bf = 1;
}else if(bf == 1){
//當bf為1時，其應修改的如下
parent.bf = -1;
curL.bf = 0;
cur.bf = 0;
}
//另外當bf為0的時候就已經平衡瞭，就不需要改瞭，因為在兩次旋轉的時候就已經將其改為0瞭
}
2.刪除
刪除和上面的插入是差不多的，由於AVL樹也是二叉搜索樹，可按照二叉搜索樹的方式將節點刪除，然後再更新平衡因子，隻不過與刪除不同的是，刪除節點後的平衡因子更新，最差情況下一直要調整到根節點的位置。
具體步驟：
- 找到需要刪除的節點
- 按照搜索樹的刪除規則刪除節點
- 更新平衡因子，如果出現瞭不平衡，進行旋轉。–單旋，雙旋
我這裡就不進行完整的代碼書寫瞭！！
到這兒，AVL樹就介紹完畢瞭，後面會繼續介紹紅黑樹！！！
到此這篇關於Java詳解AVL樹的應用的文章就介紹到這瞭,更多相關Java AVL樹內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！
推薦閱讀：
- JDK集合源碼之解析TreeMap(二)
- C++AVL樹4種旋轉詳講(左單旋、右單旋、左右雙旋、右左雙旋)
- C++實現AVL樹的基本操作指南
- Java中關於二叉樹的概念以及搜索二叉樹詳解
- java基礎二叉搜索樹圖文詳解