數(shù)據(jù)結(jié)構(gòu) - 第三部分.ppt

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

2、結(jié)構(gòu)是散列表,5,第7章 集合與靜態(tài)查找表,集合的基本概念 查找的基本概念 無(wú)序表的查找 有序表的查找 STL中的靜態(tài)表,6,查找的基本概念,用于查找的集合稱之為查找表 查找表的分類： 靜態(tài)查找表 動(dòng)態(tài)查找表。 內(nèi)部查找 外部查找,7,靜態(tài)查找表的存儲(chǔ),靜態(tài)查找表可以用順序表存儲(chǔ)。 如C+的標(biāo)準(zhǔn)模板庫(kù)中的類模板vector，或第二章中定義的seqList，或直接存儲(chǔ)在C+的原始數(shù)組中。 查找函數(shù)應(yīng)該是一個(gè)函數(shù)模板。模板參數(shù)是數(shù)據(jù)元素的類型。,8,第7章 集合與靜態(tài)查找表,集合的基本概念 查找的基本概念 無(wú)序表的查找 有序表的查找 STL中的靜態(tài)表,9,無(wú)序表的查找,無(wú)序表：數(shù)組中的元素是無(wú)序的

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

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

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

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

7、l類型的，指出了被查找的元素在容器中是否存在。如果存在，返回true，否則，返回false。,26,應(yīng)用實(shí)例,#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,總結(jié),本章介紹了集合關(guān)系的基本概念，以及集合類型的數(shù)據(jù)結(jié)構(gòu)中的基本操作。 針對(duì)靜態(tài)的集合，介紹了查找操作的實(shí)現(xiàn)。包括順序查找、二分查找、插值查找和分塊查找。 最后還介紹了STL中的查找函數(shù)：find和binary_search。find實(shí)現(xiàn)了順序查找，binary_search實(shí)現(xiàn)了二分查找。,28,第8章 動(dòng)態(tài)查找表,二叉查找樹(shù) AVL樹(shù) 紅黑樹(shù) AA樹(shù) 伸展樹(shù) B樹(shù)和B+樹(shù) STL中的動(dòng)態(tài)查找表,既要支持快速查找，又要支持插入刪除，通常選用樹(shù)作為存儲(chǔ)的載體,29,二叉查

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

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

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

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

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

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

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

16、的。設(shè)P（n）為查找n個(gè)結(jié)點(diǎn)的二叉查找樹(shù)的平均查找時(shí)間，則,58,二叉查找樹(shù),二叉查找樹(shù)的定義 二叉查找樹(shù)的操作 二叉查找樹(shù)的性能 二叉查找樹(shù)類的實(shí)現(xiàn),59,二叉排序樹(shù)類的設(shè)計(jì),采用標(biāo)準(zhǔn)的二叉鏈表存儲(chǔ)一棵二叉查找樹(shù)需要一個(gè)指向根節(jié)點(diǎn)的數(shù)據(jù)成員 公有的成員函數(shù)：find、insert和remove 以及構(gòu)造、析構(gòu)函數(shù) 二叉查找樹(shù)的插入、刪除和查找都是通過(guò)遞歸實(shí)現(xiàn)的，而這三個(gè)公有函數(shù)的參數(shù)表中并不需要包含遞歸參數(shù)。為此，對(duì)于每個(gè)公有的成員函數(shù)都定義了一個(gè)對(duì)應(yīng)的帶有遞歸參數(shù)的私有的成員函數(shù),60,二叉排序樹(shù)類的定義,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,二叉排序樹(shù)類的設(shè)計(jì)特點(diǎn),一個(gè)內(nèi)嵌的BinaryNode類 數(shù)據(jù)成員只有一個(gè)，樹(shù)根 公有的成員函數(shù)通過(guò)調(diào)用私有的遞歸函數(shù)完成相應(yīng)的功能,63,find函數(shù)的實(shí)現(xiàn),template bool BinarySe

18、archTree:find( const Type ,64,insert函數(shù)的實(shí)現(xiàn),template void BinarySearchTree:insert( const Type ,65,insert函數(shù)設(shè)計(jì)說(shuō)明,私有的insert函數(shù)的第二個(gè)形式參數(shù)，它是一個(gè)指向結(jié)點(diǎn)的指針的非常量引用。 這個(gè)引用符號(hào)不能省略。正是這個(gè)引用，使得新插入的結(jié)點(diǎn)和它的父結(jié)點(diǎn)之間關(guān)聯(lián)了起來(lái)。,66,remove函數(shù)的實(shí)現(xiàn),template void BinarySearchTree:remove( const Type ,67,template void BinarySearchTree:remove( con

19、st Type ,68,remove函數(shù)設(shè)計(jì)說(shuō)明,同樣請(qǐng)注意私有的remove函數(shù)的參數(shù)，它的第二個(gè)參數(shù)也是指向結(jié)點(diǎn)的指針的引用。 與插入過(guò)程一樣，這個(gè)引用也不能去掉。正是這個(gè)引用使得被刪結(jié)點(diǎn)的父結(jié)點(diǎn)和被刪結(jié)點(diǎn)的兒子連接起來(lái)。,69,二叉查找樹(shù)類的使用,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章 動(dòng)態(tài)查找表,二叉查找樹(shù) AVL樹(shù) 紅黑樹(shù) AA樹(shù) 伸展樹(shù) B樹(shù)和B+樹(shù) STL中的動(dòng)態(tài)查找表,72,AVL樹(shù),AVL樹(shù)的定義 AVL樹(shù)的插入操作 AVL樹(shù)的刪除 AVL樹(shù)類的實(shí)現(xiàn),73,平衡二叉查找樹(shù),當(dāng)樹(shù)退化為鏈表時(shí)，樹(shù)的優(yōu)點(diǎn)蕩然無(wú)存。要使查找樹(shù)的性能盡可能好，就要使得樹(shù)盡可能豐滿。要構(gòu)造一個(gè)豐滿樹(shù)很困難，一種替代的方案是平衡樹(shù)。,74,二叉平衡樹(shù),二叉平衡樹(shù)就是滿足某種平衡條件的二叉查找樹(shù) 平衡條件： 容易維護(hù) 保證樹(shù)的高度是O

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

23、衡二叉樹(shù)的查找性能,定理：具有 N 個(gè)結(jié)點(diǎn)的平衡樹(shù)，高度 h 滿足：log2(N+1) = h = 1.44log2(N+1) - 0.328;,與二叉樹(shù)的高度成正比,因此，平衡二叉樹(shù)的操作都是O(logN),79,AVL樹(shù),AVL樹(shù)的定義 AVL樹(shù)的插入操作 AVL樹(shù)的刪除 AVL樹(shù)類的實(shí)現(xiàn),80,插入操作,插入過(guò)程與二叉查找樹(shù)的插入相同，只是插入后可能出現(xiàn)兩種情況： 插入后，不破壞平衡性，只是改變了樹(shù)根到插入點(diǎn)的路徑上的某些結(jié)點(diǎn)的平衡度，因此需要自底向上修改節(jié)點(diǎn)的平衡度 破壞了路徑上的某些結(jié)點(diǎn)的平衡性，需要向上調(diào)整樹(shù)的結(jié)構(gòu),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é)點(diǎn)的平衡度，需要自底向上的調(diào)整。只要有一個(gè)節(jié)點(diǎn)的平衡度不變，它上面的節(jié)點(diǎn)的平衡度也不變。調(diào)整可以結(jié)束。,插入29,0,+1,0,82,平衡樹(shù),插入2以后，變得不平衡了。如何用最簡(jiǎn)單、最有效的辦法保持平衡分類二叉樹(shù)的性質(zhì)不變？,83,調(diào)整要求： 希望不涉及到危機(jī)結(jié)點(diǎn)的父親結(jié)點(diǎn)，即以危機(jī)結(jié)點(diǎn)為根的子樹(shù)的高度應(yīng)保持不變。調(diào)整可以到此結(jié)束。 仍應(yīng)保持分類二叉樹(shù)的性質(zhì)不變,84,重新平衡,如果節(jié)點(diǎn)原來(lái)的平衡度為0，則插入后不可能失衡，重新計(jì)算平衡度，繼續(xù)往上回溯 如果節(jié)點(diǎn)原來(lái)的平衡度非0，可能成為失衡節(jié)點(diǎn) 重新計(jì)

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

26、的根結(jié)點(diǎn)作為他的左子樹(shù)，原先的左兒子作為原先根的右兒子,88,LL問(wèn)題,保持了樹(shù)的有序性 保持了原先的高度,89,在下列樹(shù)中插入4，將會(huì)使得9失去平衡。這是在9的左孩子的左子樹(shù)上插入引起失衡，是LL情況,90,旋轉(zhuǎn)后的結(jié)果,保持了樹(shù)的有序性 保持了原先的高度,91,LR和RL問(wèn)題,通過(guò)雙旋轉(zhuǎn)來(lái)解決，即兩次單旋轉(zhuǎn)。現(xiàn)對(duì)危機(jī)結(jié)點(diǎn)的兒子和孫子進(jìn)行一次單旋轉(zhuǎn)，使孫子變成兒子。然后是危機(jī)結(jié)點(diǎn)和新的兒子進(jìn)行一次單旋轉(zhuǎn)。,92,LR問(wèn)題,有一個(gè)結(jié)點(diǎn)被插入到B的右子樹(shù)的事實(shí)保證了B的右子樹(shù)不會(huì)是空的，因此我們可以假定B的右子樹(shù)為C，它有一個(gè)根和兩棵子樹(shù)（當(dāng)然可能是空的）組成,93,保持了樹(shù)的有序性 保持了原先

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

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

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

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

31、樹(shù)矮了一層，需要繼續(xù)調(diào)整,107,AVL樹(shù),AVL樹(shù)的定義 AVL樹(shù)的插入操作 AVL樹(shù)的刪除 AVL樹(shù)類的實(shí)現(xiàn),108,AVL樹(shù)類的實(shí)現(xiàn),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函數(shù)的非遞歸

32、實(shí)現(xiàn),template bool AvlTree:find( const Type ,111,私有的insert函數(shù)的實(shí)現(xiàn),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函數(shù)的實(shí)現(xiàn),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章 動(dòng)態(tài)查找表,二叉查找樹(shù) AVL樹(shù) 紅黑樹(shù) AA樹(shù) 伸展樹(shù) B樹(shù)和B+樹(shù) STL中的動(dòng)態(tài)查找表,120,紅黑樹(shù),紅黑樹(shù)的定義 紅黑樹(shù)的插入 紅黑樹(shù)的刪除 紅黑樹(shù)類的實(shí)現(xiàn),紅黑樹(shù)是平衡樹(shù)的一種替換方案。它比平衡樹(shù)效率高。紅黑樹(shù)在最壞情況下的操作時(shí)間是O(logN),121,紅黑樹(shù)的定義,每個(gè)節(jié)點(diǎn)都被標(biāo)記為紅色或是黑色的 根是黑色的 如果一

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

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

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

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

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

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

42、，這棵樹(shù)恢復(fù)了平衡,繼續(xù)調(diào)整,144,紅黑樹(shù),紅黑樹(shù)的定義 紅黑樹(shù)的插入 紅黑樹(shù)的刪除 紅黑樹(shù)類的實(shí)現(xiàn),紅黑樹(shù)是平衡樹(shù)的一種替換方案。它比平衡樹(shù)簡(jiǎn)單。紅黑樹(shù)在最壞情況下的操作時(shí)間是O(logN),145,紅黑樹(shù)類的實(shí)現(xiàn),紅黑樹(shù)的節(jié)點(diǎn)類需要一個(gè)保存顏色的數(shù)據(jù)成員 插入、刪除時(shí)的調(diào)整需要用到父節(jié)點(diǎn)可祖父節(jié)點(diǎn)，所以用迭代的方式實(shí)現(xiàn),146,紅黑樹(shù)類的定義,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函數(shù)的實(shí)現(xiàn),當(dāng)子樹(shù)被旋轉(zhuǎn)后，子樹(shù)的根會(huì)發(fā)生變化。對(duì)子樹(shù)的父結(jié)點(diǎn)來(lái)講，必須將新的子樹(shù)根作為兒子。reLink就是完成這個(gè)功能 ReLink函數(shù)有三個(gè)參數(shù)。第一個(gè)參數(shù)是子樹(shù)原來(lái)的根，第二個(gè)參數(shù)是子樹(shù)的新根，第三個(gè)參數(shù)是一個(gè)鏈接棧類對(duì)象，保存從根結(jié)點(diǎn)到這棵子樹(shù)的路徑上的結(jié)點(diǎn)。 這

44、里的linkStack就是第三章中實(shí)現(xiàn)的鏈接棧類,149,template void RedBlackTree:reLink(RedBlackNode *oldp, RedBlackNode *newp, linkStack ,150,Find、makeEmpty和旋轉(zhuǎn)函數(shù),與AVL樹(shù)完全相同,151,insert函數(shù)的實(shí)現(xiàn),用非遞歸實(shí)現(xiàn) 插入函數(shù)只需要一個(gè)參數(shù)：被插入的節(jié)點(diǎn) 需要維護(hù)一個(gè)棧，保存從根節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)的路徑 可以用第三章中的棧類,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函數(shù),使用迭代的方式實(shí)現(xiàn)刪除操作。 remove函數(shù)中也設(shè)置了一個(gè)棧path，保存從根結(jié)點(diǎn)到被刪結(jié)點(diǎn)的路徑。 刪除函數(shù)首先執(zhí)行結(jié)點(diǎn)刪除，然后判斷紅黑樹(shù)是否失衡。

49、如果失衡，則調(diào)用removeReBalance重新調(diào)整平衡。,158,remove函數(shù)的實(shí)現(xiàn),template void RedBlackTree:remove( const Type ,159,/ 執(zhí)行刪除 if (t = root) /刪除根結(jié)點(diǎn) 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; /刪除紅葉結(jié)點(diǎn) delete old; if (t != NULL) /有一個(gè)紅兒子 t-colour = 1; return; path.push(parent); removeReBalance(t, path); ,160,removeReBalance函數(shù)的實(shí)現(xiàn),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 /兄弟是黑結(jié)點(diǎn) if (sibl

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

53、法,將指向紅結(jié)點(diǎn)的鏈畫(huà)成水平的，可以看出所有葉子的高度都是相同的,168,用水平鏈表示的AA樹(shù)的特征：,水平鏈?zhǔn)怯覂鹤渔湥ㄒ驗(yàn)橹挥杏覂鹤硬趴赡苁羌t色的） 不可能有左水平鏈（因?yàn)樽鰞鹤硬豢赡転榧t色） 不可能有兩條連續(xù)的水平鏈（因?yàn)椴粫?huì)有連續(xù)的紅色結(jié)點(diǎn)） 如果一個(gè)結(jié)點(diǎn)沒(méi)有右水平鏈的話，它的兩個(gè)兒子就在同一層,169,節(jié)點(diǎn)的層次,如果結(jié)點(diǎn)是一個(gè)葉子的話，層次為1 如果結(jié)點(diǎn)是紅色的，就是它父親的層次 如果結(jié)點(diǎn)是黑色的，比它父親的層次少1,在AA樹(shù)中，我們用節(jié)點(diǎn)的層次表示平衡信息,170,AA樹(shù),AA樹(shù)的定義 AA樹(shù)的插入操作 AA樹(shù)的刪除操作 AA樹(shù)類的實(shí)現(xiàn),171,AA樹(shù)的插入,如普通的紅黑樹(shù)，新節(jié)

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

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

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

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