第Java詳解AVL樹的應用目錄一.什么是AVL樹1.二叉搜索樹2.為什么引入了AVL樹3.什么是AVL樹二.自己構造AVL樹三.AVL樹的插入和刪除1.插入1.1.右單旋1.2.左單旋1.3.左右雙旋1.4.右左雙旋2.刪除

一.什么是AVL樹

在認識AVL樹之前我們先認識一下什么是二叉搜索樹:

1.二叉搜索樹

二叉搜索樹又稱為二叉排序樹,二叉搜索樹滿足所有的左孩子節點都小于其根節點的值,所有的右孩子節點都大于其根節點的值,二叉搜索樹上的每一棵子樹都是一棵二叉搜索樹,因此二叉搜索樹通過中序遍歷可以獲得一個有序的序列(由小到大);

類似于這樣的樹就是一棵二叉搜索樹;

2.為什么引入了AVL樹

二叉搜索樹看似很美好,但其卻有一些缺陷.對于二叉搜索樹而言,是和查找相關的，而不論是查找還是刪除,都需要先進行查找,也就是對整棵樹來進行遍歷,而對有n個結點的二叉搜索樹，若每個元素查找的概率相等，則二叉搜索樹平均查找長度是結點在二叉搜索樹的深度函數,也就是結點越深，則比較次數越多.最優的情況下是：二叉搜索樹為完全二叉樹，其平均比較次數為：log2nlog_2{n}log2?n,但是如果二叉搜索樹退化成了一棵單分支的樹,其平均比較次數為：n/2,就是最差的情況了

這就相當于是一個順序表的查找了,這樣二叉搜索樹的優勢就完全消失了,因此就引入了AVL樹!

3.什么是AVL樹

AVL樹又稱自平衡二叉查找樹,是高度平衡的二叉搜索樹,就是在二叉搜索樹的基礎上進行了優化,既當向二叉搜索樹中插入新結點后，保證每個結點的左右子樹高度之差的絕對值不超過1(需要對樹中的結點進行調整),也就是降低樹的高度,這樣就可以減少平均搜索長度了,因此AVL樹滿足它的左右子樹都是AVL樹,左右子樹高度之差(簡稱平衡因子)的絕對值不超過1(-1/0/1),這就是AVL樹的優勢所在,因此如果一棵二叉搜索樹是高度平衡的，它就是AVL樹。如果它有n個結點，其高度可保持在，搜索時間復雜度O(log2nlog_2{n}log2?n)!!!

平衡因子=右子樹的高度-左子樹的高度

二.自己構造AVL樹

這里的構造還是和二叉搜索樹的構造差不多的，只不過在這里插入元素的話就需要考慮平衡因子的事情了，因為一定要保證插入元素后此樹還是一棵AVL樹，就需要進行相關調整，這里就先不過多介紹了，下面再詳細介紹，先來構造一棵簡單的AVL樹：

publicclassAVLTree{

staticclassTreeNode{

//內部類，表示AVL樹的每個節點

//val值

publicintval;

//左孩子的引用

publicTreeNodeleft;

//右孩子的引用

publicTreeNoderight;

//父親節點的引用

publicTreeNodeparent;

//平衡因子(每個節點都有）

publicintbf;

publicTreeNode(intval){

this.val=val;

//根節點

publicTreeNoderoot;

publicbooleaninsert(intval){

}

這樣一棵簡單的AVL樹就構造好了，下面就來寫一下AVL樹的插入！

三.AVL樹的插入和刪除

1.插入

首先就是將節點插進來，和二叉搜索樹一樣，先只看位置在哪，不關注平衡因子

這個為要插入節點：

TreeNodenode=newTreeNode(val);

if(root==null){

//沒有根節點，要插入的就是根節點

root=node;

returntrue;

//記錄每個節點的父節點

TreeNodeparent=null;

//要移動的代節點

TreeNodecur=root;

//根據val的值和root進行比較來確定應該插入節點的位置

while(cur!=null){

if(cur.valval){

//大于證明此節點應在左子樹

parent=cur;

cur=cur.left;

}elseif(cur.valval){

//大于證明此節點應在右子樹

parent=cur;

cur=cur.right;

}else{

//不能有值一樣的節點

returnfalse;

//此時cur為空，需要找到對應的位置

if(parent.valval){

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){

returntrue;

}elseif(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）：

也就是如下的效果：

也就是這樣的調整過程：

下面寫一下代碼：

privatevoidrotateRight(TreeNodeparent){

//右單旋

//此時parent的平衡因子為-2，cur的平衡因子為-1

TreeNodecur=parent.left;

//記錄cur的右節點

TreeNodecurR=cur.right;

parent.left=curR;

cur.right=parent;

//如果cur有右節點需要賦給parent的左節點，但是沒有就不需要給了

if(curR!=null){

curR.parent=parent;

//然后將cur的右孩子改變為parent

//需要記錄parent的根節點

TreeNodepParent=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）：

也就是如下的效果：

也就是這樣的調整過程：

代碼如下：

privatevoidrotateLeft(TreeNodeparent){

//左單旋

//此時parent平衡因子為2，cur的平衡因子為1

//需要記錄父親節點

TreeNodepParent=parent.parent;

TreeNodecur=parent.right;

//記錄cur的左節點

TreeNodecurL=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的平衡因子，會決定最后其他節點的平衡因子

代碼如下：

privatevoidrotateLR(TreeNodeparent){

//左右雙旋

TreeNodecur=parent.left;

TreeNodecurR=cur.right;

//此時就需要看curR的平衡因子，再決定最后其他節點的平衡因子

intbf=curR.bf;

//先調用左旋再右旋

rotateLeft(cur);

rotateRight(parent);

//這里通過規律可以得到當curR的bf值不同的時候，其需要改變的bf值也是不同的，因此里就需要做出修改

if(bf==-1){

//當bf為-1時，其應修改的如下

curR.bf=0;

cur.bf=0;

parent.bf=1;

}elseif(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有關系：

因此

代碼如下：

privatevoidrotateRL(TreeNodeparent){

//右左雙旋

Tree