數(shù)據(jù)結(jié)構(gòu) 課件 7-樹堆

數(shù)據(jù)結(jié)構(gòu)計算機領(lǐng)域本科教育教學(xué)改革試點工作計劃（“101計劃”）研究成果10112.7樹堆第12章

高級查找12.7.1樹堆的定義12.7.2樹堆的旋轉(zhuǎn)12.7.3樹堆的插入12.7.4樹堆的刪除12.7.5樹堆小結(jié)12.7.6樹堆作業(yè)

12.7.1樹堆的定義12.7.1樹堆的定義數(shù)據(jù)結(jié)構(gòu)樹堆=二叉查找樹+堆樹堆：給二叉查找樹的每個關(guān)鍵字額外增加了一個隨機優(yōu)先級，讓關(guān)鍵字滿足二叉查找樹的結(jié)構(gòu)，讓優(yōu)先級滿足二叉堆的性質(zhì)。這樣從關(guān)鍵字角度是一顆二叉查找樹，從優(yōu)先級角度是一個二叉堆，從而成為一棵平衡查找樹。(a,b)表示該結(jié)點的a是關(guān)鍵字，b是優(yōu)先級12.7.1樹堆的定義12.7.1樹堆的定義數(shù)據(jù)結(jié)構(gòu)樹堆并不是一個規(guī)則形態(tài)的二叉查找樹，更不是二叉堆這樣的完全二叉樹，也不符合AVL樹或者紅黑樹這些平衡樹的要求，是一顆近似平衡的二叉查找樹。如果生成樹堆的時候的優(yōu)先級的隨機性出現(xiàn)某種順序特征，可能使得生成的樹堆的高度比較高，形態(tài)接近單分支二叉樹。12.7.2樹堆的旋轉(zhuǎn)12.7.2樹堆的旋轉(zhuǎn)數(shù)據(jù)結(jié)構(gòu)如果進行二叉查找樹的插入或者刪除操作后，使得插入結(jié)點所在子樹的根的優(yōu)先級比插入結(jié)點的優(yōu)先級低，則需要旋轉(zhuǎn)，使得子樹根的優(yōu)先級比孩子優(yōu)先級更高，其中子樹在根的左側(cè)，需要右旋；子樹在根的右側(cè)，需要左旋。樹堆的旋轉(zhuǎn)12.7.2樹堆的旋轉(zhuǎn)12.7.2樹堆的旋轉(zhuǎn)數(shù)據(jù)結(jié)構(gòu)樹堆三層調(diào)整(1):zig-zig型旋轉(zhuǎn)zig-zig型12.7.2樹堆的旋轉(zhuǎn)12.7.2樹堆的旋轉(zhuǎn)數(shù)據(jù)結(jié)構(gòu)樹堆三層調(diào)整(2):zig-zag型旋轉(zhuǎn)zig-zag型12.7.2樹堆的旋轉(zhuǎn)12.7.2樹堆的旋轉(zhuǎn)數(shù)據(jù)結(jié)構(gòu)樹堆的旋轉(zhuǎn)讓查找的結(jié)點上升到根，使得下次再次查找這個結(jié)點可以一步到位，搜索效率非常高。但是，也注意到，如下圖訪問結(jié)點19，從左圖通過旋轉(zhuǎn)將19調(diào)整到根，如右圖所示。有的結(jié)點比如結(jié)點3和結(jié)點5，到根距離由3變成4，訪問距離反而增加。但僅有少數(shù)位置距離根較近的結(jié)點會增加最多2層深度，而搜索路徑上大多數(shù)結(jié)點會減少約一半的深度。樹堆旋轉(zhuǎn)調(diào)整小結(jié)12.7.3樹堆的插入12.7.3樹堆的插入數(shù)據(jù)結(jié)構(gòu)12.7.3樹堆的插入12.7.3樹堆的插入數(shù)據(jù)結(jié)構(gòu)例子：有8個關(guān)鍵字為12,6,7,14,1,9,31,8的數(shù)據(jù)，隨機分配優(yōu)先級為44,31,6,12,9,3,71,53(設(shè)數(shù)字越小，優(yōu)先級越高),則按照樹堆的插入結(jié)點規(guī)則，依次插入結(jié)點建立樹堆。12.7.3樹堆的插入12.7.3樹堆的插入數(shù)據(jù)結(jié)構(gòu)例子：有8個關(guān)鍵字為12,6,7,14,1,9,31,8的數(shù)據(jù)，隨機分配優(yōu)先級為44,31,6,12,9,3,71,53(設(shè)數(shù)字越小，優(yōu)先級越高),則按照樹堆的插入結(jié)點規(guī)則，依次插入結(jié)點建立樹堆。答案12.7.4樹堆的刪除12.7.4樹堆的刪除數(shù)據(jù)結(jié)構(gòu)樹堆刪除結(jié)點后從父結(jié)點到根結(jié)點回溯調(diào)整思維導(dǎo)圖12.7.4樹堆的刪除12.7.4樹堆的刪除數(shù)據(jù)結(jié)構(gòu)例：畫出下圖的樹堆中刪除8，1和9后的樹堆。12.7.4樹堆的刪除12.7.4樹堆的刪除數(shù)據(jù)結(jié)構(gòu)答案例：畫出下圖的樹堆中刪除8，1和9后的樹堆。12.7.5樹堆小結(jié)12.7.5樹堆小結(jié)數(shù)據(jù)結(jié)構(gòu)樹堆是基于堆的二叉查找樹，它既不是一個規(guī)則形態(tài)的二叉查找樹，更不是二叉堆這樣的完全二叉樹，也不符合AVL樹或者紅黑樹這些平衡樹的要求，是一棵近似平衡的二叉查找樹。樹堆的插入刪除簡單直觀，速度也不錯，但是這里的堆是隨機生成的，所以不能保證每一個操作都在一定的時限內(nèi)完成。12.7.6樹堆作業(yè)12.7.6樹堆作業(yè)數(shù)據(jù)結(jié)構(gòu)思考：樹堆保持堆性質(zhì)的隨機數(shù)如果不隨機，可能會出現(xiàn)什么情況？最壞情況如何？已知10個數(shù)據(jù)31,87,65,12,4,77,9,10,29,9