學(xué)年計算機方向課程大二上數(shù)算實習(xí)splay

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

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

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

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

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