第七章 AVL搜尋樹 二元搜尋樹簡單易懂，不過有一個問題：它並非平衡樹。本章將介紹平衡的 AVL 搜尋樹，討論它的資料結構、函式，並設計程式使用它。

Presentation on theme: "第七章 AVL搜尋樹 二元搜尋樹簡單易懂，不過有一個問題：它並非平衡樹。本章將介紹平衡的 AVL 搜尋樹，討論它的資料結構、函式，並設計程式使用它。"— Presentation transcript:

1 第七章 AVL搜尋樹 二元搜尋樹簡單易懂，不過有一個問題：它並非平衡樹。本章將介紹平衡的 AVL 搜尋樹，討論它的資料結構、函式，並設計程式使用它。

2 7.1 基本觀念 AVL 樹是一種搜尋樹，其左右子樹最大的高度差為一，因此稱為二元平衡樹。為了凸顯平衡與不平衡的差異，請看下列的二元樹。

3 AVL 樹的定義 | HL - HR | <= 1 AVL 樹的定義如下： 一顆 AVL 樹是一顆二元樹，或為空白，或含兩
顆 AVL 子樹 TL 及 TR，其高度最多相差一。 | HL - HR | <= 1 HL 為左子樹高度，HR 為右子樹高度。 因為 AVL 樹以高度來衡量平衡度，故也稱為高度平衡樹。因為任何一個節點的平衡因子（balance factor）必須為 +1、0、-1，我們用一個常數識別字來表示，LH 表示 Left High 左子樹較右子樹高一層（+1），LE 表示 Left Equal 左右子樹高度相同（0），RH 表示 Right High 右子樹較左子樹高一層，亦即左子樹較右子樹低一層（-1）。

4 7.2 平衡樹 每當我們插入一個節點進入一顆樹，或從一顆樹移除一個節點，都會破壞平衡，必須重新平衡它。每當偵測到一顆樹已經失去平衡的時候，就
必須再平衡一次。AVL 樹的平衡是透過節點向左旋轉（rotate）或向右旋轉達成的。本小節將說明基本的平衡演算法。

5 左高再插入左方 如右圖，19 的左子樹已較高，現在再插入 5 於左子樹，則 19 的左子樹（13）變成高於右子樹（21）兩個層次，變成非 AVL 樹，因此必須再平衡一下。

6 將19節點往右旋轉降下一個層次 上圖顯示一個較複雜的問題，子樹 13 是平衡的，但整棵樹 19 則並不平衡，因此必須將 19 向右旋轉，讓它成為 13 節點的右子樹，這又產生另一個問題，目前當 13 節點右子樹的 15 節點如何安排？節點 19 向右旋轉時已失掉它的左子樹了，節點 15 就當 19 節點的左子樹好了，這也合乎二元搜尋樹的規定呢。

7 右高再插入右方 如上圖，15 的右子樹已較高，現在再插入 45 於右子樹，則 15 的右子樹變成高於左子樹兩個層次，變成非 AVL 樹，因此必須再平衡一下。

8 將15節點往左旋轉降下一個層次 上圖顯示一個較複雜的問題，子樹 13 是平衡的，但整棵樹 15 則並不平衡，因此必須將 15 向左旋轉，讓它成為 21 節點的左子樹，這又產生另一個問題，目前當 21 節點左子樹的 19 節點如何安排？節點 15 向左旋轉時已失掉它的右子樹了，節點 19 就當 15 節點的右子樹好了，這也合乎二元搜尋樹的規定呢。

9 7.2.3 左方右 前面兩種情形，左方左及右方右，都是只需一次旋轉就可完成平衡，但左方右或右方左均需要兩次的旋轉才可完成平衡，下圖說明左方右的兩次旋轉例子。

10 7.2.4 右方左 下圖說明右方左的兩次旋轉例子。

11 7.3 AVL 樹實作 7.3.1 AVL二元搜尋樹資料結構 AVL 二元搜尋樹實作需要兩種不同的結構，一個頭結構以及一個資料結構。頭結構包含不屬資料的一些相關的資訊，例如資料節點計數、第一個資料節點指標、或是資料的比較方法，等等的資訊。 資料結構包含資料以及鏈欄，鏈欄的內含為下一個資料節點的指標。資料欄可以是資料本身，也可以是指到真正資料位置的指標，left 鏈欄指到下一個左子樹根節點，right 鏈欄指到下一個右子樹根節點，鏈欄其值若為 NULL 則表示不指到任何資料節點。

12 AVL樹資料結構 資料結構宣告如下： #define LH +1 /*Left High*/
#define EH /*Even High*/ #define RH /*Right High*/ struct avlNodeTag { void *dataptr; int balance; struct avlNodeTag *left, *right; }; 本案例資料結構裡的資料欄宣告為不定型態的指標「void *dataptr」，不定型態的指標與任何型態的指標相匹配，使用時只須強迫轉型為指定的型態就可使用了。平衡因子 balance 為整數。left 及 right 鏈欄都是指標，它指到下一個子樹根節點。

13 AVL樹頭結構 頭結構宣告如下： struct avlTag { int count;
int (*compare) (void* arg1, void* arg2); struct avlNodeTag *root; }; 頭結構裡有三個成員，count 成員為節點計數。root 表 AVL 二元搜尋樹根節點的指標。compare 是兩項資料比較的函式名稱。

14 7.3.2 建立頭結構初值 struct avlTag *avlCreate(int (*compare)
(void *arg1, void *arg2)) { struct avlTag *tree; tree = malloc(sizeof(struct avlTag)); if (tree) tree->root = NULL; tree->count = 0; tree->compare = compare; } return tree;

15 7.3.3 加入 int avlInsert(struct avlTag *tree, void *dataptr) {
struct avlNodeTag *p; int taller; p = malloc(sizeof(struct avlNodeTag)); if (p==NULL) return 0; p->balance = EH; p->right = NULL; p->left = NULL; p->dataptr = dataptr; tree->root=InsertAVL(tree,tree->root,p,&taller); (tree->count)++; return 1; } 加入

16 7.3.4 取得 void * avlGet(struct avlTag *tree, void *keyptr) {
if (tree->root) return GetAVL(tree, keyptr, tree->root); else return NULL; }

17 7.3.5 移除 int avlRemove(struct avlTag *tree, void * delkey) {
int shorter; int success; struct avlNodeTag *p; p = RemoveAVL(tree, tree->root, delkey, &shorter, &success); if (success) tree->root = p; (tree->count)--; return 1; } else return 0; 移除

18 7.3.6 測試空白 int avlEmpty(struct avlTag *tree) {
return (tree->count == 0); }

19 7.3.7 測試滿載 int avlFull(struct avlTag *tree) { struct avlNodeTag *p;
p = malloc(sizeof(*(tree->root))); if (p!=NULL) free(p); return 0; } else return 1;

20 7.3.8 傳回資料項數 int avlCount(struct avlTag *tree) {
return (tree->count); }

21 7.3.9 釋放記憶體 struct avlTag *avlRelease(struct avlTag *tree) {
if (tree!=NULL) ReleaseAVL(tree->root); free(tree); return NULL; }

22 7.4 AVL 二元搜尋樹應用 將前面有關 AVL 二元搜尋樹的資料結構以及函式存入 avl.h 表頭檔備用。

23 7.4.1 數字所建平衡樹 struct avlTag *tree; tree = avlCreate(compare);
程式 numavl.c 從整數陣列 k 取得一系列的整數如下： 若以此建立一般的二元樹的話，它是斜向左邊的不平衡樹，其高度差為八。以此資料建立一棵 AVL 樹，其高度為四，高度差 HL-HR=1。 struct avlTag *tree; tree = avlCreate(compare); 首先建立一棵空白的 AVL 樹 tree。

24 插入 AVL 樹 tree 裡的適當位置 for (i=0; i<sizeof(k)/sizeof(int); i++) {
dataptr = (int *)malloc(sizeof(int)); *dataptr = k[i]; avlInsert(tree, dataptr); } 取得一塊記憶體 dataptr，將 k[i] 存入 dataptr 記憶體，然後透過 avlInsert() 函式將 dataptr 資料插入 AVL 樹 tree 裡的適當位置。

25 中序遍訪每一個節點 avlTraverse(tree, printNum);
dumpTree(tree->root); 刻意以前序遍訪每一個節點，將該節點的每一個資料欄位值列印出來核對 AVL 樹是否正確，跟據這些資料可畫出整棵 AVL 樹，如下圖 7.8 所示。

26 The AVL binary search tree contains : 9 13 15 19 21 24 45 53
input data : The AVL binary search tree contains : 從執行結果可以看出，我們的輸入資料 53 至 9 是已經由大到小排成順序的，以一般的二元搜尋樹是不平衡的，從根節點往下，每一層次都沒有右子樹，但建成 AVL 樹後變成平衡樹如上圖所示。

27 當依序插入 53、45、24 後，原本的樹應該如下圖（a）所示，左子樹原已較高，今插入 24 節點後左子樹更高了，因此必須平衡，將根節點的 53 向右旋轉，變成 45 節點的右子樹，如下圖的（b）所示。

28 插入 21、19 後，原本的樹應該如下圖（a）所示，左子樹原已較高，今插入 19 節點後左子樹更高了，因此必須平衡，節點 24 向右旋轉變成 21 節點的右子樹，如下圖的（b）所示。

29 插入 15 後，原本的樹應該如下圖（a）所示，左子樹原已較高，今插入 15 節點後左子樹更高了，因此必須平衡，節點 45 向右旋轉變成節點 21 的右子樹，如下圖的（b）所示。

30 插入 13 後，原本的樹應該如下圖（a）所示，左子樹原已較高，今插入 13 節點後左子樹更高了，因此必須平衡，節點 19 向右旋轉變成節點 15 的右子樹，如下圖的（b）所示。

31 7.4.2 字組統計 上一個例子 numavl.c 所使用的資料只是單純的整數，現在要舉一個屬於結構的資料。
程式 words.c 從一個本文檔案 zoo.txt 讀取一篇本文，它是台北木柵動物園的園區介紹，其資料如下： Formasan Animal Area, Children's Zoo Area, Asian Tropical rainforests Area, Desert Animal Area, Australian Animal Area, Africa Animal Area, Temperate Zone Animal Area, Bird World Area. 將此本文讀入，統計每一個字組出現的次數。

32 字組所使用的資料結構 每一個字組所使用的資料結構宣告如下： #define STRLEN 21 struct wordNodeTag {
char word[STRLEN]; int count; }; 識別字常數 STRLEN 定義為 21，表示字組 word 最長為二十個字元。count 表該字組出現的次數。

33 比較函式 int compareWords(void *arg1, void *arg2) {
struct wordNodeTag *wp1=arg1; struct wordNodeTag *wp2=arg2; return (strcmp(wp1->word, wp2->word)); } 比較函式命名為 compareWords，對於字組結構裡的字組字串相比較，傳回其比較的結果，前者較小則傳回負整數，相等則傳回零值，較大則傳回正整數。

34 主程式的作業 struct avlTag *tree; tree = avlCreate(compareWords);
buildTree(tree); printTree(tree); printf("\ndump AVL tree:"); dumpTree(tree->root); 這是主程式的作業，首先建立一棵空白的 AVL 二元樹 tree 使用比較 compareWords 函式，然後透過 buildTree() 函式從 zoo.txt 本文檔讀取本文建立一棵 AVL 樹 tree。使用 printTree() 函式以中序遍訪列印出該樹的所有節點。最後刻意以前序遍訪傾印每一個節點的欄位值以利核對。

35 words.c執行後所建立的AVL平衡樹

36 7.4.3 字串平衡樹 從字串陣列 k[ ] 取得每一個字串元素，建立一個 AVL 平衡樹，資料如下： #define STRLEN 16
char k[ ][STRLEN]={"Zone", "Bird", "Asian", "Animal", "Africa", "Australian", "Formasan"};

37 "Zone"向右旋轉成"Bird"右子樹 依序插入 "Zone"、"Bird"、"Asian" 後，原本的樹應該如下圖（a）所示，左子樹原已較高，今插入 "Asian" 節點後左子樹更高了，因此必須平衡，將根節點的 "Zone" 向右旋轉，變成 "Bird" 節點的右子樹，如下圖的（b）所示。

38 "Asian"向右旋轉成"Animal"右子樹 插入 "Animal"、"Africa" 後，原本的樹應該如下圖（a）所示，左子樹原已較高，今插入 "Africa" 節點後左子樹更高了，因此必須平衡，將節點 "Asian" 向右旋轉，變成 "Animal" 節點的右子樹，如下圖的（b）所示。

39 "Animal"左轉"Bird"右轉達成平衡 插入 "Austrlian" 後，原本的樹應該如下圖（a）所示，左子樹原已較高，今插入 "Australian" 節點後變成右子樹較高了，因此必須平衡，將節點 "Animal" 向左旋轉，變成 "Asian" 節點的左子樹，如下圖的（b）所示。這時左子樹較高，仍未平衡，將節點 "Bird" 向右旋轉，當節點 "Asian" 的右子樹，才完成平衡，如下圖（c）所示。

40 字串平衡樹 最後將 "Formasan" 插入 "Zone" 左邊，完成平衡樹，如下圖所示。

41 若輸入反序，從 9 至 53，則所建立的 AVL 樹會不一樣的，資料相同，但順序不同，所建立的樹當然不一樣，如下圖所示。