數(shù)據(jù)結(jié)構(gòu)課件 ALV樹的處理

ALV樹的處理

1.概述

AVL樹是最早提出的自平衡二叉樹，在AVL樹中任何節(jié)點(diǎn)的兩個(gè)子樹的高度最大差別為一，所以

它也被稱為高度平衡樹。AVL樹得名于它的發(fā)明者GM.Adelson-Velsky和E.M.Landis。AVL樹種查

找、插入和刪除在平均和最壞情況下都是。（logn）,增加和刪除可能需要通過一次或多次樹旋轉(zhuǎn)來重

新平衡這個(gè)樹。本文介紹了AVL樹的設(shè)計(jì)思想和基本操作。

2.基本術(shù)語

有四種種情況可能導(dǎo)致二叉查找樹不平衡，分別為：

（1）LL：插入一個(gè)新節(jié)點(diǎn)到根節(jié)點(diǎn)的左子樹（Left）的左子樹（Left）,導(dǎo)致根節(jié)點(diǎn)的平衡因子

由1變?yōu)?

（2）RR：插入?個(gè)新節(jié)點(diǎn)到根節(jié)點(diǎn)的右子樹（Right）的右子樹（Right）,導(dǎo)致根節(jié)點(diǎn)的平衡因

子由-1變?yōu)?2

（3）LR：插入一個(gè)新節(jié)點(diǎn)到根節(jié)點(diǎn)的左子樹（Left）的右子樹（Right）,導(dǎo)致根節(jié)點(diǎn)的平衡因子

由1變?yōu)?

（4）RL：插入一個(gè)新節(jié)點(diǎn)到根節(jié)點(diǎn)的右子樹（Right）的左子樹（Left）,導(dǎo)致根節(jié)點(diǎn)的平衡因子

由-1變?yōu)?2

針對四種種情況可能導(dǎo)致的不平衡，可以通過旋轉(zhuǎn)使之變平衡。有兩種基本的旋轉(zhuǎn)：

（1）左旋轉(zhuǎn)：將根節(jié)點(diǎn)旋轉(zhuǎn)到（根節(jié)點(diǎn)的）右孩子的左孩子位置

（2）右旋轉(zhuǎn)：將根節(jié)點(diǎn)旋轉(zhuǎn)到（根節(jié)點(diǎn)的）左孩子的右孩子位置

3.AVL樹的旋轉(zhuǎn)操作

AVL樹的基本操作是旋轉(zhuǎn)，有四種旋轉(zhuǎn)方式，分別為：左旋轉(zhuǎn)，右旋轉(zhuǎn)，左右旋轉(zhuǎn)（先左后右），

右左旋轉(zhuǎn)（先右后左），實(shí)際上，這四種旋轉(zhuǎn)操作兩兩對稱，因而也可以說成兩類旋轉(zhuǎn)操作。

基本的數(shù)據(jù)結(jié)構(gòu)：

1typedefstructNode*Tree;

2typedefstructNode*Node_t;

3typedefTypeint;

4

5structNode{

6Node_tleft;

7Node_tright;

8intheight;

9Typedata;

10};

11intHeight（Node_tnode）{

12returnnode->height;

13）

3.1LL

LL情況需要右旋解決，如下圖所示:

代碼為：

1Node_tRightRotate(Node_ta){

2b=a->left;

3a->left=b->right;

4b->right=a;

5a->height=Max(Height(a->left),Height(a->right));

6b->height=Max(Height(b->left),Height(b->right));

7returnb;

8

3.2RR

RR情況需要左旋解決，如下圖所示:

代碼為：

1Node_tLeftRotate(Node_ta){

2b=a->right;

3a->right=b->left;

4b->left=a;

5a->height=Max(Height(a->left),Height(a->right));

6b->height=Max(Height(b->left),Height(b->right));

7returnb;

8}

3.3LR

LR情況需要左右（先B左旋轉(zhuǎn)，后A右旋轉(zhuǎn)）旋解決，如下圖所示:

代碼為：

1Node_tLeftRightRotate(Node_ta){

2a->left=LeftRotate(a->left);

3returnRightRotate(a);

4

3.4RL

RL情況需要右左旋解決（先B右旋轉(zhuǎn)，后A左旋轉(zhuǎn)），如下圖所示:

代碼為：

1Node_tRightLeftRotate(Node_ta){

2a->right=RightRotate(a->right);

3returnLeftRotate(a);

4)

4.AVL數(shù)的插入和刪除操作

(1)插入操作：實(shí)際上就是在不同情況下采用不同的旋轉(zhuǎn)方式調(diào)整整棵樹，具體代碼如下:

1Node_tInsert(Typex,Treet){

2if(t==NULL){

3t=NewNode(x);

4}elseif(x<t->data){

5t->left=Insert(t->left);

6if(Height(t->left)-Height(t->right)==2){

7if(x<t->left->data){

8t=RightRotate(t);

9}else{

10t=LeftRightRotate(t);

11)

12)

13}else{

14t->right=Insert(t->right);

15if(Height(t->right)-Height(t->left)==2){

16if(x>t->right->data){

17t=LeftRotate(t);

18}else{

19t=RightLeftRotate(t);

20}

21}

22)

23t->height=Max(Height(t->left),Height(t->right))+1;

24returnt;

25)

(2)刪除操作：首先定位要?jiǎng)h除的節(jié)點(diǎn)，然后用該節(jié)點(diǎn)的右孩子的最左孩子替換該節(jié)點(diǎn)，并重新調(diào)

整以該節(jié)點(diǎn)為根的子樹為AVL樹，具體調(diào)整方法跟插入數(shù)據(jù)類似，代碼如下：

1Node_tDelete(Typex,Treet){

2if(t==NULL)returnNULL;

3if(t->data==x){

4if(t->right==NULL){

5Node_ttemp=t;

6t=t->left;

7free(temp);

8}else{

9Node_thead=t->right;

10while(head->left){

11head=head->left;

12)

13t->data=head->data;//justcopydata

14t->right=Delete(t->data,t->right);

15t->height=Max(Height(t->left),Height(t->right))+1;

16)

17returnt;

18}elseif(t->data<x){

19Delete(x,t->right);

20if(t->right)Rotate(x,t->right);

21}else{

22Delete(x,t->left);

23if(t->left)Rotate(x,t->left);

24)

25if(t)Rotate(x,t);

26)

5.總結(jié)

AVL樹是最早的自平衡二叉樹，相比于后來出現(xiàn)的平衡二叉樹(紅黑樹，treap,splay樹)而

言，它現(xiàn)在應(yīng)用較少，但研究AVL樹對于了解后面出現(xiàn)的常用平衡二叉樹具有重要意義。

6.參考資料

(1)數(shù)據(jù)結(jié)構(gòu)(C語言版)嚴(yán)蔚敏，吳偉民著

(2)/wiki/AVL%E6