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

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

一.什么是AVL樹(shù)

在認(rèn)識(shí)AVL樹(shù)之前我們先認(rèn)識(shí)一下什么是二叉搜索樹(shù):

1.二叉搜索樹(shù)

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

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

2.為什么引入了AVL樹(shù)

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

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

3.什么是AVL樹(shù)

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

平衡因子=右子樹(shù)的高度-左子樹(shù)的高度

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

這里的構(gòu)造還是和二叉搜索樹(shù)的構(gòu)造差不多的，只不過(guò)在這里插入元素的話就需要考慮平衡因子的事情了，因?yàn)橐欢ㄒＷC插入元素后此樹(shù)還是一棵AVL樹(shù)，就需要進(jìn)行相關(guān)調(diào)整，這里就先不過(guò)多介紹了，下面再詳細(xì)介紹，先來(lái)構(gòu)造一棵簡(jiǎn)單的AVL樹(shù)：

publicclassAVLTree{

staticclassTreeNode{

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

//val值

publicintval;

//左孩子的引用

publicTreeNodeleft;

//右孩子的引用

publicTreeNoderight;

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

publicTreeNodeparent;

//平衡因子(每個(gè)節(jié)點(diǎn)都有）

publicintbf;

publicTreeNode(intval){

this.val=val;

//根節(jié)點(diǎn)

publicTreeNoderoot;

publicbooleaninsert(intval){

}

這樣一棵簡(jiǎn)單的AVL樹(shù)就構(gòu)造好了，下面就來(lái)寫一下AVL樹(shù)的插入！

三.AVL樹(shù)的插入和刪除

1.插入

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

這個(gè)為要插入節(jié)點(diǎn)：

TreeNodenode=newTreeNode(val);

if(root==null){

//沒(méi)有根節(jié)點(diǎn)，要插入的就是根節(jié)點(diǎn)

root=node;

returntrue;

//記錄每個(gè)節(jié)點(diǎn)的父節(jié)點(diǎn)

TreeNodeparent=null;

//要移動(dòng)的代節(jié)點(diǎn)

TreeNodecur=root;

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

while(cur!=null){

if(cur.valval){

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

parent=cur;

cur=cur.left;

}elseif(cur.valval){

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

parent=cur;

cur=cur.right;

}else{

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

returnfalse;

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

if(parent.valval){

parent.left=node;

}else{

parent.right=node;

此時(shí)節(jié)點(diǎn)就已經(jīng)插進(jìn)來(lái)了，此時(shí)就需要看其每個(gè)節(jié)點(diǎn)的平衡因子了

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

//再反著回去寫

node.parent=parent;

cur=node;

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

while(parent!=null){

if(cur==parent.right){

//在右邊右樹(shù)高度加一，因此bf+1

parent.bf++;

}else{

//再左邊，左樹(shù)高度加一，因此bf-1

parent.bf--;

//在這里就要進(jìn)行判斷了，如果此時(shí)的父親節(jié)點(diǎn)如果平衡因子為0了，那么就不需要再往上走了，因?yàn)樯厦娴亩际瞧胶獾?/p>

if(parent.bf==0){

returntrue;

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

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

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

cur=parent;

parent=cur.parent;

}else{

//此時(shí)父親節(jié)點(diǎn)的平衡因子為2、-2

if(parent.bf==2){

//此時(shí)右樹(shù)高需要降低右樹(shù)的高度

if(cur.bf==1){

//左單旋

rotateLeft(parent);

}else{

//右左雙旋

rotateRL(parent);

}else{

//此時(shí)左樹(shù)高，需要降低左樹(shù)的高度

if(cur.bf==1){

//左右雙旋

rotateLR(parent);

}else{

//右單旋

rotateRight(parent);

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

break;

}

這是當(dāng)前會(huì)出現(xiàn)的問(wèn)題：

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

首先是平衡因子調(diào)整為0了，那么就不需要再往上走了，因?yàn)樯厦娴亩际瞧胶獾?，?dāng)前的父親節(jié)點(diǎn)的平衡因子為0了表示插入的這個(gè)元素只影響到了這一棵樹(shù)，上面是沒(méi)有影響的，因此是0的話就結(jié)束了

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

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

而如果是2或者-2的話，會(huì)以下四種情況，再來(lái)分別看一下：

1.1.右單旋

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

也就是如下的效果：

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

下面寫一下代碼：

privatevoidrotateRight(TreeNodeparent){

//右單旋

//此時(shí)parent的平衡因子為-2，cur的平衡因子為-1

TreeNodecur=parent.left;

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

TreeNodecurR=cur.right;

parent.left=curR;

cur.right=parent;

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

if(curR!=null){

curR.parent=parent;

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

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

TreeNodepParent=parent.parent;

parent.parent=cur;

//檢查當(dāng)前是不是根節(jié)點(diǎn)，不是根節(jié)點(diǎn)需要看是左子樹(shù)，還是右子樹(shù)

if(pParent!=null){

//改變之前的指向

cur.parent=pParent;

if(parent==pParent.right){

pParent.right=cur;

}else{

pParent.left=cur;

}else{

//此時(shí)parent就是root，因?yàn)闆](méi)有根節(jié)點(diǎn)

root=cur;

root.parent=null;

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

parent.bf=0;

cur.bf=0;

}

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

1.2.左單旋

這種情況就是最開(kāi)始的情況了

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

也就是如下的效果：

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

代碼如下：

privatevoidrotateLeft(TreeNodeparent){

//左單旋

//此時(shí)parent平衡因子為2，cur的平衡因子為1

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

TreeNodepParent=parent.parent;

TreeNodecur=parent.right;

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

TreeNodecurL=cur.left;

parent.right=curL;

cur.left=parent;

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

root=cur;

root.parent=null;

cur.bf=0;

parent.bf=0;

}

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

1.3.左右雙旋

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

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

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

先左旋：

此時(shí)修改的平衡因子是沒(méi)有用的

再右旋：

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

通過(guò)觀察curR的平衡因子，會(huì)決定最后其他節(jié)點(diǎn)的平衡因子

代碼如下：

privatevoidrotateLR(TreeNodeparent){

//左右雙旋

TreeNodecur=parent.left;

TreeNodecurR=cur.right;

//此時(shí)就需要看curR的平衡因子，再?zèng)Q定最后其他節(jié)點(diǎn)的平衡因子

intbf=curR.bf;

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

rotateLeft(cur);

rotateRight(parent);

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

if(bf==-1){

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

curR.bf=0;

cur.bf=0;

parent.bf=1;

}elseif(bf==1){

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

curR.bf=0;

cur.bf=-1;

parent.bf=0;

//另外當(dāng)bf為0的時(shí)候就已經(jīng)平衡了，就不需要改了，因?yàn)樵趦纱涡D(zhuǎn)的時(shí)候就已經(jīng)將其改為0了

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

1.4.右左雙旋

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

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

先右旋：

再左旋：

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

因此

代碼如下：

privatevoidrotateRL(TreeNodeparent){

//右左雙旋

Tree