數據結構 - 第三部分.ppt

1、1,第三部分 集合,集合中的元素互相之間沒有關系 集合的存儲：借用其他容器 集合的操作：查找和排序 這一部分將介紹 查找表 排序算法 散列表 不相交集,2,第7章 集合與靜態(tài)查找表,集合的基本概念 查找的基本概念 無序表的查找 有序表的查找 STL中的靜態(tài)表,3,集合的基本概念,集合中的數據元素除了屬于同一集合之外，沒有任何邏輯關系。 在集合中，每個數據元素有一個區(qū)別于其他元素的唯一標識，通常稱為鍵值或關鍵字值 集合的主要運算： 查找某一元素是否存在 將集合中的元素按照它的唯一標識排序,4,集合的存儲,任何容器都能存儲集合 常用的表示形式是借鑒于線性表或樹 唯一一個僅適合于存儲和處理集合的數據

2、結構是散列表,5,第7章 集合與靜態(tài)查找表,集合的基本概念 查找的基本概念 無序表的查找 有序表的查找 STL中的靜態(tài)表,6,查找的基本概念,用于查找的集合稱之為查找表 查找表的分類： 靜態(tài)查找表 動態(tài)查找表。 內部查找 外部查找,7,靜態(tài)查找表的存儲,靜態(tài)查找表可以用順序表存儲。 如C+的標準模板庫中的類模板vector，或第二章中定義的seqList，或直接存儲在C+的原始數組中。 查找函數應該是一個函數模板。模板參數是數據元素的類型。,8,第7章 集合與靜態(tài)查找表,集合的基本概念 查找的基本概念 無序表的查找 有序表的查找 STL中的靜態(tài)表,9,無序表的查找,無序表：數組中的元素是無序的

3、 無序表的查找：毫無選擇只能做線性的順序查找,template int seqSearch(vector ,10,第7章 集合與靜態(tài)查找表,集合的基本概念 查找的基本概念 無序表的查找 有序表的查找 STL中的靜態(tài)表,11,有序表的查找,順序查找 二分查找 插值查找 分塊查找,12,順序查找,與無序表的順序查找類似，只是當被查元素在表中不存在時，不需要查到表尾,template int seqSearch(vector ,13,有序表的查找,順序查找 二分查找 插值查找 分塊查找,14,二分查找,每次檢查待查數據中排在最中間的那個元素 如中間元素等于要查找的元素，則查找完成 否則，確定要找的數

4、據是在前一半還是在后一半，然后縮小范圍，在前一半或后一半內繼續(xù)查找。,15,查找 x=8,16,template int binarySearch(const vector ,17,有序表的查找,順序查找 二分查找 插值查找 分塊查找,18,插值查找,適用于數據的分布比較均勻的情況 查找位置的估計 缺點：計算量大,19,插值查找適用情況,訪問一個數據元素必須比一個典型的指令費時得多。例如，數組可能在磁盤里而不是在內存里，而且每次比較都需要訪問一次磁盤。 這些數據必須不僅有序，而且分布相當均勻，這可以使每次估計都相當準確，可以將大量的數據排除出查找范圍。這樣，花費這些計算代價是值得的,20,有序

5、表的查找,順序查找 二分查找 插值查找 分塊查找,21,分塊查找,分塊查找也稱為索引順序塊的查找。 是處理大量數據查找的一種方法。 它把整個有序表分成若干塊，塊內的數據元素可以是有序存儲，也可以是無序的，但塊之間必須是有序的。,22,查找由兩個階段組成：查找索引和查找塊,23,第7章 集合與靜態(tài)查找表,集合的基本概念 查找的基本概念 無序表的查找 有序表的查找 STL中的靜態(tài)表,24,STL中的靜態(tài)表,對應于順序查找和二分查找，C+的標準模板庫中提供兩個模板函數：find和binary_search。這兩個函數模板都位于標準庫algorithm中 find函數順序查找一個序列 find有兩個模

6、板參數。第一個模板參數是對應于存儲集合數據的容器的迭代器。第二個模板參數是集合元素的類型。 函數有三個形式參數。第一、二個形式參數是兩個迭代器對象，指出查找的范圍。第三個參數是需要查找的對象值。 find函數的返回值是一個迭代器對象，指出了被查找的元素在容器中的位置。,25,binary_search,binary_search函數用二分查找的方式查找一個有序序列。 它也有兩個模板參數。第一個模板參數是對應于存儲集合數據的容器的迭代器。第二個模板參數是集合元素的類型。 函數也有三個形式參數。第一、二個形式參數是兩個迭代器對象，指出查找的范圍。第三個參數是需要查找的對象值。 函數的返回值是boo

7、l類型的，指出了被查找的元素在容器中是否存在。如果存在，返回true，否則，返回false。,26,應用實例,#include #include #include using namespace std; int main() int a = 2,4,7,8,10,12,13,15,16,19,20; vector v; vector:iterator itr; for (int i=0; i11; +i) v.push_back(ai); if (binary_search(v.begin(), v.end(),13) cout 13 存在n; else cout 13 不存在n; itr

8、= find(v.begin(), v.end(),13); cout *itr endl; return 0; ,27,總結,本章介紹了集合關系的基本概念，以及集合類型的數據結構中的基本操作。 針對靜態(tài)的集合，介紹了查找操作的實現。包括順序查找、二分查找、插值查找和分塊查找。 最后還介紹了STL中的查找函數：find和binary_search。find實現了順序查找，binary_search實現了二分查找。,28,第8章 動態(tài)查找表,二叉查找樹 AVL樹 紅黑樹 AA樹 伸展樹 B樹和B+樹 STL中的動態(tài)查找表,既要支持快速查找，又要支持插入刪除，通常選用樹作為存儲的載體,29,二叉查

9、找樹,二叉查找樹的定義 二叉查找樹的操作 二叉查找樹的性能 二叉查找樹類的實現,30,二叉查找樹,如果p的左子樹若非空，則左子樹上的所有結點的關鍵字值均小于p結點的關鍵字值。 如果p的右子樹若非空，則右子樹上的所有結點的關鍵字值均大于p結點的關鍵字值。 結點p的左右子樹同樣是二叉查找樹。,二叉查找樹是二叉樹在查找方面的重要應用。二叉查找樹或者為空，或者具有如下性質：對任意一個結點p而言,31,e、g：二叉查找樹,32,二叉查找樹,二叉查找樹的定義 二叉查找樹的操作 二叉查找樹的性能 二叉查找樹類的實現,33,二叉查找樹的操作,特定節(jié)點在樹上是否存在 插入一個節(jié)點 刪除一個節(jié)點,由于樹是遞歸定義

10、的，因此這些操作往往也用遞歸實現。因為二叉樹的平均高度為logN，這些操作的時間復雜度也是O(logN),34,查找過程,若根結點的關鍵字值等于查找的關鍵字，成功。 否則，若關鍵字值小于根結點，查其左子樹。若關鍵字值大于根結點，查其右子樹。在左右子樹上的操作類似。,35,如：查找122， 查找110， 查找230， 查找225,36,查找過程的遞歸描述,如果樹為空，返回false 如果根節(jié)點等于被查結點，返回true 如果被查節(jié)點小于根節(jié)點，遞歸查找左子樹，否則遞歸查找右子樹,37,插入操作,若二叉樹為空。則新插入的結點成為根結點。 如二叉樹非空 首先執(zhí)行查找算法，找出被插結點的父親結點。 判

11、斷被插結點是其父親結點的左、右兒子。將被插結點作為葉子結點插入。,注意：新插入的結點總是葉子結點,38,將數的序列：122、99、250、110、300、280 作為二叉查找樹的結點的關鍵字值，生成二叉查找樹。,122,250,300,110,280,99,39,插入操作的遞歸實現,如果當前樹為空，插入值作為樹的根節(jié)點，返回 如果插入值小于根節(jié)點，插入到左子樹，否則插入到右子樹。,40,執(zhí)行實例：插入值為 280 的結點,41,刪除操作,刪除葉結點 刪除有一個兒子的結點 刪除有兩個兒子的結點,42,刪除葉結點,直接刪除，更改它的父親結點的相應指針字段為空。這不會改變二叉查找樹的特性。如：刪除數

12、據字段為 15、70 的結點。,43,刪除操作,刪除葉結點 刪除有一個兒子的結點 刪除有兩個兒子的結點,44,只有一個兒子,122,250,300,200,230,216,400,450,500,45,122,250,110,200,99,105,400,450,500,46,若被刪結點只有一個唯一的兒子，將此兒子取代被刪結點的位置。即，如被刪結點是其父結點的左孩子，那么將他的兒子作為父結點的左孩子；如被刪結點是其父結點的有孩子，那么將他的孩子作為父結點的右孩子。 能保持二查查找樹的有序性,47,刪除操作,刪除葉結點 刪除有一個兒子的結點 刪除有兩個兒子的結點,48,被刪結點有兩個兒子,通常的

13、做法：選取“ 替身”取代被刪結點。有資格充當該替身的是誰哪？ 替身的要求：維持二叉查找樹的特性不變。因此，只有在中序周游中緊靠著被刪結點的結點才有資格作為“替身”，即， 左子樹中最大的結點 或 右子樹中最小的結點。,刪除這個結點會使其他結點從樹上脫離。,49,250,300,200,99,105,330,316,400,450,500,被刪結點,替身,做法：將替身110的數據字段復制到被刪結點的數據字段。 將結點 110 的左兒子作為 99 的右兒子。,用左子樹中的最大值做替身,122,110,50,250,300,110,99,105,330,316,400,450,500,被刪結點,替身,

14、做法：將替身的數據字段復制到被刪結點的數據字段。將結點 200 的右兒子作為200 的父結點的左兒子。,用右子樹的最小值做替身,122,200,51,結論： 先將替身的數據字段復制到被刪結點 將原替身的另一兒子作為它的父親結點的兒子，究竟是作為左兒子還是右兒子依原替身結點和其父親結點的關系而定 釋放原替身結點的空間。,52,刪除總結,PL、PR皆 空， 直接刪除 。,PL或PR為空,PL為空，刪除后的情況。,53,用左子樹的最大值代替,54,刪除的遞歸實現,如果是空樹，返回 如果被刪節(jié)點小于根節(jié)點，遞歸在左子樹上刪除 如果被刪節(jié)點大于根節(jié)點，遞歸在右子樹刪除 如果被刪節(jié)點等于根節(jié)點 如果根節(jié)點

15、有兩個兒子，將右子樹的最小值放入根節(jié)點，在右子樹上刪除最小節(jié)點 如果只有左子樹，左子樹取代根節(jié)點，刪除原來的根節(jié)點 如果只有右子樹，右子樹取代根節(jié)點，刪除原來的根節(jié)點,55,二叉查找樹,二叉查找樹的定義 二叉查找樹的操作 二叉查找樹的性能 二叉查找樹類的實現,56,二叉查找樹性能,二叉查找樹的操作（包括insert、find和delete等）的代價正比于操作過程中要訪問的結點數。如果所操作的二叉查找樹是完全平衡的，那么訪問的代價將是對數級別的 在最壞的請況下，二叉查找樹會退化為一個單鏈表。時間復雜度是O(N)。,57,平均性能,n 個結點二叉查找樹的可能有n種形態(tài)，如果這些形態(tài)出現的概率是相等

16、的。設P（n）為查找n個結點的二叉查找樹的平均查找時間，則,58,二叉查找樹,二叉查找樹的定義 二叉查找樹的操作 二叉查找樹的性能 二叉查找樹類的實現,59,二叉排序樹類的設計,采用標準的二叉鏈表存儲一棵二叉查找樹需要一個指向根節(jié)點的數據成員 公有的成員函數：find、insert和remove 以及構造、析構函數 二叉查找樹的插入、刪除和查找都是通過遞歸實現的，而這三個公有函數的參數表中并不需要包含遞歸參數。為此，對于每個公有的成員函數都定義了一個對應的帶有遞歸參數的私有的成員函數,60,二叉排序樹類的定義,template class BinarySearchTree private: s

17、truct BinaryNode Type data; BinaryNode *left; BinaryNode *right; BinaryNode( const Type ,61,public: BinarySearchTree( BinaryNode *t = NULL ) root = t; BinarySearchTree( ); bool find( const Type ,62,二叉排序樹類的設計特點,一個內嵌的BinaryNode類 數據成員只有一個，樹根 公有的成員函數通過調用私有的遞歸函數完成相應的功能,63,find函數的實現,template bool BinarySe

18、archTree:find( const Type ,64,insert函數的實現,template void BinarySearchTree:insert( const Type ,65,insert函數設計說明,私有的insert函數的第二個形式參數，它是一個指向結點的指針的非常量引用。 這個引用符號不能省略。正是這個引用，使得新插入的結點和它的父結點之間關聯(lián)了起來。,66,remove函數的實現,template void BinarySearchTree:remove( const Type ,67,template void BinarySearchTree:remove( con

19、st Type ,68,remove函數設計說明,同樣請注意私有的remove函數的參數，它的第二個參數也是指向結點的指針的引用。 與插入過程一樣，這個引用也不能去掉。正是這個引用使得被刪結點的父結點和被刪結點的兒子連接起來。,69,二叉查找樹類的使用,int main () int a = 10, 8, 6, 21, 87, 56, 4, 0 , 11, 3, 22, 7, 5, 34, 1, 2, 9; BinarySearchTree tree; for (int i = 0; i 17; +i) tree.insert(ai); cout endl find 2 is (tree.fi

20、nd(2)?true:false) endl; tree.remove(2); cout after delete 2, find 2 is (tree.find(2)?true:false) endl; cout find 3 is (tree.find(3)?true:false) endl; tree.remove(3); cout after delete 3, find 3 is (tree.find(3)?true:false) endl; cout find 21 is (tree.find(21)?true:false) endl; tree.remove(21); cout

21、after delete 21, find 21 is (tree.find(21)?true:false) endl; return 0; ,70,71,第8章 動態(tài)查找表,二叉查找樹 AVL樹 紅黑樹 AA樹 伸展樹 B樹和B+樹 STL中的動態(tài)查找表,72,AVL樹,AVL樹的定義 AVL樹的插入操作 AVL樹的刪除 AVL樹類的實現,73,平衡二叉查找樹,當樹退化為鏈表時，樹的優(yōu)點蕩然無存。要使查找樹的性能盡可能好，就要使得樹盡可能豐滿。要構造一個豐滿樹很困難，一種替代的方案是平衡樹。,74,二叉平衡樹,二叉平衡樹就是滿足某種平衡條件的二叉查找樹 平衡條件： 容易維護 保證樹的高度是O

22、(logN),75,平衡條件,最簡單的想法是讓左右子樹有同樣的高度。但它并不能保證樹是矮胖的。 另一個想法是要求每個節(jié)點的左右子樹都有同樣的高度。這個條件能保證樹是矮胖的，但這個條件太苛刻，只有滿二叉樹才滿足這個條件。 將上述條件稍微放寬一些就是二叉平衡查找樹。,76,平衡樹的定義,平衡因子（平衡度）：結點的平衡度是結點的左子樹的高度右子樹的高度。 空樹的高度定義為-1。 平衡二叉樹：每個結點的平衡因子都為 1、1、0 的二叉樹。或者說每個結點的左右子樹的高度最多差1的二叉樹。 可以證明平衡樹的高度至多約為：1.44log(N+2) -1.328,77,是平衡樹不是豐滿樹,不是平衡樹,78,平

23、衡二叉樹的查找性能,定理：具有 N 個結點的平衡樹，高度 h 滿足：log2(N+1) = h = 1.44log2(N+1) - 0.328;,與二叉樹的高度成正比,因此，平衡二叉樹的操作都是O(logN),79,AVL樹,AVL樹的定義 AVL樹的插入操作 AVL樹的刪除 AVL樹類的實現,80,插入操作,插入過程與二叉查找樹的插入相同，只是插入后可能出現兩種情況： 插入后，不破壞平衡性，只是改變了樹根到插入點的路徑上的某些結點的平衡度，因此需要自底向上修改節(jié)點的平衡度 破壞了路徑上的某些結點的平衡性，需要向上調整樹的結構,81,14,12,5,3,9,28,63,53,60,50,17,

24、18,7,30,+1,+1,-1,-1,-1,0,0,0,0,0,0,0,0,只改變了某些結點的平衡度，需要自底向上的調整。只要有一個節(jié)點的平衡度不變，它上面的節(jié)點的平衡度也不變。調整可以結束。,插入29,0,+1,0,82,平衡樹,插入2以后，變得不平衡了。如何用最簡單、最有效的辦法保持平衡分類二叉樹的性質不變？,83,調整要求： 希望不涉及到危機結點的父親結點，即以危機結點為根的子樹的高度應保持不變。調整可以到此結束。 仍應保持分類二叉樹的性質不變,84,重新平衡,如果節(jié)點原來的平衡度為0，則插入后不可能失衡，重新計算平衡度，繼續(xù)往上回溯 如果節(jié)點原來的平衡度非0，可能成為失衡節(jié)點 重新計

25、算平衡度 如果平衡度在合法范圍，調整結束 如果失去平衡，重新調整樹的結構，調整結束,從插入位置向根回溯,85,可能引起節(jié)點不平衡的情況,在節(jié)點的左孩子的左子樹上插入（LL） 在節(jié)點左孩子的右子樹上插入（LR） 在節(jié)點的右孩子的左子樹上插入（RL） 在節(jié)點的右孩子的右子樹上插入（RR）,86,可能引起不平衡的情況,LL RR：LL的鏡像對稱,LR RL：LR的鏡像對稱,87,LL和RR問題,通過單旋轉來解決。即危機結點和引起危機的兒子的角色轉換。 如果是LL問題，將危機結點的左兒子作為根，原來的根結點作為他的右子樹，原先的右兒子作為原先根的左兒子。 如果是RR問題，將危機結點的右兒子作為根，原來

26、的根結點作為他的左子樹，原先的左兒子作為原先根的右兒子,88,LL問題,保持了樹的有序性 保持了原先的高度,89,在下列樹中插入4，將會使得9失去平衡。這是在9的左孩子的左子樹上插入引起失衡，是LL情況,90,旋轉后的結果,保持了樹的有序性 保持了原先的高度,91,LR和RL問題,通過雙旋轉來解決，即兩次單旋轉?，F對危機結點的兒子和孫子進行一次單旋轉，使孫子變成兒子。然后是危機結點和新的兒子進行一次單旋轉。,92,LR問題,有一個結點被插入到B的右子樹的事實保證了B的右子樹不會是空的，因此我們可以假定B的右子樹為C，它有一個根和兩棵子樹（當然可能是空的）組成,93,保持了樹的有序性 保持了原先

27、的高度,LR旋轉可以看成有兩個單選轉組成：先對B執(zhí)行RR旋轉，再對A執(zhí)行LL旋轉,94,插入4后,調整后,95,AVL插入總結,用遞歸實現 要在AVL樹T中插入一個鍵值為X的結點，我們遞歸地將它插入到T的某棵合適的子樹（記做TLR）中，如果插入后TLR的高度沒有改變，就完成了操作。否則，我們就根據X和T及TLR中的鍵值選擇單旋轉或是雙旋轉（以T為根），然后操作也結束了（因為原來的高度和旋轉后的高度是一樣的）,96,AVL樹,AVL樹的定義 AVL樹的插入操作 AVL樹的刪除 AVL樹類的實現,97,平衡二叉樹的刪除,首先在AVL樹上刪除結點x 然后調整平衡,98,調整平衡,和插入操作一樣， 失

28、衡節(jié)點存在于被刪節(jié)點到根節(jié)點的路徑上 在刪除了一個結點后，必須沿著到根結點的路徑向上回溯，隨時調整路徑上的結點的平衡度。 刪除操作沒有插入操作那么幸運。插入時，最多只需要調整一個結點。而刪除時，我們無法保證子樹在平衡調整后的高度不變。只有當某個結點的高度在刪除前后保持不變，才無需繼續(xù)調整。 遞歸的刪除函數有一個布爾型的返回值。當返回值為true時，調整停止。當返回值為false時，繼續(xù)調整。,99,刪除可能出現的情況,令q是最終被刪除的結點，p是q到根結點的路徑上的某個結點。q的刪除對p的影響有以下幾種情況： 結點P的平衡因子原為0 從p的較高的子樹上刪去一個結點 從p較矮的子樹上刪除一個結點

29、,100,結點P的平衡因子原為0,從p的某棵子樹上刪除結點后，該子樹變矮，但以p為根的子樹高度不會改變。 只需要修改p的平衡因子即可。 p的高度不變，意味著它上面的結點的平衡因子都不變，調整可以結束。返回true。,101,從p的較高的子樹上刪去一個結點,從p的較高的子樹上刪除結點后，如果該子樹變矮，以p為根的子樹也變矮。但以結點P為根的這棵子樹仍然是AVL樹，而且更平衡了。 調整： 將p的平衡因子置為0 由于以p為根的子樹變矮，可能會影響p的父結點的平衡度，返回false,102,刪除2：原來結點5是左高右低，屬于情況2。刪除2以后，結點5的平衡因子變?yōu)?，以結點5為根結點的子樹也矮了一層，

30、這樣就會影響結點7的平衡度，所以繼續(xù)往上調整。對結點7而言，正好屬于情況一。所以修改7的平衡因子，調整結束。,103,從p較矮的子樹上刪除一個結點,在p的較矮的子樹上刪除一個結點，使較矮的子樹變得更矮，p的平衡度肯定遭到坡壞，此時要通過旋轉來恢復這棵子樹的平衡。 設q是p的較高的子樹的根。根據q的平衡因子的值，可以進一步細化為以下三種不同的情況： q的平衡因子為0 q的平衡因子和p的平衡因子符號相同 q的平衡因子和p的平衡因子符號相反,104,q的平衡因子為0,整棵樹高度不變，不需要繼續(xù)調整,105,q和p的平衡因子符號相同,整棵樹矮了一層，需要繼續(xù)調整,106,q和p的平衡因子符號相反,整棵

31、樹矮了一層，需要繼續(xù)調整,107,AVL樹,AVL樹的定義 AVL樹的插入操作 AVL樹的刪除 AVL樹類的實現,108,AVL樹類的實現,template class AvlTree struct AvlNode Type data; AvlNode *left; AvlNode *right; int height; AvlNode( const Type ,109,public: AvlTree( AvlNode *t = NULL ) root = t; AvlTree( ) makeEmpty( root); bool find( const Type ,110,find函數的非遞歸

32、實現,template bool AvlTree:find( const Type ,111,私有的insert函數的實現,template void AvlTree:insert( const Type ,112,LL,template void AvlTree:LL( AvlNode * ,113,RR,template void AvlTree:RR( AvlNode * ,114,LR和RL,template void AvlTree:LR( AvlNode * ,115,私有的remove函數的實現,template bool AvlTree:remove( const Type ,

33、116,if( x data ) stop = remove( x, t-left ); subTree = 1; else if( t-data right ); subTree = 2; else if( t-left != NULL ,117,switch(subTree) case 1: bf = height(t-left) - height(t-right) + 1; if (bf = 0) return true; /情況一 if (bf = 1) return false; /情況二 if (bf =-1) /情況三 int bfr = height(t-right-left)

34、 - height(t-right-right); switch (bfr) case 0: RR(t); return true; case -1: RR(t); return false; default: RL(t); return false; break;,118,case 2: bf = height(t-left) - height(t-right) -1; if (bf = 0) return true; /情況一 if (bf = -1) return false; /情況二 if (bf = 1) /情況三 int bfl = height(t-right-left) -

35、height(t-right-right); switch (bfl) case 0: LL(t); return true; case 1: LL(t); return false; default: LR(t); return false; ,119,第8章 動態(tài)查找表,二叉查找樹 AVL樹 紅黑樹 AA樹 伸展樹 B樹和B+樹 STL中的動態(tài)查找表,120,紅黑樹,紅黑樹的定義 紅黑樹的插入 紅黑樹的刪除 紅黑樹類的實現,紅黑樹是平衡樹的一種替換方案。它比平衡樹效率高。紅黑樹在最壞情況下的操作時間是O(logN),121,紅黑樹的定義,每個節(jié)點都被標記為紅色或是黑色的 根是黑色的 如果一

36、個節(jié)點是紅色的，那么它的兒子都是黑色的 每一條從某個節(jié)點到一個空鏈域的路徑必須具有相同數量的黑色節(jié)點,122,紅黑樹,紅黑樹的定義 紅黑樹的插入 紅黑樹的刪除 紅黑樹類的實現,紅黑樹是平衡樹的一種替換方案。它比平衡樹效率高。紅黑樹在最壞情況下的操作時間是O(logN),123,紅黑樹的插入,插入過程同普通的二叉查找樹，只是插入后被插入的節(jié)點要被著色 著成黑色是不可能的，會違反定義4，必須著成紅色 如果父節(jié)點是黑色的，插入結束。如果父節(jié)點是紅色的，則違反定義3。必須調整節(jié)點的顏色 把新插入的節(jié)點稱作X，P是它的父親節(jié)點，S是它父親的兄弟節(jié)點（空節(jié)點認為是黑色的），G是X祖父。,124,顏色調整總

37、結,父結點P的兄弟結點S是黑色的 X是G的外側結點：LLb，RRb X是G的內側結點：LRb，RLb 父結點P的兄弟結點S是紅色的,125,LLb，RRb,D,E,C,A,G,P,B,X,S,RRb旋轉,D,E,C,A,P,X,B,S,G,調整后，樹根為黑色。不需要繼續(xù)調整,126,LRb，RLb,LRb旋轉,B,D,E,C,A,G,S,B,P,D,E,C,A,X,G,S,RLb旋轉,X,P,調整后，樹根為黑色。不需要繼續(xù)調整,127,在樹中插入1，屬LLb的情況,128,父結點P的兄弟結點S是紅色的,通過重新著色，消除連續(xù)紅節(jié)點,129,通過重新著色，連續(xù)的紅結點就不存在了，而且路徑上的黑結

38、點數也沒有變化 。 經過重新著色以后，根結點變成了紅色。如果原來X的曾祖父就是紅色的，那么又出現了連續(xù)紅結點問題。于是，需要繼續(xù)往上調整。最壞的情況下可能要調整到根。,130,插入24,重新著色,調整20、25的連續(xù)紅節(jié)點，又是情況二。重新著色,131,紅黑樹,紅黑樹的定義 紅黑樹的插入 紅黑樹的刪除 紅黑樹類的實現,紅黑樹是平衡樹的一種替換方案。它比平衡樹效率高。紅黑樹在最壞情況下的操作時間是O(logN),132,紅黑樹的刪除,刪除操作首先使用普通的二叉查找樹的刪除算法刪除結點，然后進行旋轉及顏色的調整。 在二叉查找樹的刪除中，最終可以歸結到兩種情況：刪除葉結點和刪除只有一個兒子的結點。只

39、要解決了這兩種情況下的著色問題，就解決了紅黑樹的刪除,133,紅黑樹刪除時的情況,刪除的是紅色葉結點 ：直接刪除 刪除只有一個兒子的結點 ：將兒子的顏色改為黑色 刪除一個黑色的葉結點,134,刪除一個黑色的葉結點,被調整的結點的兄弟是黑色的（如果兄弟是空結點，則認為是黑色結點） 被調整的結點的兄弟是紅色的,刪除這個結點將會使得這個位置變成了一個空結點。因此，這條路徑上少了一個黑結點。我們將這個空結點稱為被調整結點。,135,被調整的結點的兄弟是黑色的,L0和R0：兄弟結點有0個紅孩子 L1L和R1R：兄弟有一個紅孩子，且為它的外側的孩子 L1R和R1L：兄弟有一個紅孩子，且為它的內側的孩子 L

40、2和R2：兄弟有兩個紅孩子,136,L0和R0,父節(jié)點原來可以為任意顏色。如果父結點原來是紅色的，現在變成了黑色，調整可以結束了。但如果父結點原來就是黑色的，現在經過父結點的所有路徑都少了一個黑結點。于是繼續(xù)調整。,137,L1L和R1R,新的根結點的顏色和老的根結點的顏色是相同的，因此也不會出現連續(xù)的紅結點的問題。調整可以結束了,138,L1R和R1L,由于新的根結點的顏色和老的根結點的顏色是相同的，因此也不會出現連續(xù)的紅結點的問題。調整可以結束了,139,L2和R2,L2的調整方法和L1R是一樣的，R2的調整方法和R1L是一樣的,140,刪除一個黑色的葉結點,被調整的結點的兄弟是黑色的（如

41、果兄弟是空結點，則認為是黑色結點） 被調整的結點的兄弟是紅色的,刪除這個結點將會使得這個位置變成了一個空結點。因此，這條路徑上少了一個黑結點。我們將這個空結點稱為被調整結點。,141,兄弟結點是紅色的,如果被調整結點的兄弟結點是紅色的，那么父結點一定是黑色的，兄弟結點的兒子也一定是黑色的。 旋轉后，紅黑樹的特性得以保持，但被調整結點的兄弟結點變成了黑色。 第2種情況轉換成了第1種情況，,142,在下列紅黑樹中刪除26，違反了紅黑樹的性質，25的右路徑少了一個黑結點，是屬于第二種情況,143,旋轉后，結果如下，被調整節(jié)點（25的右孩子）的兄弟變成了黑色而且有一個紅孩子，屬于L1R的情況。,調整后

42、，這棵樹恢復了平衡,繼續(xù)調整,144,紅黑樹,紅黑樹的定義 紅黑樹的插入 紅黑樹的刪除 紅黑樹類的實現,紅黑樹是平衡樹的一種替換方案。它比平衡樹簡單。紅黑樹在最壞情況下的操作時間是O(logN),145,紅黑樹類的實現,紅黑樹的節(jié)點類需要一個保存顏色的數據成員 插入、刪除時的調整需要用到父節(jié)點可祖父節(jié)點，所以用迭代的方式實現,146,紅黑樹類的定義,template class RedBlackTree struct RedBlackNode Type data; RedBlackNode *left; RedBlackNode *right; int colour; / 0 - Red, 1

43、 - Black RedBlackNode( const Type ,147,public: RedBlackTree( RedBlackNode *t = NULL ) root = t; RedBlackTree( ) makeEmpty( root); bool find( const Type ,148,reLink函數的實現,當子樹被旋轉后，子樹的根會發(fā)生變化。對子樹的父結點來講，必須將新的子樹根作為兒子。reLink就是完成這個功能 ReLink函數有三個參數。第一個參數是子樹原來的根，第二個參數是子樹的新根，第三個參數是一個鏈接棧類對象，保存從根結點到這棵子樹的路徑上的結點。 這

44、里的linkStack就是第三章中實現的鏈接棧類,149,template void RedBlackTree:reLink(RedBlackNode *oldp, RedBlackNode *newp, linkStack ,150,Find、makeEmpty和旋轉函數,與AVL樹完全相同,151,insert函數的實現,用非遞歸實現 插入函數只需要一個參數：被插入的節(jié)點 需要維護一個棧，保存從根節(jié)點到當前節(jié)點的路徑 可以用第三章中的棧類,152,template void RedBlackTree:insert( const Type ,153,if (t != NULL) return

45、; t = new RedBlackNode( x, NULL, NULL); parent = path.pop(); if (x data) parent-left = t; else parent-right = t; if (parent-colour = 1) return; path.push(parent); insertReBalance(t, path); ,154,insertReBalance(t, path),template void RedBlackTree:insertReBalance ( RedBlackNode *t, linkStack ,155,whil

46、e (parent-colour = 0) if (parent = root) parent-colour = 1; return; grandParent = rootOfSubTree = path.pop(); if (grandParent-data parent-data) uncle = grandParent-right; else uncle = grandParent-left; if (uncle = NULL | uncle-colour = 1) /情況一的處理 else /情況二 grandParent-colour = 0; parent-colour = 1;

47、uncle-colour = 1; if (root = grandParent) root-colour = 1; return; t = grandParent; parent = path.pop(); ,156,/情況一的處理,If (grandParent-left = parent) if (t = parent-left) /LLb parent-colour = 1; grandParent -colour = 0; LL(grandParent); else /LRb grandParent-colour = 0; t-colour = 1; LR(grandParent);

48、 else if (t = parent-right) /RRb parent-colour = 1; grandParent -colour = 0; RR(grandParent); else /RLb grandParent-colour = 0; t-colour = 1; RL(grandParent); reLink(rootOfSubTree, grandParent, path); return; ,157,Remove函數,使用迭代的方式實現刪除操作。 remove函數中也設置了一個棧path，保存從根結點到被刪結點的路徑。 刪除函數首先執(zhí)行結點刪除，然后判斷紅黑樹是否失衡。

49、如果失衡，則調用removeReBalance重新調整平衡。,158,remove函數的實現,template void RedBlackTree:remove( const Type ,159,/ 執(zhí)行刪除 if (t = root) /刪除根結點 root = (t-left ? t-left : t-right); if (root != NULL) root-colour = 1; return; parent = path.pop(); old = t; t = (t-left ? t-left : t-right); if (parent-left = old) parent-le

50、ft = t; else parent-right = t; if (old-colour = 0) delete old; return; /刪除紅葉結點 delete old; if (t != NULL) /有一個紅兒子 t-colour = 1; return; path.push(parent); removeReBalance(t, path); ,160,removeReBalance函數的實現,template void RedBlackTree:removeReBalance ( RedBlackNode *t, linkStack ,161,while (parent !=

51、 NULL) if (parent-left = t) sibling = parent-right; else sibling = parent-left; if (sibling-colour = 0) /情況二 sibling-colour = 1; parent-colour = 0; if (parent-left = t) RR(parent); else LL(parent); reLink(rootOfSubTree, parent, path) ; path.push(parent); parent = rootOfSubTree; else /兄弟是黑結點 if (sibl

52、ing-left = NULL | sibling-left-colour = 1) / end of while,162,/ 情況一的處理 if (parent-left = t) /兄弟是右孩子 if (sibling-left != NULL ,163,第8章 動態(tài)查找表,二叉查找樹 AVL樹 紅黑樹 AA樹 伸展樹 B樹和B+樹 STL中的動態(tài)查找表,164,AA樹,AA樹的定義 AA樹的插入操作 AA樹的刪除操作 AA樹類的實現,165,AA樹,定義：左孩子不能為紅色的紅黑樹 優(yōu)點： 它省去了一半的需要重構的情況； 簡化了重新平衡的過程,166,一棵AA樹,167,AA樹的水平鏈表示

53、法,將指向紅結點的鏈畫成水平的，可以看出所有葉子的高度都是相同的,168,用水平鏈表示的AA樹的特征：,水平鏈是右兒子鏈（因為只有右兒子才可能是紅色的） 不可能有左水平鏈（因為做兒子不可能為紅色） 不可能有兩條連續(xù)的水平鏈（因為不會有連續(xù)的紅色結點） 如果一個結點沒有右水平鏈的話，它的兩個兒子就在同一層,169,節(jié)點的層次,如果結點是一個葉子的話，層次為1 如果結點是紅色的，就是它父親的層次 如果結點是黑色的，比它父親的層次少1,在AA樹中，我們用節(jié)點的層次表示平衡信息,170,AA樹,AA樹的定義 AA樹的插入操作 AA樹的刪除操作 AA樹類的實現,171,AA樹的插入,如普通的紅黑樹，新節(jié)

54、點總是插入為葉子且為紅節(jié)點。但可能引起不平衡： 插入為左子樹，則出現水平左鏈。這是不允許的 插入為一個紅節(jié)點的右子樹，則出現連續(xù)的水平右鏈，也是不允許的 不管是哪一種情況，進行一次單旋轉就可以解決問題了,172,水平左鏈的解決（LL旋轉）,節(jié)點和左孩子進行一個單旋,可能出現連續(xù)的水平右鏈，需要繼續(xù)調整,173,連續(xù)的水平右鏈問題(RR),對前兩個節(jié)點進行一次旋轉,中間的結點層次增長了1，這樣又會給X原來的父親帶來了問題：出現水平左鏈或是連續(xù)的水平右鏈，但不管是什么問題，都可以通過在向根回溯的過程中反復應用LL/RR策略來解決,174,在下面的樹中插入75，出現連續(xù)水平右鏈,175,執(zhí)行RR旋轉

55、,176,在上述AA樹中插入40，出現連續(xù)水平右鏈,177,執(zhí)行RR旋轉,出現水平左鏈，執(zhí)行LL旋轉,178,出現連續(xù)水平右鏈，執(zhí)行RR旋轉,出現連續(xù)水平右鏈，執(zhí)行RR旋轉,179,AA樹,AA樹的定義 AA樹的插入操作 AA樹的刪除操作 AA樹類的實現,180,AA樹的刪除,二叉查找樹的刪除最終總能歸結到刪除葉節(jié)點或只有一個孩子的節(jié)點。 如果被刪除節(jié)點只有一個孩子，那該孩子一定是紅節(jié)點。也就是說被刪節(jié)點一定是第一層的節(jié)點 因此，AA是的刪除歸結到刪除一個第一層的節(jié)點,181,被刪節(jié)點的情況,被刪節(jié)點是紅節(jié)點：直接刪除 被刪節(jié)點有一個紅節(jié)點的兒子：將此紅節(jié)點替代被刪節(jié)點 被刪節(jié)點是黑節(jié)點：會影

56、響平衡，要調整,182,刪除5：可直接刪除 刪除3：把5調整到3的位置 刪除12：會影響平衡，節(jié)點9不平衡,183,調整方法,首先降低父結點的層次 如果父結點有一個水平右鏈，它右兒子的層次也必須降低。這時，AA樹中可能會出現水平左鏈或連續(xù)的水平右鏈。 用插入時相同的方法消除這些水平左鏈或連續(xù)的水平右鏈。,184,刪除75，將使得70出現了一條水平左鏈。 刪除25將使24出現了水平左鏈。刪除15，將使得20，24，23，25全部成為第一層的結點。于是，24到23出現了一條水平左鏈，20到24到25出現了連續(xù)的水平右鏈。,185,被刪除的結點是父結點的右孩子,最復雜的情況如下圖所示 當12被刪除后

57、，結點9的層次變成了1。于是，9到3的鏈變成了水平鏈。 對9做一次LL旋轉，又出現了9到5的水平鏈， 對9再做一次LL旋轉，此時，水平左鏈都消除了，但出現了連續(xù)的水平右鏈， 對3做一次RR旋轉，此時，這棵樹恢復了AA樹的特性。 結點5的層次提升了一層，變成了第二層的結點?？赡苁沟眠@棵子樹的父結點出現水平左鏈或連續(xù)的水平右鏈,186,被刪除的結點是父結點的左孩子,最壞的情況可能影響到6個節(jié)點。如下圖中刪除15，使得所有結點都變成了第一層的節(jié)點，23變成了30的水平左鏈，20還出現了連續(xù)的水平右鏈,187,對30執(zhí)行LL，消除30到23的水平左鏈,對30執(zhí)行LL，消除30到25的水平左鏈,188,對20執(zhí)行RR,對25執(zhí)行RR,調整結束,189,刪除黑結點總結,如果刪除的是父節(jié)點的右孩子 先對根結點執(zhí)行一次LL旋轉 如果需要的話，再對根的右孩子執(zhí)行一次LL旋轉 如果需要的話，再對根執(zhí)行一次RR旋轉。 如果刪除的是父結點的左孩子時 對根結點的右兒子執(zhí)行LL旋轉 如果需要的話，對根結點的右兒子的右兒子執(zhí)行一次LL旋轉 如果需要的話，對根結點執(zhí)行RR旋轉。 如果需要的話，對根結點的右兒子執(zhí)行RR旋轉,190,完整的調整過程,如果需要的話，對根結點執(zhí)行LL旋轉 如果需要的話，對根結點的右兒子執(zhí)行LL旋轉 如果需要的話，對根結點的右兒子的右兒子執(zhí)行LL旋轉 如果需要的話，