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

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

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