GLIB平衡二叉搜索樹算法淺析【原】

ID:72519 · 發表于 2015-1-23 19:21

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

帳號		自動登錄	找回密碼
密碼			立即注冊

久久久久久久999_99精品久久精品一区二区爱城_成人欧美一区二区三区在线播放_国产精品日本一区二区不卡视频_国产午夜视频_欧美精品在线观看免费

GLIB平衡二叉搜索樹算法淺析【原】