學(xué)年計(jì)算機(jī)方向課程大二上數(shù)算實(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)整位置漢字輸入法的詞表伸展樹不是一個(gè)新數(shù)據(jù)結(jié)構(gòu)，而只是改進(jìn) BST性能的一組規(guī)則保證的總代價(jià)不高，達(dá)到最令人滿意的性能不能保證最終樹高平衡2數(shù)據(jù)結(jié)構(gòu)與算法第十二章高級數(shù)據(jù)結(jié)構(gòu)展開(splaying)一次結(jié)點(diǎn) (例如結(jié)點(diǎn) x)，完成一次稱為展開的過程入、檢索時(shí)，把結(jié)點(diǎn) x 移到 BST 的根結(jié)點(diǎn)x刪除結(jié)點(diǎn) x 時(shí)，把結(jié)點(diǎn) x 的父結(jié)點(diǎn)移到根結(jié)點(diǎn)像在 AVL 樹中一樣，結(jié)點(diǎn)x的一次展開包括一組旋轉(zhuǎn)(roion)調(diào)整結(jié)點(diǎn) x、父結(jié)點(diǎn)、祖父結(jié)點(diǎn)的位置把

2、 x 移到樹結(jié)構(gòu)中的更3數(shù)據(jù)結(jié)構(gòu)與算法第十二章高級數(shù)據(jù)結(jié)構(gòu)單旋轉(zhuǎn) (single roion)x 是根結(jié)點(diǎn)的直接子結(jié)點(diǎn)時(shí)把結(jié)點(diǎn) x 與它的父結(jié)點(diǎn)交換位置保持 BST 特性xyCABx、y 為結(jié)點(diǎn)，不是值大小，有大小順序A、B、C 代表4數(shù)據(jù)結(jié)構(gòu)與算法第十二章高級數(shù)據(jù)結(jié)構(gòu)雙旋轉(zhuǎn)(double roion)雙旋轉(zhuǎn)涉及到結(jié)點(diǎn) x結(jié)點(diǎn) x 的父結(jié)點(diǎn) (稱為 y)結(jié)點(diǎn) x 的祖父結(jié)點(diǎn) (稱為 z)把結(jié)點(diǎn) 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é)點(diǎn)x是y的結(jié)點(diǎn)y是z的結(jié)點(diǎn)結(jié)點(diǎn)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é)點(diǎn)x是y的右子結(jié)點(diǎn)結(jié)點(diǎn)y是z的結(jié)點(diǎn)第十二章高級數(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é)點(diǎn)移動(dòng)結(jié)構(gòu)的高

4、度減1趨向于使樹結(jié)構(gòu)更加平衡一字形一般不會(huì)降低樹結(jié)構(gòu)的高度只是把新的向根結(jié)點(diǎn)移動(dòng)12 數(shù)據(jù)結(jié)構(gòu)與算法第十二章高級數(shù)據(jù)結(jié)構(gòu)伸展樹的調(diào)整過程一系列雙旋轉(zhuǎn)直到結(jié)點(diǎn) x 到達(dá)根結(jié)點(diǎn)或者根結(jié)點(diǎn)的子結(jié)點(diǎn)如果結(jié)點(diǎn)x到達(dá)根結(jié)點(diǎn)的子結(jié)點(diǎn)進(jìn)行一次單旋轉(zhuǎn)使結(jié)點(diǎn) x 成為根結(jié)點(diǎn)這個(gè)過程趨向于使樹結(jié)構(gòu)重新平衡使最頻繁的結(jié)點(diǎn)靠近樹結(jié)構(gòu)的根層從而減少代價(jià)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é)點(diǎn)被的頻率相關(guān)根據(jù)、刪除、檢索而動(dòng)態(tài)地調(diào)整樹的結(jié)構(gòu)與頻率無關(guān)AVL只與、刪除的順序有關(guān)19 數(shù)據(jù)結(jié)構(gòu)與算法伸展樹的效率n 個(gè)結(jié)點(diǎn)的伸展樹進(jìn)行一組m次操作mn時(shí)，總代價(jià)是、刪除、查找操作)，當(dāng)(O(mlogn)伸展樹不能保證每一個(gè)單個(gè)操作是有效率的即每次操作的平均代價(jià)為O(logn)不要求掌握證明方法20 數(shù)據(jù)結(jié)