|
|
<p>GLIB平衡二叉搜索樹算法淺析</p><p>一．樹的基本概念</p><p>樹，在計(jì)算機(jī)領(lǐng)域中，它是一種十分基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)，幾乎所有操作系統(tǒng)都將文件存放在樹狀結(jié)構(gòu)里，幾乎所有的編譯器都需要實(shí)現(xiàn)一個表達(dá)式樹等等。</p><p> 樹由節(jié)點(diǎn)和邊組成；如圖一，整個樹有一個最上端節(jié)點(diǎn)，稱為根節(jié)點(diǎn)（root），每個節(jié)點(diǎn)可以擁有具有方向性的邊，用它來和其它節(jié)點(diǎn)相連。相連節(jié)點(diǎn)之中，以上者稱為父節(jié)點(diǎn)，在下者稱為子節(jié)點(diǎn)。無子節(jié)點(diǎn)稱為葉節(jié)點(diǎn)。子節(jié)點(diǎn)可以存在多個，如果最多只允許兩個子節(jié)點(diǎn)，即所謂的二叉樹。不同的節(jié)點(diǎn)如果擁有相同的父節(jié)點(diǎn)，彼此互稱為兄弟節(jié)點(diǎn)。跟節(jié)點(diǎn)至任何節(jié)點(diǎn)之間有唯一的路徑，路徑所經(jīng)過的邊數(shù)，稱為路徑長度。根節(jié)點(diǎn)至任一節(jié)點(diǎn)的路徑長度，即所謂該節(jié)點(diǎn)的深度。根節(jié)點(diǎn)的深度永遠(yuǎn)都為0。某節(jié)點(diǎn)至其最深子節(jié)點(diǎn)（葉節(jié)點(diǎn)）的路徑長度，稱為該節(jié)點(diǎn)的高度。整棵樹的高度，便以根節(jié)點(diǎn)的高度來代表。</p><p><img src="http://c.51hei.com/a/old/up/0/512311261930791.jpg" small="0"></p><p>圖一</p><p>二．平衡二叉搜索樹BBST(Balancing Binary Search Tree)</p><p> 所謂二叉搜索樹，即二叉樹，上面也講到，即“任何節(jié)點(diǎn)最多只允許有兩個子節(jié)點(diǎn)”。這兩個子節(jié)點(diǎn)稱為左子節(jié)點(diǎn)和右子節(jié)點(diǎn)，二叉樹的運(yùn)用極廣，在linux內(nèi)核中所使用的就是二叉樹中的紅黑樹，上面提到的幾乎所有的編譯器都需要實(shí)現(xiàn)一個表達(dá)式樹也是使用的二叉樹，同時本文所要講解的glib里面的樹結(jié)構(gòu)也是使用的二叉樹。</p><p> 我們對數(shù)的操作，無非就是對樹進(jìn)行插入、刪除、查找等操作。而這些操作都要是對樹的節(jié)點(diǎn)進(jìn)行操作，那怎么入手呢，好在二叉樹有這么一個規(guī)則：任何一個節(jié)點(diǎn)的鍵值一定大于左子樹中每一個節(jié)點(diǎn)的鍵值，并小于右子樹中每一個節(jié)點(diǎn)的鍵值。因此，從根節(jié)點(diǎn)一直往左走，直至無路可走，可查得最小元素；反之，從右走，可得到最大元素。</p><p> 也許因?yàn)槟承┎迦牖騽h除的鍵值不夠隨機(jī)，二叉樹可能會失去平衡，造成搜尋效率低落的情況，圖二是極度平衡樹跟極度不平衡樹的狀況。</p><p><img src="http://c.51hei.com/a/old/up/0/512311261929276.jpg" small="0"></p><p>圖二</p><p> 樹的平衡與否，并沒有一個絕對的衡量標(biāo)準(zhǔn)。平衡的大致意義是沒有任何一個節(jié)點(diǎn)的深度過大。有數(shù)種結(jié)構(gòu)如AVL-tree、RB-tree、AA-tree均可實(shí)現(xiàn)平衡二叉樹，它們都比一般的二叉樹復(fù)雜，插入和刪除節(jié)點(diǎn)的平均時間也比較長，但它們可以避免極難對付的最壞（高度不平和）情況，而且因?yàn)樗麄兛偸潜３制胶猓栽氐乃褜に钑r間也就比較小，比一般要省25%。</p><p> 在GLIB中所使用的平衡二叉樹結(jié)構(gòu)是AVL-tree，所以本文主要分析AVL-tree數(shù)據(jù)結(jié)構(gòu)的插入跟刪除方法，但是不會分析其源碼實(shí)現(xiàn)，讀者可以自行分析其結(jié)構(gòu)。</p><p> 在計(jì)算機(jī)科學(xué)中，AVL樹是最先發(fā)明的自平衡二叉查找樹。在AVL樹中任何節(jié)點(diǎn)的兩個兒子子樹的高度最大差別為一，所以它也被稱為高度平衡樹。查找、插入和刪除在平均和最壞情況下都是O（log n）。增加和刪除可能需要通過一次或多次樹旋轉(zhuǎn)來重新平衡這個樹。AVL樹得名于它的發(fā)明者 G.M. Adelson-Velsky 和 E.M. Landis，他們在 1962 年的論文《An algorithm for the organization of information》中發(fā)表了它。</p><p>1. BBST的插入：</p><p> 插入一個葉節(jié)點(diǎn)只有插入點(diǎn)至根節(jié)點(diǎn)路徑上各節(jié)點(diǎn)可能會破壞AVL的平衡條件。由于只有只有插入點(diǎn)至根節(jié)點(diǎn)路徑上各節(jié)點(diǎn)可能會破壞AVL的平衡條件，因此只需要調(diào)整最深的那個節(jié)點(diǎn)，便可使整棵樹重新獲得平衡。假設(shè)最深節(jié)點(diǎn)為Root【失去平衡樹的根節(jié)點(diǎn)】，由于節(jié)點(diǎn)最多擁有兩個子節(jié)點(diǎn)，而所謂的平衡破壞就是左右子樹的高度相差2，因此可以分為如下四種情況：</p><p>a) 插入點(diǎn)位于Root的左子節(jié)點(diǎn)的左子樹—左左情況</p><p>b) 插入點(diǎn)位于Root的右子節(jié)點(diǎn)的右子樹—右右情況</p><p>c) 插入點(diǎn)位于Root的左子節(jié)點(diǎn)的右子樹—左右情況</p><p>d) 插入點(diǎn)位于Root的右子節(jié)點(diǎn)的左子樹—右左情況</p><p>情況a) 跟 b) 是從外側(cè)插入，可以通過單旋來調(diào)整；c) 跟 d) 為內(nèi)側(cè)插入，可以通過雙旋轉(zhuǎn)來調(diào)整，如下圖所示。</p><p><img src="http://c.51hei.com/a/old/up/0/512311261986769.jpg" small="0" height="508" width="758"></p><p>插入算法實(shí)現(xiàn)：</p><p>在平衡的二叉搜索樹 BBST上插入一個新的數(shù)據(jù)元素e的遞歸算法可描述如下：</p><p>1) 若BBST為空樹，則插入一個數(shù)據(jù)元素為e的新結(jié)點(diǎn)作為BBST的根結(jié)點(diǎn)，樹的深度增1； </p><p>2) 若e的關(guān)鍵字和BBST的根結(jié)點(diǎn)的關(guān)鍵字相等，則不進(jìn)行； </p><p>3) 若e的關(guān)鍵字小于BBST的根結(jié)點(diǎn)的關(guān)鍵字，而且在BBST的左子樹中不存在和e有相同關(guān)鍵字的結(jié)點(diǎn)，則將e插入在BBST的左子樹上，并且當(dāng)插入之后的左子樹深度增加（+1）時，分別就下列不同情況處理之： </p><p>1.1) BBST的根結(jié)點(diǎn)的平衡因子為-1（右子樹的深度大于左子樹的深度，則將根結(jié)點(diǎn)的平衡因子更改為0，BBST的深度不變； </p><p>1.2) BBST的根結(jié)點(diǎn)的平衡因子為0（左、右子樹的深度相等）：則將根結(jié)點(diǎn)的平衡因子更改為1，BBST的深度增1； </p><p>1.3) BBST的根結(jié)點(diǎn)的平衡因子為1（左子樹的深度大于右子樹的深度）：則若BBST的左子樹根結(jié)點(diǎn)的平衡因子為1：則需進(jìn)行單向右旋平衡處理，并且在右旋處理之后，將根結(jié)點(diǎn)和其右子樹根結(jié)點(diǎn)的平衡因子更改為0，樹的深度不變； </p><p>4) 若e的關(guān)鍵字大于BBST的根結(jié)點(diǎn)的關(guān)鍵字，而且在BBST的右子樹中不存在和e有相同關(guān)鍵字的結(jié)點(diǎn)，則將e插入在BBST的右子樹上，并且當(dāng)插入之后的右子樹深度增加（+1）時，分別就不同情況處理之。 </p><p>2. BBST的刪除：</p><p> 我們先來回顧下二叉搜索樹的刪除節(jié)點(diǎn)z的過程：如果z沒有子節(jié)點(diǎn)，那么直接刪除即可；如果z只有一個子節(jié)點(diǎn)，那么讓這個子節(jié)點(diǎn)來代替z的 位置，然 后把z刪除即可；如果z有兩個子節(jié)點(diǎn)，那么找到z在中序遍歷中的后繼節(jié)點(diǎn)s（也就是從z->rchild開始向左下方一直走到底的那一個節(jié)點(diǎn)），把 s的key賦值給z的key，然后刪除s。</p><p> 那么AVL-tree刪除節(jié)點(diǎn) z的方法首先也是按部就班以上的過程，這過程從根本上講其實(shí)就是刪除葉節(jié)點(diǎn)。刪除一個葉節(jié)點(diǎn)只有刪除點(diǎn)的父節(jié)點(diǎn)至根節(jié)點(diǎn)路徑上各節(jié)點(diǎn)可能會破壞AVL的平衡條件。由于只有刪除點(diǎn)的父節(jié)點(diǎn)至根節(jié)點(diǎn)路徑上各節(jié)點(diǎn)可能會破壞AVL的平衡條件，因此只需要調(diào)整最深的那個節(jié)點(diǎn)，便可使整棵樹重新獲得平衡，處理方法跟插入節(jié)點(diǎn)調(diào)整平衡的方法及其相似。</p><p>刪除算法實(shí)現(xiàn)：</p><p>三．RB-tree簡介</p><p> RB-tree即紅黑樹，也是一種自平衡二叉查找樹。紅黑樹的每個節(jié)點(diǎn)上的屬性除了有一個key、3個指針：parent、lchild、rchild以外，還多了一個屬性：color。它只能是兩種顏色：紅或黑。而紅黑樹除了具有二叉搜索樹的所有性質(zhì)之外，還具有以下4點(diǎn)性質(zhì)：</p><p>1. 根節(jié)點(diǎn)是黑色的。</p><p>2. 空節(jié)點(diǎn)是黑色的（紅黑樹中，根節(jié)點(diǎn)的parent以及所有葉節(jié)點(diǎn)lchild、rchild都不指向NULL，而是指向一個定義好的空節(jié)點(diǎn)）。</p><p>3. 紅色節(jié)點(diǎn)的父、左子、右子節(jié)點(diǎn)都是黑色。</p><p>4. 在任何一棵子樹中，每一條從根節(jié)點(diǎn)向下走到空節(jié)點(diǎn)的路徑上包含的黑色節(jié)點(diǎn)數(shù)量都相同。</p><p>這些約束強(qiáng)制了紅黑樹的關(guān)鍵性質(zhì): 從根到葉子的最長的可能路徑不多于最短的可能路徑的兩倍長。結(jié)果是這個樹大致上是平衡的。</p><p> 本文就簡單介紹下紅黑樹的性質(zhì)，具體關(guān)于插入、刪除等操作可以參考本文所引用的參考資料。</p><p>四．參考資料</p><p>l AVL樹 - 維基百科，自由的百科全書</p><p>l 紅黑樹 - 維基百科，自由的百科全書</p><p>l STL源碼分析</p>
|
|
