第七章AVL搜寻树-Read.ppt

第七章 AVL搜尋樹 二元搜尋樹簡單易懂，不過有一個問題：它並非平衡樹。本章將介紹平衡的 AVL 搜尋樹，討論它的資料結構、函式，並設計程式使用它。 7.1 基本觀念 AVL 樹是一種搜尋樹，其左右子樹最大的高度差為一，因此稱為二元平衡樹。為了凸顯平衡與不平衡的差異，請看下列的二元樹。 AVL 樹的定義 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）。 7.2 平衡樹 每當我們插入一個節點進入一顆樹，或從一顆樹移除一個節點，都會破壞平衡，必須重新平衡它。每當偵測到一顆樹已經失去平衡的時候，就 必須再平衡一次。AVL 樹的平衡是透過節點向左旋轉（rotate）或向右旋轉達成的。本小節將說明基本的平衡演算法。 左高再插入左方 如右圖，19 的左子樹已較高，現在再插入 5 於左子樹，則 19 的左子樹（13）變成高於右子樹（21）兩個層次，變成非 AVL 樹，因此必須再平衡一下。 將19節點往右旋轉降下一個層次 右高再插入右方 將15節點往左旋轉降下一個層次 7.2.3 左方右 前面兩種情形，左方左及右方右，都是只需一次旋轉就可完成平衡，但左方右或右方左均需要兩次的旋轉才可完成平衡，下圖說明左方右的兩次旋轉例子。 7.2.4 右方左 下圖說明右方左的兩次旋轉例子。 7.3 AVL 樹實作 7.3.1 AVL二元搜尋樹資料結構 AVL 二元搜尋樹實作需要兩種不同的結構，一個頭結構以及一個資料結構。頭結構包含不屬資料的一些相關的資訊，例如資料節點計數、第一個資料節點指標、或是資料的比較方法，等等的資訊。 資料結構包含資料以及鏈欄，鏈欄的內含為下一個資料節點的指標。資料欄可以是資料本身，也可以是指到真正資料位置的指標，left 鏈欄指到下一個左子樹根節點，right 鏈欄指到下一個右子樹根節點，鏈欄其值若為 NULL 則表示不指到任何資料節點。 AVL樹資料結構 資料結構宣告如下： #define LH +1 /*Left High*/ #define EH 0 /*Even High*/ #define RH -1 /*Right High*/ struct avlNodeTag { void *dataptr; int balance; struct avlNodeTag *left, *right; }; 本案例資料結構裡的資料欄宣告為不定型態的指標「void *dataptr」，不定型態的指標與任何型態的指標相匹配，使用時只須強迫轉型為指定的型態就可使用了。平衡因子 balance 為整數。left 及 right 鏈欄都是指標，它指到下一個子樹根節點。 AVL樹頭結構 頭結構宣告如下： struct avlTag { int count; int (*compare) (void* arg1, void* arg2); struct avlNodeTag *root; }; 頭結構裡有三個成員，count 成員為節點計數。root 表 AVL 二元搜尋樹根節點的指標。compare 是兩項資料比較的函式名稱。 7.3.2