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

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

手機站
千鋒教育

千鋒學習站 | 隨時隨地免費學

千鋒教育

掃一掃進入千鋒手機站

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

關(guān)注千鋒學習站小程序
隨時隨地免費學習課程

當前位置:首頁  >  技術(shù)干貨  > 紅黑樹與普通的平衡二叉樹除了顏色到底有什么區(qū)別?

紅黑樹與普通的平衡二叉樹除了顏色到底有什么區(qū)別?

來源:千鋒教育
發(fā)布人:xqq
時間: 2023-10-11 03:56:58 1696967818

一、紅黑樹與普通的平衡二叉樹的區(qū)別

1、平衡二叉樹通過保持任一節(jié)點左、右子樹高度差的絕對值不超過1來維持二叉樹的平衡;而紅黑樹是根據(jù)查找路徑上黑色節(jié)點的個數(shù)以及紅、黑節(jié)點之間的聯(lián)系來維持二叉樹的平衡。

2、平衡二叉樹在插入或者刪除節(jié)點時為了保證左右子樹的高度差會進行旋轉(zhuǎn),這一個旋轉(zhuǎn)根據(jù)數(shù)據(jù)的不同旋轉(zhuǎn)的復雜度也會不一樣,所以在插入或者刪除平衡二叉樹的節(jié)點時,旋轉(zhuǎn)的次數(shù)不可知,這也導致在頻繁的插入、修改中造成的效率問題;紅黑樹在執(zhí)行插入修改的操作時會發(fā)生旋轉(zhuǎn)與變色(紅變黑,或者黑變紅)以確保沒有一條路徑會比其它路徑長出兩倍。

3、總體來說,在插入或者刪除節(jié)點時,紅黑樹旋轉(zhuǎn)的次數(shù)比平衡二叉樹少,因此在插入與刪除操作比較頻繁的情況下,選用紅黑樹。

什么樣的數(shù)據(jù)結(jié)構(gòu)稱為紅黑樹

紅黑樹(Red Black Tree)是一種自平衡的二叉查找樹,它與平衡二叉樹相同的地方在于都是為了維護查找樹的平衡而構(gòu)建的數(shù)據(jù)結(jié)構(gòu),它的主要特征是在二叉查找樹的每個節(jié)點上添加了一個屬性表示顏色,顏色有兩種,紅與黑。

性質(zhì):

每個節(jié)點是紅色或者黑色;

根節(jié)點是黑色;

所有葉子節(jié)點都是黑色(葉子是NIL節(jié)點,也稱為外節(jié)點);

每個紅色節(jié)點的子節(jié)點都是黑色(從每個葉子節(jié)點到根節(jié)點的所有路徑上不能有兩個連續(xù)的紅色節(jié)點);

從紅黑樹的任一節(jié)點到其每個葉子節(jié)點的所有路徑都包含相同數(shù)目的黑色節(jié)點(包含黑色節(jié)點的數(shù)目稱為該節(jié)點的黑高度)。

延伸閱讀:

二、什么是平衡二叉樹

平衡二叉樹(Balanced Binary Tree)的定義是這樣的——空樹,或者任一節(jié)點左、右子樹高度差的絕對值不超過1,稱為平衡二叉樹。

比如,我們將1,2,3,4,5,6,7,8這幾個節(jié)點以5,3,1,4,2,7,6,8的順序插入構(gòu)造查找二叉樹,這棵樹就是一個平衡二叉樹,它的根節(jié)點高度為3,平均查找長度為(1*1+ 2*2 + 4*3 + 1*4)/8 = 2.625,,并且它的任一節(jié)點左、右子樹高度差的絕對值不超過1。而如果按照6,4,3,5,2,1,7,8的順序插入構(gòu)造查找二叉樹,這棵樹也不能稱為平衡二叉樹,因為它的根節(jié)點的左子樹高度為4,而右子樹的高度為2,相差大于1;而對于4這一個節(jié)點,它的左子樹高度為3,右子樹的高度為1,相差也大于1。而這棵樹的平均查找長度為(1*1 + 2*2 + 3*3 + 4*1 + 5*1)/ 8 = 2.875(這里數(shù)據(jù)量較小,看不出與平衡二叉樹的明顯差別)。

聲明:本站稿件版權(quán)均屬千鋒教育所有,未經(jīng)許可不得擅自轉(zhuǎn)載。
10年以上業(yè)內(nèi)強師集結(jié),手把手帶你蛻變精英
請您保持通訊暢通,專屬學習老師24小時內(nèi)將與您1V1溝通
免費領(lǐng)取
今日已有369人領(lǐng)取成功
劉同學 138****2860 剛剛成功領(lǐng)取
王同學 131****2015 剛剛成功領(lǐng)取
張同學 133****4652 剛剛成功領(lǐng)取
李同學 135****8607 剛剛成功領(lǐng)取
楊同學 132****5667 剛剛成功領(lǐng)取
岳同學 134****6652 剛剛成功領(lǐng)取
梁同學 157****2950 剛剛成功領(lǐng)取
劉同學 189****1015 剛剛成功領(lǐng)取
張同學 155****4678 剛剛成功領(lǐng)取
鄒同學 139****2907 剛剛成功領(lǐng)取
董同學 138****2867 剛剛成功領(lǐng)取
周同學 136****3602 剛剛成功領(lǐng)取
相關(guān)推薦HOT
在C語言下數(shù)組array與鏈表linklist各自的優(yōu)點和缺陷是什么?

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

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

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

2023-10-11 05:33:42
為什么python沒有大頂堆?

一、python沒有大頂堆的原因Python沒有內(nèi)置大頂堆,是因為在實際使用中,大頂堆并不是那么常用。相比之下,小頂堆和普通的堆操作更具有廣泛的應...詳情>>

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

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

2023-10-11 05:28:00
單調(diào)棧什么時候從后向前遍歷,什么時候從前向后遍歷?

一、單調(diào)棧什么時候從后向前遍歷,什么時候從前向后遍歷如果是求右邊的名列前茅個最大,那么就是從右向左遍歷,構(gòu)建單調(diào)遞增棧。如果是求右邊的...詳情>>

2023-10-11 05:23:50