離散數(shù)學及其應用第9章-樹的基本理論與算法(下)課件

1、2022/7/19計算機應用技術研究所11離散數(shù)學Discrete Mathematics 汪榮貴 教授合肥工業(yè)大學計算機與信息學院2022/7/19計算機應用技術研究所2第9章 樹的基本理論與算法（下）2022/7/19 本章學習內(nèi)容 無向樹的基本知識1 根樹的基本知識2 樹模型的應用4 特殊根樹與算法32022/7/19計算機應用技術研究所4特殊根樹與算法2022/7/19計算機應用技術研究所5 特殊根樹與算法 平衡樹模型 紅黑樹模型 B樹模型2022/7/19 平衡二叉樹【定義】平衡二叉樹是一種特殊的二叉樹，要求樹中任何結點的兩棵子樹高度差不能超過1， 如果插入或者刪除一個結點使得高度之

2、差大于 1，就要進行結點之間的旋轉操作，將二叉樹重新維持在一個平衡狀態(tài)。2022/7/19 平衡因子【定義】樹模型中某結點左子樹的高度減去該結點右子樹的高度，所形成的差值稱為該結點的平衡因子，即Balance Fector(BF)=左子樹的高度-右子樹的高度。平衡二叉樹的平衡因子為-1， 0 或 1。 設計平衡二叉樹操作算法的關鍵在于如何使得平衡二叉樹保持平衡2022/7/19 不平衡情況以下四種情況下的插入操作可能會導致原有平衡二叉樹發(fā)生不平衡:（1） LL： 若某一節(jié)點的平衡因子為 1，當在其左子樹的左子樹上插入一個新結點時會導致該結點的平衡因子由 1 變?yōu)?2。（2） RR： 若某一節(jié)點

3、的平衡因子為-1，當在其右子樹的右子樹上插入一個新結點時會導致該結點的平衡因子由-1 變?yōu)?2。（3） LR： 若某一節(jié)點的平衡因子為 1，當在其左子樹的右子樹上插入一個新結點時會導致該結點的平衡因子由 1 變?yōu)?2。（4） RL： 若某一節(jié)點的平衡因子為-1，當在其右子樹的左子樹上插入一個新結點時會導致該結點的平衡因子由-1 變?yōu)?2。平衡二叉樹有四種基本的旋轉方式，分別為：左旋轉，右旋轉，先左后右旋轉，先右后左旋轉。針對上述四種情況可能導致的不平衡，可通過旋轉的方式使得平衡二叉樹恢復平衡。2022/7/19 LL型調(diào)整2022/7/19 RR型調(diào)整2022/7/19 LR型調(diào)整2022/7

4、/19 LR型調(diào)整2022/7/19 RL型調(diào)整2022/7/19 RL型調(diào)整2022/7/19在上述四種旋轉基礎上，就可對平衡二叉樹進行插入和刪除操作，具體如下：（1）插入操作：插入完成后需要從插入的結點開始維護一個到根結點的路徑，每經(jīng)過一個結點都要維持樹的平衡，需要根據(jù)高度差的特點采取不同的旋轉策略進行調(diào)整，使整棵樹恢復成為平衡樹。（2）刪除操作：首先定位要刪除的結點， 刪除完成后，要從刪除結點的父親開始向上維護樹的平衡一直到根結點， 然后采取不同的旋轉策略調(diào)整，使整棵樹恢復成為平衡樹。 插入刪除操作2022/7/19計算機應用技術研究所16特殊根樹與算法 平衡樹模型 紅黑樹模型 B樹模型

5、2022/7/19 紅黑樹【定義】紅黑樹是一種自平衡二叉查找樹。與其他二叉查找樹的不同，紅黑樹在每個結點上增加一個存儲位來表示結點的顏色，可以是紅色或黑色，通過自動控制紅色和黑色這兩種顏色的結點分布，以保證樹的高度達到近似平衡，從而能夠得到比較高的算法效率。一棵紅黑樹需要滿足以下五條性質：（1）每個結點是紅色或者是黑色；（2）根結點是黑色；（3）每個葉結點，即空結點（NIL）是黑色的；（4）如果一個結點是紅色，那么它的兩個子結點都是黑色；（5）對每個結點，從該結點到其所有后代葉結點的所有路徑上包含相同數(shù)目的黑結點。2022/7/19 插入操作插入操作主要為以下3個基本步驟：步驟1：查找要插入的

6、位置；步驟2：將新結點的顏色域賦值為紅色；步驟3：自下而上重新調(diào)整該樹為紅黑樹；2022/7/19 具體實現(xiàn)步驟3的具體實現(xiàn)方法：假設要插入的結點為N，其父親結點為P，P的兄弟結點為U?？紤]以下兩類情況：（1）如果P是黑色的，那么整棵樹已經(jīng)是紅黑樹不需要再進行調(diào)整。（2）如果P是紅色的，那么插入N后，將與第4條性質不符，這時需要進行旋轉調(diào)整。具體的調(diào)整方法又可以分為以下3種情況：2022/7/19 具體實現(xiàn)1）如圖所示，N的叔叔U是紅色（圖中使用陰影表示紅色），將結點P和結點U的定義為黑色并定義結點G為紅色。此時，插入結點N的父親結點P為黑色。 因為通過父結點P或結點U的任何路徑都必定通過結點

7、G，而在這些路徑上黑色結點的數(shù)目沒有改變。但是，結點G的父結點也可能是紅色的，因此需要以結點G向上遞歸調(diào)整結點顏色。2022/7/19 具體實現(xiàn)2）如圖所示，N的叔叔U是黑色的，且N是右孩子，此時對結點P進行一次左旋轉調(diào)換， 然后按情形3）的方法處理。2022/7/19 具體實現(xiàn)3)如圖所示，N的叔叔U是黑色的，且N是左孩子，此時需對結點G做一次右旋轉調(diào)換，使得在變換后的樹中結點P是新結點N和結點G的父結點，然后調(diào)換之前的結點P和結點G的顏色，使之滿足第4和第5條性質。2022/7/19 刪除操作紅黑樹刪除操作分為以下三個基本步驟：(1) 查找要刪除結點的位置；(2) 用其后繼替換該結點；(3

8、) 若替換結點為黑色，則需重新調(diào)整樹模型使其重新成為紅黑樹。2022/7/19 具體實現(xiàn)步驟3的具體實現(xiàn)分四種情況分別處理：設被刪除的結點為N，其父結點為P，其兄弟結點為S。由于結點N是黑色的，則結點P和S都有可能是黑色或紅色。2022/7/19 具體實現(xiàn)（1）結點S是紅色的。此時結點P肯定是黑色。對結點N的父結點P做左旋轉，然后把紅色兄弟結點轉換成結點N的祖父。接著轉換結點N的父親和祖父的顏色。 接下去按第二、第三或第四種情況來處理，如圖所示。2022/7/19 具體實現(xiàn)（2） 結點S及其的孩子全是黑色的。這種情況下，結點P可能是黑色也可能是紅色的。此時，首先把結點S賦值為紅色。然后要調(diào)整以

9、P作為N遞歸調(diào)整樹，如圖所示。2022/7/19 具體實現(xiàn)（3）S是黑色的，S的左孩子是紅色，右孩子是黑色。這種情況下，對結點S做右旋轉，這樣S的左孩子就成為S的父親和N的新兄弟。這樣就將問題轉化到第四種情況。此時N和它的父結點都不受這個變換的影響，如圖所示。2022/7/19 具體實現(xiàn)（4）S是黑色的，S的右孩子是紅色。這種情況下，對N的父結點做左旋轉，這樣S成為N的父結點和S右兒子父結點。接著交換N的父結點和S的顏色，并使S的右兒子為黑色。此時，N增加了一個黑色祖先: 要么N的父結點變成黑色，要么它是黑色而S增加了一個黑色祖父。所以，通過N的路徑都增加了一個黑色結點，如圖所示。2022/7

10、/19計算機應用技術研究所29 特殊根樹與算法 平衡樹模型 紅黑樹模型 B樹模型2022/7/19 B樹【定義】B樹中所有結點的孩子結點數(shù)目的最大值稱為B樹的階，通常用m表示，出于查找效率考慮，要求m3。 一棵m階B樹一般具有以下性質：（1）每個結點最多有m個分支，最少分支數(shù)要看是否為根結點，若為根結點，則根結點的分支數(shù)至少為2，否則非根結點至少有m/2個分支。（2）結點的分支數(shù)等于關鍵字數(shù)加1，即n(knm)個分支的結點含有n1個關鍵字，它們按遞增順序排列。 其中，k = 2(根結點)或m/2 (非根結點)。2022/7/19 B樹2022/7/19 例例如，圖表示為一棵5階B樹（即樹中任一

11、結點至多含有 4個關鍵字，5棵子樹），下面將以該B樹為例詳細介紹B樹的查找、插入、刪除操作。2022/7/19 查找操作根據(jù)結點的孩子數(shù)做分支界定。比較要查找的值與當前值的大小，若比當前值小則在其左子樹，否則在其右子樹，遞歸查找，直到找到相等的結點為止，并返回該結點的位置。如果直到葉子結點仍然沒有找到則返回Null。2022/7/19 插入操作插入操作后所構成的新樹必須滿足B樹性質。對于高度為h的m階B樹，新結點一般插在第B層。分兩種情況討論具體的插入算法：（1）若該結點中關鍵字個數(shù)小于m-1，則直接插入即可。（2）若該結點中關鍵字個數(shù)等于m-1，以中間關鍵字為界將結點一分為二，產(chǎn)生一個新結點

12、，并把中間關鍵字插入到父結點中；重復上述步驟，直到完成插入過程。最壞情況是一直分裂到根結點，建立一個新的根結點，此時整個B樹增加一層。2022/7/19 舉例說明【例】插入以下字符到一棵空的5階B樹中（非根結點關鍵字數(shù)小于2個就合并，大于4個就分裂）：A C G N H E K Q M F W L T Z D P R X Y S。2022/7/19 舉例說明2022/7/19 舉例說明2022/7/19 刪除操作第一種情況，若刪除前該結點中關鍵字個數(shù)nm/2，那么直接刪除該結點。2022/7/19 刪除操作2022/7/19 刪除操作2022/7/19 刪除操作2022/7/19 刪除操作20

13、22/7/19 刪除操作2022/7/19 本章學習內(nèi)容 無向樹的基本知識1 根樹的基本知識2 特殊根樹與算法3 樹模型的應用42022/7/19計算機應用技術研究所45樹模型的應用2022/7/19計算機應用技術研究所46 樹模型的應用 找假幣問題 輪流摸牌問題 關鍵道路問題2022/7/19 決策樹2022/7/19 決策樹 決策樹是圖論中最常見的模型之一，它把做出判決的邏輯關系用樹的形式表現(xiàn)出來，最后的結果都集中在葉子上，條理清晰，一目了然。 2022/7/19 例【例】女孩子被父母安排相親，為了確定見與不見，他可能會考慮諸如：年齡、長相、收入等問題。圖所示的決策樹就是她可能的一種決策過

14、程。2022/7/19 找假幣問題1【例】現(xiàn)有5枚外觀相同的硬幣，其中有1枚是假的，假幣與真幣在重量上有差異，但不知孰重孰輕。問如何使用一架無砝碼天平找出假幣并判別其與真幣的重量關系？【分析】用天平來稱A和B兩枚硬幣，只有AB三種可能的情形，因此可構造3元決策樹來解決。如圖所示。2022/7/19 找假幣問題12022/7/19找假幣問題2 【例】已知有12個金幣，其中有一個是假的，且不知道假幣和金幣的重量關系，現(xiàn)在要求用一個天平，只稱3次，把假幣找出來。2022/7/19找假幣問題2【解】把球分成三份：2022/7/19計算機應用技術研究所54樹模型的應用 找假幣問題 輪流摸牌問題 關鍵道路

15、問題2022/7/19 博弈樹作為一種經(jīng)典的博奕類游戲，下面我們介紹輪流摸牌問題2022/7/19 輪流摸牌問題【例】圖所示為初始的三堆撲克牌數(shù)量。第一堆和第二堆的撲克牌數(shù)量都為3張，第三堆撲克牌的數(shù)量為1張，組成了初始狀態(tài)(3，3，1)。2022/7/19 輪流摸牌問題其在給定初始狀態(tài)（3，3，1）擴展下的所有對弈策略博弈樹如圖所示2022/7/19 輪流摸牌問題一般結論：若某個初始局面為先手必勝，那么每走一步都必須使后首落在必敗點。因此對于每一個局面，要么為勝局面，要么為負局面。用非0表示表示勝局面，0表示負局面。對于某一個局面，若為非0局面，它的任務就是要尋找某一種取法，使局面變?yōu)?局面

16、。那么其對手無論怎么取，都會使局面又變?yōu)?局面。2022/7/19 輪流摸牌問題輪流摸撲克牌游戲為典型的尼姆博弈問題。尼姆博弈的關鍵在于游戲開始時游戲處于何種狀態(tài)（平衡或非平衡）和先手是否能夠按照取子游戲的獲勝策略來進行游戲。2022/7/19計算機應用技術研究所60 樹模型的應用 找假幣問題 輪流摸牌問題 關鍵道路問題2022/7/19 關鍵道路一項工程往往由許多作業(yè)構成，其中某些作業(yè)可以同時進行，而某些作業(yè)卻必須按照一定先后順序執(zhí)行。例如，在建筑工程中，室內(nèi)裝修卻必須在砌墻立屋之后才能動工等。這樣就存在問題：為了使工期最短、成本最低，我們應該采取什么方法安排各個作業(yè)實施？先引入一些概念來對關鍵道路相關問題進行建模2022/7/19 PERT圖2022/7/19 PERT圖 對于PERT圖，我們主要關心其關鍵路徑，以及每個作業(yè)的最早啟動時間和最晚啟動時間。2