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

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

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

3、的平衡因子為-1，當(dāng)在其右子樹的右子樹上插入一個(gè)新結(jié)點(diǎn)時(shí)會(huì)導(dǎo)致該結(jié)點(diǎn)的平衡因子由-1 變?yōu)?2。（3） LR： 若某一節(jié)點(diǎn)的平衡因子為 1，當(dāng)在其左子樹的右子樹上插入一個(gè)新結(jié)點(diǎn)時(shí)會(huì)導(dǎo)致該結(jié)點(diǎn)的平衡因子由 1 變?yōu)?2。（4） RL： 若某一節(jié)點(diǎn)的平衡因子為-1，當(dāng)在其右子樹的左子樹上插入一個(gè)新結(jié)點(diǎn)時(shí)會(huì)導(dǎo)致該結(jié)點(diǎn)的平衡因子由-1 變?yōu)?2。平衡二叉樹有四種基本的旋轉(zhuǎn)方式，分別為：左旋轉(zhuǎn)，右旋轉(zhuǎn)，先左后右旋轉(zhuǎn)，先右后左旋轉(zhuǎn)。針對(duì)上述四種情況可能導(dǎo)致的不平衡，可通過(guò)旋轉(zhuǎn)的方式使得平衡二叉樹恢復(fù)平衡。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在上述四種旋轉(zhuǎn)基礎(chǔ)上，就可對(duì)平衡二叉樹進(jìn)行插入和刪除操作，具體如下：（1）插入操作：插入完成后需要從插入的結(jié)點(diǎn)開始維護(hù)一個(gè)到根結(jié)點(diǎn)的路徑，每經(jīng)過(guò)一個(gè)結(jié)點(diǎn)都要維持樹的平衡，需要根據(jù)高度差的特點(diǎn)采取不同的旋轉(zhuǎn)策略進(jìn)行調(diào)整，使整棵樹恢復(fù)成為平衡樹。（2）刪除操作：首先定位要?jiǎng)h除的結(jié)點(diǎn)， 刪除完成后，要從刪除結(jié)點(diǎn)的父親開始向上維護(hù)樹的平衡一直到根結(jié)點(diǎn)， 然后采取不同的旋轉(zhuǎn)策略調(diào)整，使整棵樹恢復(fù)成為平衡樹。 插入刪除操作2022/7/19計(jì)算機(jī)應(yīng)用技術(shù)研究所16特殊根樹與算法 平衡樹模型 紅黑樹模型 B樹模型

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

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

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

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

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

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

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

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

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

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

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

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