




版權(quán)說(shuō)明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
1、左傾樹的特點(diǎn)及應(yīng)用,廣東省中山一中黃園河2。左傾樹的定義,左傾樹是一個(gè)可合并堆,它不僅支持優(yōu)先級(jí)隊(duì)列的三個(gè)基本操作(插入、刪除、取最小節(jié)點(diǎn)),還支持一個(gè)非常特殊的操作合并操作。左傾樹是一個(gè)堆有序的二叉樹。左傾的樹滿足了左派的屬性。左偏樹的定義左偏屬性定義左偏樹中的外部節(jié)點(diǎn)是左子樹或右子樹為空的節(jié)點(diǎn)。節(jié)點(diǎn)I的距離(dist(i)定義為從節(jié)點(diǎn)I到其后代中最近的外部節(jié)點(diǎn)的邊數(shù)。任何節(jié)點(diǎn)的左子節(jié)點(diǎn)的距離不小于右子節(jié)點(diǎn)的距離(左偏移屬性)。根據(jù)左偏屬性,節(jié)點(diǎn)的距離等于以節(jié)點(diǎn)為根的子樹的最右邊路徑的長(zhǎng)度。4,左傾樹的性質(zhì),定理:如果左傾樹有N個(gè)節(jié)點(diǎn),左傾樹的距離不應(yīng)超過對(duì)數(shù)(N 1) -1。最右邊的路徑:
2、 ACG最右邊的路徑節(jié)點(diǎn)數(shù)=3距離=2,左傾樹的最大距離為8個(gè)節(jié)點(diǎn):log(8 1) -1=2,5,左傾樹的操作,左傾樹支持以下操作:MakeNull初始化一個(gè)空的左傾樹合并兩個(gè)左傾樹插入一個(gè)新的節(jié)點(diǎn)最小值得到最小節(jié)點(diǎn)刪除最小值刪除最小節(jié)點(diǎn)刪除任何已知節(jié)點(diǎn)減少一個(gè)節(jié)點(diǎn)的鍵值,6, 左傾樹合并的操作,合并操作是遞歸的,合并T1和T2左傾樹,首先合并T1的右子樹和T2,7。 合并左傾樹,這是遞歸的,首先合并T1的右子樹和T2,8。合并左樹,這是遞歸的,交換左右子樹并更新根節(jié)點(diǎn)距離,合并后,右子樹距離可能大于左子樹距離。合并操作代碼如下:函數(shù)合并(a,b)如果a=空,則返回b如果b=空,則返回a如果
3、鍵(b) dist(左(a)然后交換(左(a),右(a)如果右(a)=空,則dist (a) 0否則dist (a) dist(右(a) 1返回一個(gè)結(jié)束函數(shù),10。以下是合并的示例:11。以下是合并的示例:12。以下是合并的示例:13。以下是合并的示例:18、NULL、14。下面是一個(gè)合并的例子。15,左傾樹操作合并,下面是一個(gè)合并示例:1,1,2,26,17,37,18,8,7,16,左傾樹操作合并,下面是一個(gè)合并示例:0,2,17、左傾樹被合并。以下是合并的示例:3、10、2、0、1、18。合并操作總是沿著兩個(gè)左傾樹的最右邊的路徑執(zhí)行。有N個(gè)節(jié)點(diǎn)的左傾樹在最右邊的路徑上最多有N(1)個(gè)節(jié)點(diǎn)。因此,合并操作的時(shí)間復(fù)雜度為:0(對(duì)數(shù)N1對(duì)數(shù)N2)=0(對(duì)數(shù)N),19,插入一個(gè)新節(jié)點(diǎn),將待插入的節(jié)點(diǎn)作為單節(jié)點(diǎn)左偏樹,合并兩個(gè)左偏樹:0(對(duì)數(shù)N),20,刪除左偏樹,刪除最小節(jié)點(diǎn),刪除根節(jié)點(diǎn)合
溫馨提示
- 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 各地專升本數(shù)學(xué)試卷
- 廣東高中新課標(biāo)數(shù)學(xué)試卷
- 甘肅六年級(jí)數(shù)學(xué)試卷
- 冮蘇省七下數(shù)學(xué)試卷
- 2025年04月佳木斯市湯原縣鄉(xiāng)鎮(zhèn)衛(wèi)生院公開招聘醫(yī)學(xué)畢業(yè)生1人筆試歷年專業(yè)考點(diǎn)(難、易錯(cuò)點(diǎn))附帶答案詳解
- 2025年浙江醫(yī)療衛(wèi)生招聘溫州醫(yī)科大學(xué)附屬第二醫(yī)院招聘心理測(cè)評(píng)室技師2人筆試歷年專業(yè)考點(diǎn)(難、易錯(cuò)點(diǎn))附帶答案詳解
- 2025至2030城市商業(yè)銀行行業(yè)發(fā)展趨勢(shì)分析與未來(lái)投資戰(zhàn)略咨詢研究報(bào)告
- 四川甘孜州遴選公務(wù)員考試真題2024
- 光谷八下數(shù)學(xué)試卷
- 分享一次數(shù)學(xué)試卷
- 《出生醫(yī)學(xué)證明》單親母親情況聲明
- PCS-915母差保護(hù)裝置介紹
- 第一套路面工程考試試題及答案
- GB∕T 22590-2021 軋鋼加熱爐用耐火澆注料
- 研發(fā)部程序文件bom管理
- 大件運(yùn)輸管理制度
- 結(jié)構(gòu)化思維PPT通用課件
- 跨境電商模擬試題 (1)
- 意外受傷賠償協(xié)議書的格式
- PE管閉水試驗(yàn)表
- 沈陽(yáng)市內(nèi)中小學(xué)教育培訓(xùn)機(jī)構(gòu)調(diào)查研究報(bào)告
評(píng)論
0/150
提交評(píng)論