Java詳解AVL樹的應(yīng)用

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

一.什么是AVL樹

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

1.二叉搜索樹

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

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

2.為什么引入了AVL樹

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

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

3.什么是AVL樹

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

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

二.自己構(gòu)造AVL樹

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

publicclassAVLTree{

staticclassTreeNode{

//內(nèi)部類，表示AVL樹的每個節(jié)點

//val值

publicintval;

//左孩子的引用

publicTreeNodeleft;

//右孩子的引用

publicTreeNoderight;

//父親節(jié)點的引用

publicTreeNodeparent;

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

publicintbf;

publicTreeNode(intval){

this.val=val;

//根節(jié)點

publicTreeNoderoot;

publicbooleaninsert(intval){

}

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

三.AVL樹的插入和刪除

1.插入

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

這個為要插入節(jié)點：

TreeNodenode=newTreeNode(val);

if(root==null){

//沒有根節(jié)點，要插入的就是根節(jié)點

root=node;

returntrue;

//記錄每個節(jié)點的父節(jié)點

TreeNodeparent=null;

//要移動的代節(jié)點

TreeNodecur=root;

//根據(jù)val的值和root進行比較來確定應(yīng)該插入節(jié)點的位置

while(cur!=null){

if(cur.valval){

//大于證明此節(jié)點應(yīng)在左子樹

parent=cur;

cur=cur.left;

}elseif(cur.valval){

//大于證明此節(jié)點應(yīng)在右子樹

parent=cur;

cur=cur.right;

}else{

//不能有值一樣的節(jié)點

returnfalse;

//此時cur為空，需要找到對應(yīng)的位置

if(parent.valval){

parent.left=node;

}else{

parent.right=node;

此時節(jié)點就已經(jīng)插進來了，此時就需要看其每個節(jié)點的平衡因子了

//而此時就需要對樹進行平衡因子的調(diào)整了，保證樹是高度平衡的

//再反著回去寫

node.parent=parent;

cur=node;

//當父親節(jié)點一直存在的時候，就表示沒有調(diào)到根節(jié)點就需要繼續(xù)調(diào)整

while(parent!=null){

if(cur==parent.right){

//在右邊右樹高度加一，因此bf+1

parent.bf++;

}else{

//再左邊，左樹高度加一，因此bf-1

parent.bf--;

//在這里就要進行判斷了，如果此時的父親節(jié)點如果平衡因子為0了，那么就不需要再往上走了，因為上面的都是平衡的

if(parent.bf==0){

returntrue;

}elseif(parent.bf==-1||parent.bf==1){

//此時父親節(jié)點的平衡因子為1、-1

//此時表示當前樹平衡了，但是不表示整棵樹都平衡了，因此還需要繼續(xù)往上走

cur=parent;

parent=cur.parent;

}else{

//此時父親節(jié)點的平衡因子為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);

//調(diào)整完就平衡了

break;

}

這是當前會出現(xiàn)的問題：

先來討論一下調(diào)整平衡因子會出現(xiàn)的一些情況，來分別看一下：

首先是平衡因子調(diào)整為0了，那么就不需要再往上走了，因為上面的都是平衡的，當前的父親節(jié)點的平衡因子為0了表示插入的這個元素只影響到了這一棵樹，上面是沒有影響的，因此是0的話就結(jié)束了

因此是0的話就表示當前已經(jīng)結(jié)束了，不需要再往上了，其他變?yōu)?的情況也是一樣的這里就不細畫了

而如果是1或者-1的話，表示當前樹平衡了，但是不表示整棵樹平衡了，因此需要再往上走；

而如果是2或者-2的話，會以下四種情況，再來分別看一下：

1.1.右單旋

此時左樹高，需要降低左樹的高度，也就是右旋（parent.bf=-2,cur.bf=-1）：

也就是如下的效果：

也就是這樣的調(diào)整過程：

下面寫一下代碼：

privatevoidrotateRight(TreeNodeparent){

//右單旋

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

TreeNodecur=parent.left;

//記錄cur的右節(jié)點

TreeNodecurR=cur.right;

parent.left=curR;

cur.right=parent;

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

if(curR!=null){

curR.parent=parent;

//然后將cur的右孩子改變?yōu)閜arent

//需要記錄parent的根節(jié)點

TreeNodepParent=parent.parent;

parent.parent=cur;

//檢查當前是不是根節(jié)點，不是根節(jié)點需要看是左子樹，還是右子樹

if(pParent!=null){

//改變之前的指向

cur.parent=pParent;

if(parent==pParent.right){

pParent.right=cur;

}else{

pParent.left=cur;

}else{

//此時parent就是root，因為沒有根節(jié)點

root=cur;

root.parent=null;

//最后記得一定要修改平衡因子

parent.bf=0;

cur.bf=0;

}

這樣一個簡單的右單旋就結(jié)束了~

1.2.左單旋

這種情況就是最開始的情況了

此時右樹高，需要降低右樹的高度，也就是左旋（parent.bf=2,cur.bf=1）：

也就是如下的效果：

也就是這樣的調(diào)整過程：

代碼如下：

privatevoidrotateLeft(TreeNodeparent){

//左單旋

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

//需要記錄父親節(jié)點

TreeNodepParent=parent.parent;

TreeNodecur=parent.right;

//記錄cur的左節(jié)點

TreeNodecurL=cur.left;

parent.right=curL;

cur.left=parent;

//判斷左節(jié)點是不是空的，如果是空的就不需要管了，不是空的就需要將parent右節(jié)點指向它，并且它的父親節(jié)點為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{

//是根節(jié)點

root=cur;

root.parent=null;

cur.bf=0;

parent.bf=0;

}

這樣一個簡單的左單旋就結(jié)束了~

1.3.左右雙旋

此時左樹高，需要降低左樹的高度，（parent.bf=-2,cur.bf=1）：

而此時僅通過單旋是無法完成的，需要通過兩種旋轉(zhuǎn)才能完成：

上面左單旋和右單旋已經(jīng)介紹過了，這里就不詳細介紹了，

先左旋：

此時修改的平衡因子是沒有用的

再右旋：

兩次旋轉(zhuǎn)之后只需要進行平衡因子的改變就可以了，

通過觀察curR的平衡因子，會決定最后其他節(jié)點的平衡因子

代碼如下：

privatevoidrotateLR(TreeNodeparent){

//左右雙旋

TreeNodecur=parent.left;

TreeNodecurR=cur.right;

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

intbf=curR.bf;

//先調(diào)用左旋再右旋

rotateLeft(cur);

rotateRight(parent);

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

if(bf==-1){

//當bf為-1時，其應(yīng)修改的如下

curR.bf=0;

cur.bf=0;

parent.bf=1;

}elseif(bf==1){

//當bf為1時，其應(yīng)修改的如下

curR.bf=0;

cur.bf=-1;

parent.bf=0;

//另外當bf為0的時候就已經(jīng)平衡了，就不需要改了，因為在兩次旋轉(zhuǎn)的時候就已經(jīng)將其改為0了

這樣一個左右雙旋就結(jié)束了~

1.4.右左雙旋

此時右樹高，需要降低右樹的高度（parent.bf=2,cur.bf=-1）：

而此時僅通過單旋是無法完成的，需要通過兩種旋轉(zhuǎn)才能完成：

先右旋：

再左旋：

通過觀察發(fā)現(xiàn)其需要改變的平衡因子和curL有關(guān)系：

因此

代碼如下：

privatevoidrotateRL(TreeNodeparent){

//右左雙旋

Tree