国产一区二区精品-国产一区二区精品久-国产一区二区精品久久-国产一区二区精品久久91-免费毛片播放-免费毛片基地

千鋒教育-做有情懷、有良心、有品質(zhì)的職業(yè)教育機(jī)構(gòu)

手機(jī)站
千鋒教育

千鋒學(xué)習(xí)站 | 隨時(shí)隨地免費(fèi)學(xué)

千鋒教育

掃一掃進(jìn)入千鋒手機(jī)站

領(lǐng)取全套視頻
千鋒教育

關(guān)注千鋒學(xué)習(xí)站小程序
隨時(shí)隨地免費(fèi)學(xué)習(xí)課程

當(dāng)前位置:首頁(yè)  >  技術(shù)干貨  > 樹(shù)堆(Treap)和紅黑樹(shù)(RB-Tree)各有哪些優(yōu)劣?

樹(shù)堆(Treap)和紅黑樹(shù)(RB-Tree)各有哪些優(yōu)劣?

來(lái)源:千鋒教育
發(fā)布人:xqq
時(shí)間: 2023-10-11 04:06:02 1696968362

一、樹(shù)堆(Treap)和紅黑樹(shù)(RB-Tree)的優(yōu)劣

Treap

優(yōu)點(diǎn): 插入刪除簡(jiǎn)單直觀,速度也不錯(cuò),很好地平衡了編碼復(fù)雜度和時(shí)間效率。

缺點(diǎn):由于優(yōu)先級(jí)(優(yōu)先級(jí)是個(gè)堆)是隨機(jī)生成的,所以只能保證它的插入和刪除操作時(shí)間復(fù)雜度大概是log(n),你不能保證它的一個(gè)操作一定能在很準(zhǔn)確的時(shí)限內(nèi)完成。

所以Treap常用于算法競(jìng)賽需要手動(dòng)寫(xiě)B(tài)ST的時(shí)候,尤其是擴(kuò)展而來(lái)的Rank Tree (名次樹(shù),查詢第k人的元素,set做不了)。

RB-Tree

優(yōu)點(diǎn): 保證平衡并且有平衡限制條件,操作有準(zhǔn)確時(shí)限,插入刪除操作比AVL Tree快.

缺點(diǎn): 太復(fù)雜,插入有5種情況,刪除有6種情況,代碼量大,編寫(xiě)容易出錯(cuò)。

所以RB-Tree用于大部分語(yǔ)言的set的實(shí)現(xiàn),實(shí)時(shí)系統(tǒng)等。

延伸閱讀:

二、樹(shù)堆實(shí)現(xiàn)平衡樹(shù)的特點(diǎn)

普通的BST具有很強(qiáng)的不確定性,如果數(shù)據(jù)特殊,建樹(shù)的時(shí)候可能直接變成一條鏈。不僅如此,插入刪除的時(shí)候也很麻煩。因?yàn)槿绻迦牖蛘邉h除,整個(gè)樹(shù)原來(lái)的結(jié)構(gòu)就會(huì)被打亂,這會(huì)為遍歷和查找?guī)?lái)災(zāi)難性的后果。

所以我們推出了平衡樹(shù)。就是通過(guò)將樹(shù)旋轉(zhuǎn)來(lái)動(dòng)態(tài)維護(hù)這個(gè)樹(shù)形態(tài)是平衡的,這樣查找的復(fù)雜度就是O(log)級(jí)別的,是一種穩(wěn)定的復(fù)雜度。

樹(shù)堆是一種平衡樹(shù),它通過(guò)為鍵值(也就是我們需要維護(hù)成BST的)賦予優(yōu)先級(jí),使之也滿足堆結(jié)構(gòu)來(lái)進(jìn)行旋轉(zhuǎn),成為一棵平衡樹(shù)。

但是我們需要注意一點(diǎn):樹(shù)堆的優(yōu)先級(jí)是隨機(jī)賦予的。也就是說(shuō),這個(gè)數(shù)據(jù)結(jié)構(gòu)其實(shí)是一個(gè)隨機(jī)化的數(shù)據(jù)結(jié)構(gòu)。這不是樹(shù)堆的缺點(diǎn),因?yàn)橹挥须S機(jī)化賦予優(yōu)先級(jí),才有可能保證樹(shù)堆的復(fù)雜度是O(log)的級(jí)別。那么,上述性質(zhì)也說(shuō)明了,樹(shù)堆并不是一個(gè)規(guī)則形態(tài)的二叉樹(shù),更不是堆需要滿足的完全二叉樹(shù)。甚至它也不符合平衡樹(shù)的定義:每個(gè)節(jié)點(diǎn)左右子樹(shù)高度相差≤1,所以我們說(shuō)樹(shù)堆是近似實(shí)現(xiàn)平衡。但是通過(guò)形態(tài)定義二叉樹(shù)的方式并不絕對(duì)。我們換一種方式來(lái)對(duì)平衡樹(shù)進(jìn)行定義:能夠保證時(shí)間復(fù)雜度的BST,就是平衡樹(shù)。

聲明:本站稿件版權(quán)均屬千鋒教育所有,未經(jīng)許可不得擅自轉(zhuǎn)載。
10年以上業(yè)內(nèi)強(qiáng)師集結(jié),手把手帶你蛻變精英
請(qǐng)您保持通訊暢通,專屬學(xué)習(xí)老師24小時(shí)內(nèi)將與您1V1溝通
免費(fèi)領(lǐng)取
今日已有369人領(lǐng)取成功
劉同學(xué) 138****2860 剛剛成功領(lǐng)取
王同學(xué) 131****2015 剛剛成功領(lǐng)取
張同學(xué) 133****4652 剛剛成功領(lǐng)取
李同學(xué) 135****8607 剛剛成功領(lǐng)取
楊同學(xué) 132****5667 剛剛成功領(lǐng)取
岳同學(xué) 134****6652 剛剛成功領(lǐng)取
梁同學(xué) 157****2950 剛剛成功領(lǐng)取
劉同學(xué) 189****1015 剛剛成功領(lǐng)取
張同學(xué) 155****4678 剛剛成功領(lǐng)取
鄒同學(xué) 139****2907 剛剛成功領(lǐng)取
董同學(xué) 138****2867 剛剛成功領(lǐng)取
周同學(xué) 136****3602 剛剛成功領(lǐng)取
相關(guān)推薦HOT
功能安全開(kāi)發(fā)與ASPICE和CMMI之間有什么樣的聯(lián)系?

一、功能安全開(kāi)發(fā)與ASPICE和CMMI之間的聯(lián)系CMMI是產(chǎn)品和系統(tǒng)開(kāi)發(fā)的通用模型,ASPICE是針對(duì)車這個(gè)垂直領(lǐng)域,(軟件)產(chǎn)品和系統(tǒng)開(kāi)發(fā)的標(biāo)準(zhǔn)。ASPI...詳情>>

2023-10-11 05:59:32
在C語(yǔ)言下數(shù)組array與鏈表linklist各自的優(yōu)點(diǎn)和缺陷是什么?

一、在C語(yǔ)言下數(shù)組array與鏈表linklist各自的優(yōu)點(diǎn)和缺陷數(shù)組可以通過(guò)下標(biāo)訪問(wèn),隨機(jī)訪問(wèn)效率高,鏈表需要通過(guò)指針遍歷,訪問(wèn)效率低。數(shù)組在分配...詳情>>

2023-10-11 05:43:25
oa系統(tǒng)一般有哪些模塊?

一、組織架構(gòu)模塊組織架構(gòu)模塊記錄了企業(yè)的組織結(jié)構(gòu)、人員信息、部門(mén)職責(zé)、工作流程等基本信息,實(shí)現(xiàn)了組織架構(gòu)的可視化和管理。該模塊主要包括...詳情>>

2023-10-11 05:33:42
為什么python沒(méi)有大頂堆?

一、python沒(méi)有大頂堆的原因Python沒(méi)有內(nèi)置大頂堆,是因?yàn)樵趯?shí)際使用中,大頂堆并不是那么常用。相比之下,小頂堆和普通的堆操作更具有廣泛的應(yīng)...詳情>>

2023-10-11 05:30:39
什么是crm管理?

一、crm管理概念 CRM管理也叫客戶管理,亦即客戶關(guān)系管理(Customer Relationship Management)的簡(jiǎn)稱。CRM管理的主要含義就是通過(guò)對(duì)客戶詳細(xì)資...詳情>>

2023-10-11 05:28:00
快速通道