動(dòng)態(tài)搜索結(jié)構(gòu)

1、馬強(qiáng)2015年4月4日大綱二叉搜索樹平衡二叉樹伸展樹 2 二叉搜索樹二叉搜索樹定義每個(gè)節(jié)點(diǎn)有一個(gè)唯一的key值，且所有結(jié)點(diǎn)互不相同左子樹所有key值小于根的key值右子樹所有key值大于根的key值左右子樹都是二叉搜索樹12225030011020099105230216二叉搜索樹又稱為二叉搜索樹又稱為“二叉排序樹二叉排序樹”、“二叉查找樹二叉查找樹”、“二叉檢索樹二叉檢索樹”3二叉搜索樹的基本操作查找插入刪除4二叉搜索樹查找操作 與根結(jié)點(diǎn)的key值比較相等則 查找成功小于則查找左子樹大于則查找右子樹13 85231837如何查找元素如何查找元素 5 ?555查找成功！查找成功！5二叉搜索樹插

2、入操作 首先執(zhí)行查找算法，找出將要插入結(jié)點(diǎn)的父親結(jié)點(diǎn)首先執(zhí)行查找算法，找出將要插入結(jié)點(diǎn)的父親結(jié)點(diǎn) 判斷被插結(jié)點(diǎn)是其父親結(jié)點(diǎn)的左或右孩子。將被插判斷被插結(jié)點(diǎn)是其父親結(jié)點(diǎn)的左或右孩子。將被插結(jié)點(diǎn)作為葉子結(jié)點(diǎn)插入。結(jié)點(diǎn)作為葉子結(jié)點(diǎn)插入。 若二叉樹為空。作為根結(jié)點(diǎn)。若二叉樹為空。作為根結(jié)點(diǎn)。6二叉搜索樹插入操作利用插入操作可以構(gòu)造一棵二叉搜索樹利用插入操作可以構(gòu)造一棵二叉搜索樹首先給出結(jié)點(diǎn)序列首先給出結(jié)點(diǎn)序列:13、8、23、5、18、37 13537 18 8238 2355181837377二叉搜索樹刪除操作情況1 葉子結(jié)點(diǎn)：直接刪除，更改它的父親結(jié)點(diǎn)的相應(yīng)指針域?yàn)榭?。葉子結(jié)點(diǎn)：直接刪除，更改它的

3、父親結(jié)點(diǎn)的相應(yīng)指針域?yàn)榭?。如：刪除值為如：刪除值為 15、70 的結(jié)點(diǎn)。的結(jié)點(diǎn)。156070302050603020508二叉搜索樹刪除操作情況212225030011020099105230400450500若被刪結(jié)點(diǎn)只有一個(gè)孩子結(jié)點(diǎn)。則用它的子樹代替它。若被刪結(jié)點(diǎn)只有一個(gè)孩子結(jié)點(diǎn)。則用它的子樹代替它。如刪除結(jié)點(diǎn)的關(guān)鍵值為如刪除結(jié)點(diǎn)的關(guān)鍵值為 99 結(jié)點(diǎn)。結(jié)點(diǎn)。被刪結(jié)點(diǎn)被刪結(jié)點(diǎn)1222503002002304004505001101059二叉搜索樹刪除操作情況3被刪結(jié)點(diǎn)左右孩子都不為空選取“替身”取代被刪結(jié)點(diǎn)。然后刪除替身結(jié)點(diǎn)如何選擇替身？左子樹中最大的結(jié)點(diǎn)或 右子樹中最小的結(jié)點(diǎn)101222

4、5030011020099105330400450500被刪結(jié)點(diǎn)被刪結(jié)點(diǎn)替替身身11025030010520099330400450500將替身的數(shù)據(jù)復(fù)制到被刪結(jié)點(diǎn)的數(shù)據(jù)。將替身的數(shù)據(jù)復(fù)制到被刪結(jié)點(diǎn)的數(shù)據(jù)。刪除值為刪除值為122的結(jié)點(diǎn)。的結(jié)點(diǎn)。110二叉搜索樹刪除操作情況311 12225030011020099105330400450500被刪結(jié)點(diǎn)被刪結(jié)點(diǎn)替替身身將替身的數(shù)據(jù)場(chǎng)復(fù)制到被刪結(jié)點(diǎn)的數(shù)據(jù)場(chǎng)。將替身的數(shù)據(jù)場(chǎng)復(fù)制到被刪結(jié)點(diǎn)的數(shù)據(jù)場(chǎng)。刪除值為刪除值為122的結(jié)點(diǎn)。的結(jié)點(diǎn)。 20025030011099105400450500330200二叉搜索樹刪除操作情況312二叉搜索樹的性能查找：從

5、根節(jié)點(diǎn)向下掃描到葉子結(jié)點(diǎn)。O(h)插入和刪除：先查找、再操作。所以也是O(h)與樹的高度密切相關(guān)20025030011099105400450500330主要用于內(nèi)存中目錄的編制要求能夠快速的查找、插入刪除13二查搜索樹的高度 輸入順序?yàn)檩斎腠樞驗(yàn)?4、5、6、7、8 4 5 6 7 8 7 5 8 4 6 輸入順序?yàn)檩斎腠樞驗(yàn)?7、5、4、6、8 最壞情況為n,最好情況為logn如何使樹的高度保持為logn？14大綱二叉搜索樹平衡二叉樹伸展樹 15平衡二叉搜索樹1962年由俄羅斯數(shù)學(xué)家G.M.Adelson-Valskii和E.M.Landis提出，所以簡(jiǎn)稱為AVL樹。定義：空樹或者是具有以

6、下性質(zhì)的二叉搜索樹左右子樹的高度差的絕對(duì)值不超過(guò) 1且左右子樹都是AVL樹平衡因子：右子樹的高度減左子樹的高度。簡(jiǎn)稱：bf16平衡二叉樹舉例11726391518161410000000-1是AVL樹163269718261411不是AVL樹-30431100-117平衡化旋轉(zhuǎn)目的：通過(guò)旋轉(zhuǎn)使每個(gè)結(jié)點(diǎn)的 |bf|2四種旋轉(zhuǎn)：左單旋轉(zhuǎn)右單旋轉(zhuǎn)先左后右雙旋轉(zhuǎn)先右后左雙旋轉(zhuǎn)3060ABC10 123060ABC0018平衡化旋轉(zhuǎn)目的：通過(guò)旋轉(zhuǎn)使每個(gè)結(jié)點(diǎn)的 |bf|2四種旋轉(zhuǎn)：左單旋轉(zhuǎn)右單旋轉(zhuǎn)先左后右雙旋轉(zhuǎn)先右后左雙旋轉(zhuǎn)3060ABC00-1-23060ABC0-119目的：通過(guò)旋轉(zhuǎn)使每個(gè)結(jié)點(diǎn)的 |b

7、f|2四種旋轉(zhuǎn)：左單旋轉(zhuǎn)右單旋轉(zhuǎn)先左后右雙旋轉(zhuǎn)先右后左雙旋轉(zhuǎn)平衡化旋轉(zhuǎn)-100903060ABCDhh-11-2-1906030ABCDh0-2-20906030ABCDh0120目的：通過(guò)旋轉(zhuǎn)使每個(gè)結(jié)點(diǎn)的 |bf|2四種旋轉(zhuǎn)：左單旋轉(zhuǎn)右單旋轉(zhuǎn)先左后右雙旋轉(zhuǎn)先右后左雙旋轉(zhuǎn)平衡化旋轉(zhuǎn)100903060ABCDhh-112-1906030ACBDh0220906030ABCDh-1021平衡化旋轉(zhuǎn)總結(jié)3060ABC12-13060ABC-2903060ABCDhh-11-2-1903060ABCDhh-112-1左單旋轉(zhuǎn)右單旋轉(zhuǎn)先左后右先右后左22AVL樹的操作和性能操作查找、插入、刪除二叉搜索樹

8、的方法+平衡旋轉(zhuǎn)時(shí)間復(fù)雜度O(logn)23大綱二叉搜索樹平衡二叉樹伸展樹 24伸展樹“八二原則”80%的人只會(huì)用到20%的數(shù)據(jù)正在訪問(wèn)的結(jié)點(diǎn)將以很高的概率再次被訪問(wèn)將經(jīng)常訪問(wèn)的結(jié)點(diǎn)放在靠近根的位置，以便再訪問(wèn)。伸展樹：對(duì)二叉搜索樹的改進(jìn)：每訪問(wèn)完一個(gè)結(jié)點(diǎn)就把該結(jié)點(diǎn)移動(dòng)到樹的根部。25伸展樹的旋轉(zhuǎn)方法情況一：被訪問(wèn)結(jié)點(diǎn)S的父結(jié)點(diǎn)是根結(jié)點(diǎn)采用單旋轉(zhuǎn)方式PSABCPSABC26伸展樹的旋轉(zhuǎn)方法情況二：同構(gòu)形狀采用一字形旋轉(zhuǎn)方式PSABCGDPSABCGDPSABCGD27伸展樹的旋轉(zhuǎn)方法情況三：異構(gòu)形狀采用之字形旋轉(zhuǎn)方式PSABCGDSPABCGDPSABCGD28綜合例子803010905020407060803010905020407060803010905020407060803010905020407060一字旋轉(zhuǎn)之字旋轉(zhuǎn)單