1、數據結構與算法伸展樹采用高等教育：，蛟，趙海燕 編寫，2008. 6 (“十一五”國家級規劃)第十二章高級數據結構伸展樹一種自組織數據結構數據隨檢索而調整位置漢字輸入法的詞表伸展樹不是一個新數據結構，而只是改進 BST性能的一組規則保證的總代價不高，達到最令人滿意的性能不能保證最終樹高平衡2數據結構與算法第十二章高級數據結構展開(splaying)一次結點 (例如結點 x)，完成一次稱為展開的過程入、檢索時，把結點 x 移到 BST 的根結點x刪除結點 x 時，把結點 x 的父結點移到根結點像在 AVL 樹中一樣，結點x的一次展開包括一組旋轉(roion)調整結點 x、父結點、祖父結點的位置把

2、 x 移到樹結構中的更3數據結構與算法第十二章高級數據結構單旋轉 (single roion)x 是根結點的直接子結點時把結點 x 與它的父結點交換位置保持 BST 特性xyCABx、y 為結點，不是值大小，有大小順序A、B、C 代表4數據結構與算法第十二章高級數據結構雙旋轉(double roion)雙旋轉涉及到結點 x結點 x 的父結點 (稱為 y)結點 x 的祖父結點 (稱為 z)把結點 x 在樹結構中向上移兩層一字形旋轉 (zigzig roion)也稱為同構調整 (homogeneous configuration)之字形旋轉 (zigzag roion)也稱為異構調整 (heter

3、ogeneous configuration)5數據結構與算法第十二章高級數據結構一字形旋轉圖示z結點x是y的結點y是z的結點結點DyxCAB6數據結構與算法一字形旋轉圖示yzxABCD7數據結構與算法第十二章高級數據結構之字形旋轉圖示zDyxABC8 數據結構與算法結點x是y的右子結點結點y是z的結點第十二章高級數據結構之字形旋轉圖示zDxyCBA9數據結構與算法第十二章高級數據結構之字形旋轉圖示xyzCBDA10 數據結構與算法第十二章高級數據結構之字形旋轉圖示xyzABCD11 數據結構與算法第十二章高級數據結構第十二章高級數據結構兩種旋轉的不同作用之字形旋轉把新使的向根結點移動結構的高

4、度減1趨向于使樹結構更加平衡一字形一般不會降低樹結構的高度只是把新的向根結點移動12 數據結構與算法第十二章高級數據結構伸展樹的調整過程一系列雙旋轉直到結點 x 到達根結點或者根結點的子結點如果結點x到達根結點的子結點進行一次單旋轉使結點 x 成為根結點這個過程趨向于使樹結構重新平衡使最頻繁的結點靠近樹結構的根層從而減少代價13 數據結構與算法伸展樹的調整過程h(a-b-c)一字形旋轉gIfHeAdGc(a, c)左轉(a, b)左轉BbCaDEF數據結構與算法14第十二章高級數據結構伸展樹的調整過程hgIfHa-d-e之字形調整eAdGaBbFcECD15 數據結構與算法第十二章高級數據結構

5、伸展樹的調整過程h(a-f-g)之字形旋轉gI(a, g)右轉Hf(a, f)左轉eaAdbBGFcECD16 數據結構與算法第十二章高級數據結構伸展樹的調整過程(a, h)右轉h單旋轉IafgeHAdGFBbcECD數據結構與算法17第十二章高級數據結構伸展樹的調整過程ahfgIAdeHBbGFEcCD18 數據結構與算法伸展樹與 AVL 樹的差別伸展樹與結點被的頻率相關根據、刪除、檢索而動態地調整樹的結構與頻率無關AVL只與、刪除的順序有關19 數據結構與算法伸展樹的效率n 個結點的伸展樹進行一組m次操作mn時，總代價是、刪除、查找操作)，當(O(mlogn)伸展樹不能保證每一個單個操作是有效率的即每次操作的平均代價為O(logn)不要求掌握證明方法20 數據結