6.平衡二叉查找樹

AVL樹的定義：一種特殊的二叉搜索樹，它能自動維持平衡

專注于為中小企業(yè)提供網(wǎng)站設(shè)計、成都做網(wǎng)站服務(wù),電腦端+手機(jī)端+微信端的三站合一,更高效的管理,為中小企業(yè)汾西免費(fèi)做網(wǎng)站提供優(yōu)質(zhì)的服務(wù)。我們立足成都，凝聚了一批互聯(lián)網(wǎng)行業(yè)人才，有力地推動了上千企業(yè)的穩(wěn)健成長，幫助中小企業(yè)通過網(wǎng)站建設(shè)實(shí)現(xiàn)規(guī)模擴(kuò)充和轉(zhuǎn)變。

AVL是發(fā)明者的名字縮寫：G.M. AdelsonVelskii and E.M. Landis

利用AVL樹實(shí)現(xiàn)ADT Map，基本上與BST的實(shí)現(xiàn)相同，不同之處僅在于二叉樹的生成與維護(hù)過程

AVL樹的實(shí)現(xiàn)中，需要對每個節(jié)點(diǎn)跟蹤“平衡因子balance factor”參數(shù)，平衡因子是根據(jù)節(jié)點(diǎn)的左右子樹的高度來定義的，確切地說，是左右子樹高度差：

balanceFactor = height(leftSubTree) ? height(rightSubTree)

如果平衡因子大于0，稱為“左傾left-heavy”，小于零稱為“右傾right-heavy”平衡因子等于0，則稱作平衡。

如果一個二叉查找樹中每個節(jié)點(diǎn)的平衡因子都在-1，0，1之間，則把這個二叉搜索樹稱為平衡樹

我們先看看限定平衡因子帶來的結(jié)果。我們認(rèn)為，保證樹的平衡因子為–1、0 或 1，可以使關(guān)鍵操作獲得更好的大O性能

觀察上圖h=1～4時，總節(jié)點(diǎn)數(shù)N的變化

h= 1, N= 1

h= 2, N= 2= 1+ 1

h= 3, N= 4= 1+ 1+ 2

h= 4, N= 7= 1+ 2+ 4

觀察這個通式，很接近斐波那契數(shù)列

定義斐波那契數(shù)列

利用 重寫

最多搜索次數(shù)h和規(guī)模N的關(guān)系，可以說AVL樹的搜索時間復(fù)雜度為O(log n)

?既然AVL平衡樹確實(shí)能夠改進(jìn)BST樹的性能，避免退化情形

?我們來看看向AVL樹插入一個新key，如何才能保持AVL樹的平衡性質(zhì)

?首先，作為BST，新key必定以葉節(jié)點(diǎn)形式插入到AVL樹中

葉節(jié)點(diǎn)的平衡因子是0，其本身無需重新平衡

但會影響其父節(jié)點(diǎn)的平衡因子：

這種影響可能隨著其父節(jié)點(diǎn)到根節(jié)點(diǎn)的路徑一直傳遞上去，直到傳遞到根節(jié)點(diǎn)為止；

或者某個父節(jié)點(diǎn)平衡因子被調(diào)整到0，不再影響上層節(jié)點(diǎn)的平衡因子為止。

? （無論從-1或者1調(diào)整到0，都不會改變子樹高度）

重新定義_put方法,調(diào)整因子

UpdateBalance方法

rebalance重新平衡

主要手段：將不平衡的子樹進(jìn)行旋轉(zhuǎn)rotation視“左傾”或者“右傾”進(jìn)行不同方向的旋轉(zhuǎn)

同時更新相關(guān)父節(jié)點(diǎn)引用，更新旋轉(zhuǎn)后被影響節(jié)點(diǎn)的平衡因子

如圖，是一個“右傾”子樹A的左旋轉(zhuǎn)（并保持BST性質(zhì)）將右子節(jié)點(diǎn)B提升為子樹的根，將舊根節(jié)點(diǎn)A作為新根節(jié)點(diǎn)B的左子節(jié)點(diǎn)，如果新根節(jié)點(diǎn)B原來有左子節(jié)點(diǎn)，則將此節(jié)點(diǎn)設(shè)

置為A的右子節(jié)點(diǎn)（A的右子節(jié)點(diǎn)一定有空）

更復(fù)雜一些的情況：如圖的“左傾”子樹右旋轉(zhuǎn)，旋轉(zhuǎn)后，新根節(jié)點(diǎn)將舊根節(jié)點(diǎn)作為右子節(jié)點(diǎn)，但是新根節(jié)點(diǎn)原來已有右子節(jié)點(diǎn)，需要將原有的右子節(jié)點(diǎn)重新定位！原有的右子節(jié)點(diǎn)D改到舊根節(jié)點(diǎn)E的左子節(jié)點(diǎn)，同樣，E的左子節(jié)點(diǎn)在旋轉(zhuǎn)后一定有空

如何調(diào)整平衡因子

看看左旋轉(zhuǎn)對平衡因子的影響，保持了次序ABCDE，ACE的平衡因子不變，hA/hC/hE不變，主要看BD新舊關(guān)系

拓展 嘗試計算樹的高度

TreeNode類中添加高度方法

經(jīng)過復(fù)雜的put方法，AVL樹始終維持平衡，get方法也始終保持O(log n)高性能

將AVL樹的put方法分為兩個部分：

需要插入的新節(jié)點(diǎn)是葉節(jié)點(diǎn)，更新其所有父節(jié)點(diǎn)和祖先節(jié)點(diǎn)的代價最多為O(log n)

如果插入的新節(jié)點(diǎn)引發(fā)了不平衡，重新平衡最多需要2次旋轉(zhuǎn)，但旋轉(zhuǎn)的代價與問題規(guī)模無關(guān)，是常數(shù)O(1)所以整個put方法的時間復(fù)雜度還是O(log n)

現(xiàn)有一棵無重復(fù)關(guān)鍵字的平衡二叉樹（AVL 樹）

D、樹中最大元素一定是無左子樹。

因?yàn)槊總€結(jié)點(diǎn)的左子樹的結(jié)點(diǎn)的值比該結(jié)點(diǎn)的值小，所以樹中最大元素一定是無左子樹。

BT退化為每個結(jié)點(diǎn) (非葉) 只有兩棵子樹時，結(jié)點(diǎn)的數(shù)目最少，葉子也最少。設(shè)層號為i則各層結(jié)點(diǎn)數(shù)為2^(i-1)個，那么高為h的BT最大層號是j時，有h=j-1。

整個樹的結(jié)點(diǎn)數(shù)為s=2^0+2^1+2^2+…+2^h, 故s=2^(h+1)-1。其葉子的個數(shù)是2^h。同理，當(dāng)BT每個非葉結(jié)點(diǎn)都有三棵子數(shù)時，結(jié)點(diǎn)數(shù)目最多。

擴(kuò)展資料：

任意節(jié)點(diǎn)的子樹的高度差都小于等于1。常見的符合平衡樹的有，B樹（多路平衡搜索樹）、AVL樹（二叉平衡搜索樹）等。

平衡樹可以完成集合的一系列操作,?時間復(fù)雜度和空間復(fù)雜度相對于“2-3樹”要低，在完成集合的一系列操作中始終保持平衡，為大型數(shù)據(jù)庫的組織、索引提供了一條新的途徑。

平衡二叉樹

以前做的。

一、 需求分析

1． 本程序是是利用平衡二叉樹實(shí)現(xiàn)一個動態(tài)查找表，實(shí)現(xiàn)動態(tài)查找表的三種基本功能：查找、插入和刪除。

2． 初始，平衡二叉樹為空樹，可以按先序輸入平衡二叉樹，以輸入0結(jié)束，中間以回車隔開，創(chuàng)建好二叉樹后，可以對其查找，再對其插入，輸入0結(jié)束插入，再可以對其刪除，輸入0結(jié)束，每次插入或刪除一個結(jié)點(diǎn)后，更新平衡二叉樹的顯示。

3． 本程序以用戶和計算機(jī)的對話方式執(zhí)行，根據(jù)計算機(jī)終端顯示：“提示信息”下，用戶可由鍵盤輸入要執(zhí)行的操作。

4． 測試數(shù)據(jù)（附后）

二、 概要設(shè)計

1． 抽象數(shù)據(jù)類型動態(tài)查找表的定義如下：

ADT DynamicSearchTable{

數(shù)據(jù)結(jié)構(gòu)D：D是具有相同特性的數(shù)據(jù)元素的集合。各個數(shù)據(jù)元素含有類型相同，可惟一標(biāo)識數(shù)據(jù)元素的關(guān)鍵字。

數(shù)據(jù)關(guān)系R：數(shù)據(jù)元素同屬一個集合。

基本操作P：

InitDSTable(DT);

操作結(jié)果：構(gòu)造一個空的動態(tài)查找表DT。

DestroyDSTable(DT);

初試條件：動態(tài)查找表DT存在。

操作結(jié)果: 銷毀動態(tài)查找表DT。

SearchDSTable(DT,key);

初試條件：動態(tài)查找表DT存在，key為和關(guān)鍵字類型相同的給定值。

操作結(jié)果: 若DT中存在其關(guān)鍵字等于key的數(shù)據(jù)元素，則函數(shù)值為該元素的值或表中的位置，否則為“空”。

InsertDSTable(DT,e);

初試條件：動態(tài)查找表DT存在，e為待插入的數(shù)據(jù)元素。

操作結(jié)果: 若DT中不存在其關(guān)鍵字等于e. key的數(shù)據(jù)元素，則插入e到DT。

DeleteDSTable(DT,key);

初試條件：動態(tài)查找表DT存在，key為和關(guān)鍵字類型相同的給定值。

操作結(jié)果: 若DT中存在其關(guān)鍵字等于key的數(shù)據(jù)元素，則刪除之。

TraverseDSTable(DT,Visit());

初試條件：動態(tài)查找表DT存在，Visit()是結(jié)點(diǎn)操作的應(yīng)用函數(shù)。

操作結(jié)果: 按某種次序?qū)T的每個結(jié)點(diǎn)調(diào)用函數(shù)Visit()一次且至多

一次。一但Visit()失敗，則操作失敗。

}ADT DynamicSearchTable

2． 本程序包含兩個模塊：

Void main(){

Do{

接受命令（根據(jù)提示輸入終點(diǎn)城市和起點(diǎn)城市的序號）；

處理命令；

}while(“命令”=“退出”)；

}

3．本程序只有兩個模塊，調(diào)用關(guān)系簡單

主程序模塊

平衡二叉樹的模塊

三、 詳細(xì)設(shè)計

1． 根據(jù)題目要求和查找的基本特點(diǎn)，其結(jié)點(diǎn)類型

typedef struct BSTnode{

int data;

int bf;

struct BSTnode *lchild,*rchild;

}BSTnode,*bstree;

#define LH +1

#define EH 0

#define RH -1

/-----------------------------************對平衡二叉樹的操作

bstree InsertAVL(bstree T, int e)；

////////在平衡二叉樹中插入結(jié)點(diǎn)。

int FindAVL(bstree p,int e)；

////////查找平衡二叉樹中是否有結(jié)點(diǎn)e。

bstree DeleteAVL(bstree T,int e)

////////刪除平衡平衡二叉樹的結(jié)點(diǎn)e，并保持平衡二叉樹的性質(zhì)。

int Preordertraverse(bstree T)

////////按先序遍歷平衡二叉樹。

/------------------------************平衡二叉樹的操作的詳細(xì)算法

bstree InsertAVL(bstree T, int e)

{

bstree p;

//插入新結(jié)點(diǎn)，樹長高置taller為TRUE

if(!T) {

T=(bstree)malloc(sizeof(BSTnode));

T-data=e;

T-lchild=T-rchild=NULL;

T-bf=EH;

taller=TRUE;

}

else {

//樹中存在和e有相同關(guān)鍵字的結(jié)點(diǎn)則不再插入

if(e==T-data){

taller=FALSE;

return NULL;

}

//值小于則繼續(xù)在樹的左子樹中搜索

if(e T-data){

//插入到左子樹且左子樹長高

p=InsertAVL(T-lchild,e);

if(p){

T-lchild=p;

if(taller) {

switch(T-bf){ //檢查*T的平衡度

case LH: //原本左子樹比右子樹高，需要做左平衡處理

T=LeftBalance(T);

taller=FALSE;

break;

case EH: //原本左子樹和右子樹同高，現(xiàn)因左子樹爭高而使樹增高

T-bf=LH;

taller=TRUE;

break;

case RH: //原本右子樹比左子樹高，現(xiàn)在左右子樹等高

T-bf=EH;

taller=FALSE;

break;

}///////switch(T-bf)

}///////if(taller)

}/////if(p)

}///////if(e T-data)

//繼續(xù)在*T的右子樹中搜索

else{

//插入到右子樹且使右子樹長高

p=InsertAVL(T-rchild,e);

if (p){

T-rchild=p;

if(taller) {

switch(T-bf){ //檢查*T的平衡度

case LH: //原本左子樹比右子樹高，現(xiàn)在左右子樹等高

T-bf=EH;

taller=FALSE;

break;

case EH: //原本左子樹和右子樹同高，現(xiàn)因右子樹增高而使樹增高

T-bf=RH;

taller=TRUE;

break;

case RH: //原本右子樹比左子樹高，需要做右平衡處理

T=RightBalance(T);

taller=FALSE;

break;

}//////switch(T-bf)

}/////if(taller)

}/////if (p)

}//////if(e T-data)

}///////else

return T;

}

int Preordertraverse(bstree T){

if(T){

printf(" %d %d\n",T-data,T-bf);

Preordertraverse(T-lchild);

Preordertraverse(T-rchild);

}

return 1;

}

int FindAVL(bstree p,int e){

if(p==NULL)return NULL;

else if(e==p-data) return true;

else if(ep-data){

p=p-lchild;

return FindAVL(p, e);

}////左子樹上查找

else {

p=p-rchild;

return FindAVL( p, e);

}////右子樹上查找

}

bstree DeleteAVL(bstree T,int e){

//刪除后要保證該二叉樹還是平衡的

int n,m=0;/////標(biāo)記

bstree q;

if(!T)return NULL;

else {

if(e==T-data) {////直接刪除

n=Delete(T,e);

m=n;

if(m!=0) {

q=T;

DeleteAVL(T,m);

q-data=m;}

}

else {

if(eT-data){////在左子樹上尋找

DeleteAVL(T-lchild,e);

if(shorter){

switch(T-bf){

case LH:T-bf=EH;shorter=true;break;

case EH:T-bf=RH;shorter=false;break;

case RH:Delete_Rightbalance(T);shorter=true;break;

}////switch(T-bf)

}/////if(shorter)

}/////if(eT-data)

else{ /////////在右子樹上尋找

DeleteAVL(T-rchild,e);

if(shorter)

switch(T-bf){

case LH:Delete_Leftbalance(T);shorter=true;break;

case EH:T-bf=LH;shorter=false;break;

case RH:T-bf=EH;shorter=true;break;

}////////switch(T-bf)

}////////在右子數(shù)上尋找完

}////////在左右子上完

}///////////刪除完

return T;

}

2． 主程序和其他偽碼算法

void main(){

while(e!=0){

if(e!=0) InsertAVL(T,e);

}

while(d!=0){

if(d!=0) InsertAVL(T,d);

Preordertraverse(T);

}

c=FindAVL(T,t);

if(c==1)printf("有要查找的節(jié)點(diǎn)\n");

else printf("無要查找的節(jié)點(diǎn)\n");

do{

DeleteAVL(T,b);

Preordertraverse(T);

}while(b==1);

}

///右旋

bstree R_Rotate(bstree p){

bstree lc;

lc=p-lchild;

p-lchild=lc-rchild;

lc-rchild=p;

p=lc;

return p;

}

////左旋

bstree L_Rotate(bstree p){

bstree rc;

rc=p-rchild;

p-rchild=rc-lchild;

rc-lchild=p;

p=rc;

return p;

}

/////左平衡處理

bstree LeftBalance(bstree T){

bstree lc,rd;

lc=T-lchild; //lc指向*T的左子樹根結(jié)點(diǎn)

switch(lc-bf) { //檢查*T的左子樹平衡度，并做相應(yīng)的平衡處理

case LH: //新結(jié)點(diǎn)插入在*T的左孩子的左子樹上，要做單右旋處理

T-bf=lc-bf=EH;

T=R_Rotate(T);

break;

case RH: //新結(jié)點(diǎn)插入在*T的左孩子的右子樹上，要做雙旋處理

rd=lc-rchild; //rd指向*T的左孩子的右子樹根

switch(rd-bf){ //修改*T及其左孩子的平衡因子

case LH:

T-bf=RH;

lc-bf=EH;

break;

case EH:

T-bf=lc-bf=EH;

break;

case RH:

T-bf=EH;

lc-bf=LH;

break;

}//////////switch(rd-bf)

rd-bf=EH;

T-lchild=L_Rotate(T-lchild); //對*T的左孩子做左旋平衡處理

T=R_Rotate(T); //對*T做右旋處理

}////////switch(lc-bf)

return T;

}

////右平衡處理

bstree RightBalance(bstree T)

{

bstree rc,ld;

rc=T-rchild; //rc指向*T的右子樹根結(jié)點(diǎn)

switch(rc-bf) { //檢查*T的右子樹平衡度，并做相應(yīng)的平衡處理

case RH: //新結(jié)點(diǎn)插入在*T的右孩子的右子樹上，要做單右旋處理

T-bf=rc-bf=EH;

T=L_Rotate(T);

break;

case LH: //新結(jié)點(diǎn)插入在*T的右孩子的左子樹上，要做雙旋處理

ld=rc-lchild; //ld指向*T的右孩子的左子樹根

switch(ld-bf){ //修改*T及其右孩子的平衡因子

case LH:

T-bf=EH;

rc-bf=RH;

break;

case EH:

T-bf=rc-bf=EH;

break;

case RH:

T-bf=LH;

rc-bf=EH;

break;

}///switch(ld-bf)

ld-bf=EH;

T-rchild=R_Rotate(T-rchild); //對*T的右孩子做右旋平衡處理

T=L_Rotate(T); //對*T做左旋處理

}/////switch(rc-bf)

return T;

}

int Delete(bstree T,int e){

//刪除結(jié)點(diǎn)

bstree p,q;

e=0;

p=T;

if(!T-rchild) {//右子數(shù)為空需要重接它的左子數(shù)

T=T-lchild;

free(p);

shorter=true;

}

else if(!T-lchild) {//重接它的右子數(shù)

T=T-rchild;

free(p);

shorter=true;

}

else{ //左右子數(shù)均不空

q=T-lchild;

while(q-rchild!=NULL){//轉(zhuǎn)左，然后向右到盡頭

q=q-rchild;

}

e=q-data;

}

return e;

}

void Delete_Rightbalance(bstree T){

///////////刪除在左子樹上的，相當(dāng)于插入在右子樹

bstree rc=T-rchild,ld;

switch(rc-bf){

case LH://///////雙旋 ，先右旋后左旋

ld=rc-lchild;

rc-lchild=ld-rchild;

ld-rchild=rc;

T-rchild=rc-lchild;

rc-lchild=T;

switch(ld-bf) {

case LH:T-bf=EH;

rc-bf=RH;

break;

case EH:T-bf=rc-bf=EH;

break;

case RH:T-bf=LH;

rc-bf=EH;

break;

}

ld-bf=EH;

T=rc;

shorter=true;break;

case EH:///////刪除在左子樹，相當(dāng)于插入在右子樹，左單旋

T-rchild=rc-lchild;

rc-lchild=T;

rc-bf=LH;

T-bf=RH;

T=rc;

shorter=EH;break;

case RH:///////刪除在左子樹，相當(dāng)于插入在右子樹，左單旋

T-rchild=rc-lchild;

rc-lchild=T;

rc-bf=T-bf=EH;

T=rc;

shorter=true;break;

}

}

void Delete_Leftbalance(bstree T)/////刪除右子樹上的，相當(dāng)于插入在左子樹上

{

bstree p1,p2;

p1=T-lchild;

switch(p1-bf) {

case LH:T-lchild=p1-rchild;//////右旋

p1-rchild=T;

p1-bf=T-bf=EH;

T=p1;

shorter=true;

break;

case EH:T-lchild=p1-rchild;///////右旋

p1-rchild=T;

p1-bf=RH;

T-bf=LH;

T=p1;

shorter=false;

break;

case RH:p2=p1-rchild;//////////右雙旋

p1-rchild=p2-lchild;

p2-lchild=p1;

T-lchild=p2-rchild;

p2-rchild=T;

switch(p2-bf){

case LH:T-bf=RH;p1-bf=EH;break;

case EH:T-bf=EH;p1-bf=EH;break;

case RH:T-bf=EH;p1-bf=LH;break;

}

p2-bf=EH;

T=p2;

shorter=true;break;

}

}

3． 函數(shù)的調(diào)用關(guān)系圖

Main

InsertAVL Preordertraverse FindAVL DeleteAVL

四、 調(diào)試分析

1． 在開始對平衡二叉樹的插入后，再做平衡處理時，特別是在做雙向旋轉(zhuǎn)平衡處理后的更新時，費(fèi)了一些時間；

2． 在做平衡二叉樹的刪除時，當(dāng)刪除結(jié)點(diǎn)左右孩子均在時，開始直接用左子樹的最大數(shù)代替，然后直接刪除結(jié)點(diǎn)，結(jié)果導(dǎo)致刪除了將要刪除的結(jié)點(diǎn)及其孩子均刪除了，后來將要刪除的結(jié)點(diǎn)用左子樹的最大樹代替后，對左子樹的最大結(jié)點(diǎn)做好標(biāo)記，然后再做對其做刪除處理。

3． 本程序算法基本簡單，沒有多大困難，就是在分析做雙旋平衡處理的更新時，開始思路有些混亂，后來就好了；

五、 用戶手冊

1. 本程序的運(yùn)行環(huán)境為DOS操作系統(tǒng)，執(zhí)行文件為Balanced Tree.exe。

2. 進(jìn)入演示程序后，按廣度遍歷輸入平衡二叉樹，中間以回車鍵隔開，輸入0為結(jié)束；再輸入要插入的結(jié)點(diǎn)，輸入0結(jié)束，再輸入要查找的結(jié)點(diǎn)，最后可以輸入要刪除的結(jié)點(diǎn)，輸入0結(jié)束

六、 測試結(jié)果

先按廣度遍歷創(chuàng)建平衡二叉樹（亦可一個一個的插入二叉樹的結(jié)點(diǎn)）（50 20 60 10 30 55 70 5 15 25 58 90） ，輸入0結(jié)束，然后可插入結(jié)點(diǎn)（39），其會顯示插入后的二叉樹，輸入0，不再插入；輸入要查找結(jié)點(diǎn)（6），輸入要刪除的結(jié)點(diǎn)（20），其顯示如下：

七、 附錄

Balance Tree.cpp

AVL樹所有的java遞歸算法

遞歸的邏輯，簡單來說就是要有一個切入點(diǎn)。從簡單的數(shù)據(jù)逆推到復(fù)雜性的數(shù)據(jù)。

分享名稱：avl平衡樹java代碼,avl樹java實(shí)現(xiàn)
網(wǎng)頁鏈接：http://chinadenli.net/article19/dsepjdh.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供品牌網(wǎng)站制作、網(wǎng)站內(nèi)鏈、定制開發(fā)、全網(wǎng)營銷推廣、用戶體驗(yàn)、動態(tài)網(wǎng)站

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)