數(shù)據(jù)結(jié)構(gòu)與算法-紅黑樹

平衡二叉查找樹

? ? 平衡二叉樹中任意一個節(jié)點的左右子樹的高度相差不能大于1

? ??????完全二叉樹活烙、滿二叉樹都是平衡二叉樹,但非完全二叉樹也有可能是平衡二叉樹

????平衡二叉查找樹滿足上面平衡二叉樹的定義,還滿足二叉查找樹的特點

? ??平衡二叉查找樹為了解決普通二叉查找樹頻繁插入弟晚、刪除等動態(tài)更新導(dǎo)致時間復(fù)雜度退化? ??

? ??平衡二叉查找樹中“平衡”:?

? ??????“平衡”可以等價為性能不退化

? ? ? ? 讓整棵樹左右子樹高度比較“平衡”朋截,相應(yīng)的插入、刪除位他、查找等操作的效率高一些

? ??如設(shè)計一個平衡二叉查找樹氛濒,只要樹高度不比logn大很多,盡管不符合定義仍然可以算合格

平衡二叉樹 VS 非平衡二叉樹

紅黑樹(Red-Black Tree)

? ? 是一種不嚴(yán)格的平衡二叉查找樹鹅髓,屬于最常用平衡二叉查找樹

? ? 滿足紅黑樹前提條件

? ? ? ? 所有節(jié)點只有黑色和紅色

? ??????根節(jié)點是黑色

? ??????每個葉子節(jié)點都是黑色的空節(jié)點(NIL) (主要為了簡化代碼實現(xiàn)而設(shè)置)

? ? ? ? ? ? 添加黑色的空葉子節(jié)點舞竿,可以在具體實現(xiàn)的時候公用一個空節(jié)點,不會太浪費空間

? ??????任何相鄰的節(jié)點都不能同時為紅色

????????每個節(jié)點從該節(jié)點到達(dá)其可達(dá)葉子節(jié)點的所有路徑窿冯,都包含相同數(shù)目的黑色節(jié)點

? ??紅黑樹是“近似平衡”

? ??????“平衡”可以等價為性能不退化骗奖,而“近似平衡”等價為性能不會退化的太嚴(yán)重

? ??????二叉查找樹操作的性能都跟樹的高度成正比,極其平衡的二叉樹高度大約為logn

? ? 特點

? ??????只要按照這些固定的調(diào)整規(guī)則來操作,就能將一個非平衡的紅黑樹調(diào)整成平衡

? ??????左旋(rotate left):?圍繞某個節(jié)點的左旋

????????右旋(rotate right): 圍繞某個節(jié)點的右旋

左旋 VS 右旋

? ??????紅黑樹的插入执桌、刪除操作會破壞紅黑樹的平衡鄙皇,如何調(diào)整平衡

? ? ? ? 名詞介紹

????????????叔叔節(jié)點: 父節(jié)點的兄弟節(jié)點,

????????????祖父節(jié)點:?父節(jié)點的父節(jié)點

? ??????????關(guān)注節(jié)點:?正在處理的節(jié)點

? ? ? ? ? ? 前驅(qū)節(jié)點: 中序遍歷的序列中鼻吮,當(dāng)前節(jié)點上一個節(jié)點

? ? ? ? ? ? 后繼節(jié)點: 中序遍歷的序列中育苟,當(dāng)前節(jié)點下一個節(jié)點

? ??????插入操作的平衡調(diào)整

????????????紅黑樹定義: 插入的節(jié)點必須是紅色,而且樹中新插入的節(jié)點都放在葉子節(jié)點上

????????????具體情況如下:

????????????????如果插入節(jié)點的父節(jié)點是黑色椎木,那不需要任何調(diào)整违柏,它仍然滿足紅黑樹的定義

????????????????如果插入的節(jié)點是根節(jié)點,那直接改變它的顏色香椎,把它變成黑色就可以了

? ? ? ? ? ? ? ? 其他情況都會違背紅黑樹的定義漱竖,需要進(jìn)行兩種基礎(chǔ)的操作: 左右旋轉(zhuǎn)和改變顏色

? ? ? ? ? ? 實現(xiàn)過程

????????????????紅黑樹的平衡調(diào)整過程是一個迭代的過程,

????????????????關(guān)注節(jié)點隨著不停地迭代處理畜伐,而不斷發(fā)生變化馍惹。最開始的關(guān)注節(jié)點是新插入的節(jié)點

? ??????????????新節(jié)點插入后,如果紅黑樹的平衡被打破玛界,一般會有下面三種情況 & 如何實現(xiàn)再平衡

? ? ? ? ? ? ? ? Case 1.如果關(guān)注節(jié)點是a万矾,它的叔叔節(jié)點d是紅色,依次執(zhí)行

? ??????????????????將關(guān)注節(jié)點a的父節(jié)點b慎框、叔叔節(jié)點d的顏色都設(shè)置成黑色

? ??????????????????將關(guān)注節(jié)點a的祖父節(jié)點c的顏色設(shè)置成紅色

? ??????????????????關(guān)注節(jié)點變成a的祖父節(jié)點c

? ??????????????????跳到CASE 2 或 CASE 3

Case 1

? ? ? ? ? ? ? ? Case?2.如果關(guān)注節(jié)點是a良狈,叔叔節(jié)點d是黑色,關(guān)注節(jié)點a是其父節(jié)點b的右子節(jié)點

? ??????????????????關(guān)注節(jié)點變成節(jié)點a的父節(jié)點b笨枯;

? ??????????????????圍繞新的關(guān)注節(jié)點b左旋薪丁;

? ??????????????????跳到 CASE 3

Case 2

? ? ? ? ? ? ? ? Case?3.如果關(guān)注節(jié)點是a,叔叔節(jié)點d是黑色馅精,關(guān)注節(jié)點a是其父節(jié)點b的左子節(jié)點

? ??????????????????圍繞關(guān)注節(jié)點a的祖父節(jié)點c右旋严嗜;

? ??????????????????將關(guān)注節(jié)點a的父節(jié)點b、兄弟節(jié)點c的顏色互換洲敢。

Case 3

? ? ? ? 刪除操作的平衡調(diào)整

? ? ? ? ? ? 實現(xiàn)過程

? ? ? ? ? ? ? ? 1.針對刪除節(jié)點初步調(diào)整

? ??????????????????紅黑樹定義中“只包含紅色節(jié)點和黑色節(jié)點”漫玄,經(jīng)過初步調(diào)整之后,

????????????????????為了保證這一條要求压彭,有些節(jié)點會被標(biāo)記成兩種顏色睦优,“紅-黑”或者“黑-黑”。

????????????????????如果一個節(jié)點被標(biāo)記為“黑-黑”哮塞,那在計算黑色節(jié)點個數(shù)的時候,要算成兩個黑色節(jié)

? ??????????????????如果一個節(jié)點既可以是紅色凳谦,也可以是黑色忆畅,在下圖用一半紅色一半黑色來表示

????????????????????如果一個節(jié)點是“紅-黑”或者“黑-黑”,我會用左上?的一個小黑點來表示額外的黑色

? ? ? ? ? ? ? ? ? ? Case 1:如果要刪除的節(jié)點是a,它只有一個子節(jié)點b

????????????????????????刪除節(jié)點a家凯,并且把節(jié)點b替換到節(jié)點a的位置

? ??????????????????????節(jié)點a只能是黑色缓醋,節(jié)點b也只能是紅色,不符合紅黑樹定義绊诲,把節(jié)點b改為黑色

Case 1

????????????????Case 2:如果要刪除的節(jié)點a有兩個非空子節(jié)點送粱,且后繼節(jié)點是節(jié)點a的右子節(jié)點c

? ??????????????????如果節(jié)點a后繼節(jié)點是右子節(jié)點c,把節(jié)點a刪除且將節(jié)點c替換到節(jié)點a的位置

? ??????????????????然后把節(jié)點c的顏色設(shè)置為跟節(jié)點a相同的顏色

? ??????????????????如果節(jié)點c是黑色掂之,給節(jié)點c右子節(jié)點d多加一個黑色抗俄,則節(jié)點d變成“紅-黑”或“黑-黑”

????????????????????這時關(guān)注節(jié)點變成了節(jié)點d,第二步的調(diào)整操作就會針對關(guān)注節(jié)點d來做

Case 2

? ? ? ? ? ? ? ? ? ? Case 3:如果要刪除是節(jié)點a有兩個非空子節(jié)點世舰,且節(jié)點a后繼節(jié)點不是右子節(jié)點

? ??????????????????????找到后繼節(jié)點d动雹,并將它刪除,刪除后繼節(jié)點d的過程參照CASE 1

? ??????????????????????將節(jié)點a替換成后繼節(jié)點d

? ??????????????????????把節(jié)點d的顏色設(shè)置為跟節(jié)點a相同的顏色

? ??????????????????????如果節(jié)點d是黑色跟压,給節(jié)點d右子節(jié)c多加一個黑色胰蝠,則節(jié)點c就成“紅-黑”或“黑-黑”

? ??????????????????????這時關(guān)注節(jié)點變成節(jié)點c,第二步的調(diào)整操作就會針對關(guān)注節(jié)點c來做

Case 3

????????????????2.針對關(guān)注節(jié)點進(jìn)行二次調(diào)整

? ??????????????????經(jīng)過初步調(diào)整之后震蒋,關(guān)注節(jié)點變成“紅-黑”或“黑-黑”節(jié)點

? ??????????????????二次調(diào)整是為了讓紅黑樹中不存在相鄰的紅色節(jié)點

? ??????????????????針對這個關(guān)注節(jié)點茸塞,我們再分四種情況來進(jìn)行二次調(diào)整

? ? ? ? ? ? ? ? ? ? Case 1:?如果關(guān)注節(jié)點是a,它的兄弟節(jié)點c是紅色的

? ??????????????????????圍繞關(guān)注節(jié)點a的父節(jié)點b左旋

? ??????????????????????關(guān)注節(jié)點a的父節(jié)點b和祖父節(jié)點c交換顏色

? ??????????????????????關(guān)注節(jié)點不變

? ??????????????????????繼續(xù)從四種情況中選擇適合的規(guī)則來調(diào)整

Case 1

? ? ? ? ? ? ? ? ? ? Case 2:?如果關(guān)注節(jié)點是a查剖,兄弟節(jié)點c是黑色钾虐,且節(jié)點c左右子節(jié)點d、e都是黑色

? ??????????????????????將關(guān)注節(jié)點a的兄弟節(jié)點c的顏色變成紅色

? ??????????????????????從關(guān)注節(jié)點a中去掉一個黑色梗搅,這個時候節(jié)點a就是單純的紅色或者黑色

? ??????????????????????給關(guān)注節(jié)點a的父節(jié)點b添加一個黑色禾唁,這時節(jié)點b就變成了“紅-黑”或者“黑黑”

? ??????????????????????關(guān)注節(jié)點從a變成其父節(jié)點b

? ??????????????????????繼續(xù)從四種情況中選擇符合的規(guī)則來調(diào)整

Case 2

????????????????????Case 3:?如果關(guān)注節(jié)點是a,兄弟節(jié)點c是黑色无切,c左子節(jié)點d紅色荡短,c右子節(jié)點e黑色

????????????????????????圍繞關(guān)注節(jié)點a的兄弟節(jié)點c右旋

????????????????????????節(jié)點c和節(jié)點d交換顏色

????????????????????????關(guān)注節(jié)點不變跳轉(zhuǎn)到Case 4,繼續(xù)調(diào)整

????????????????????Case 4:?如果關(guān)注節(jié)點a的兄弟節(jié)點c是黑色的哆键,并且c的右子節(jié)點是紅色的

? ??????????????????????圍繞關(guān)注節(jié)點a的父節(jié)點b左旋

????????????????????????將關(guān)注節(jié)點a的兄弟節(jié)點c的顏色掘托,跟關(guān)注節(jié)點a的父節(jié)點b設(shè)置成相同的顏色;

????????????????????????將關(guān)注節(jié)點a的父節(jié)點b的顏色設(shè)置為黑色籍嘹;

????????????????????????從關(guān)注節(jié)點a中去掉一個黑色闪盔,節(jié)點a就變成了單純的紅色或者黑色;

????????????????????????將關(guān)注節(jié)點a的叔叔節(jié)點e設(shè)置為黑色辱士;

????????????????????????調(diào)整結(jié)束泪掀。

Case 4

? ? 總結(jié)操作過程

? ??????第一點,把紅黑樹的平衡調(diào)整的過程比作魔方復(fù)原颂碘,不要過于深究這個算法的正確性

? ??????????只要按照固定的操作步驟异赫,保持插入、刪除的過程,不破壞平衡樹的定義即可

? ??????第二點塔拳,找準(zhǔn)關(guān)注節(jié)點鼠证,不要搞丟、搞錯關(guān)注節(jié)點

? ??????????每種操作規(guī)則靠抑,都是基于關(guān)注節(jié)點來做的

? ??????????在迭代的調(diào)整過程中量九,關(guān)注節(jié)點在不停地改變

? ??????第三點,插入操作的平衡調(diào)整比較簡單颂碧,但是刪除操作就比較復(fù)雜

? ??????????針對刪除操作荠列,我們有兩次調(diào)整,

????????????第一次針對要刪除的節(jié)點做初步調(diào)整稚伍,讓調(diào)整后的紅黑樹繼續(xù)滿足第四條定義

????????????????“每個節(jié)點到可達(dá)葉子節(jié)點的路徑都包含相同個數(shù)的黑色節(jié)點”

????????????????但是不滿足第三條定義弯予,有可能會存在兩個紅色節(jié)點相鄰的情況

????????????第二次調(diào)整就是解決讓紅黑樹不存在相鄰的紅色節(jié)點的問題

????幾種平衡二叉查找樹對比

? ? ? ? Treap(樹堆)

? ??????????Treap是二叉搜索樹和堆合并構(gòu)成的數(shù)據(jù)結(jié)構(gòu),每個節(jié)點數(shù)據(jù)域包含2個值

? ??????????????key值: 滿足左子樹<根節(jié)點<右子樹 (滿足二叉搜索樹特性)

? ? ? ? ? ? ????weight值:小于等于(或大于等于)左右子節(jié)點 (滿足堆特性)

? ? ? ? ? ? 利用weight值作為隨機(jī)因子來調(diào)整二叉樹形狀个曙,所以在大部分情況下更平衡锈嫩,性能更高

? ? ? ? ? ? 但無法避免極端情況下時間復(fù)雜度的退化,不適用對于操作時間非常敏感場景

? ??????Splay Tree(伸展樹)

? ??????????是一種能夠自我平衡的二叉查找樹

? ??????????每次查找后對樹進(jìn)行調(diào)整垦搬,把被查找的條目搬移到離根節(jié)點近一些的地方

? ??????????它會沿著從某個節(jié)點到根節(jié)點之間的路徑呼寸,通過一系列的旋轉(zhuǎn)把這個節(jié)點搬移到根節(jié)點

? ? ? ? ? ? 良好的的性能,同時存儲所需的內(nèi)存少

????????????但無法避免極端情況下時間復(fù)雜度的退化(特別在多線程環(huán)境)? ? ? ? ? ??

? ??????AVL樹

????????????一種高度平衡的二叉樹猴贰,查找的效率非常高;?

????????????但是AVL樹為了維持高度的平衡对雪,每次插入、刪除等操作都要調(diào)整米绕,就比較復(fù)雜瑟捣、耗時;?

? ? ? ? ? ? 對于有頻繁的插入、刪除操作的數(shù)據(jù)集合栅干,使用AVL樹的代價就有點高

????????紅黑樹

? ??????????紅黑樹的插入迈套、刪除、查找等操作性能都比較穩(wěn)定

? ? ? ? ? ? 因近似平衡碱鳞,在維護(hù)平衡的成本上桑李,要比AVL樹要低

? ? ? ? 綜合對比

? ? ? ? ? ? 為了支撐這種工業(yè)級的應(yīng)用,我們更傾向于這種性能穩(wěn)定的平衡二叉查找樹

最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 序言:七十年代末窿给,一起剝皮案震驚了整個濱河市贵白,隨后出現(xiàn)的幾起案子,更是在濱河造成了極大的恐慌崩泡,老刑警劉巖禁荒,帶你破解...
    沈念sama閱讀 222,729評論 6 517
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件,死亡現(xiàn)場離奇詭異角撞,居然都是意外死亡呛伴,警方通過查閱死者的電腦和手機(jī)寥掐,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 95,226評論 3 399
  • 文/潘曉璐 我一進(jìn)店門,熙熙樓的掌柜王于貴愁眉苦臉地迎上來磷蜀,“玉大人,你說我怎么就攤上這事百炬『致。” “怎么了?”我有些...
    開封第一講書人閱讀 169,461評論 0 362
  • 文/不壞的土叔 我叫張陵剖踊,是天一觀的道長庶弃。 經(jīng)常有香客問我,道長德澈,這世上最難降的妖魔是什么歇攻? 我笑而不...
    開封第一講書人閱讀 60,135評論 1 300
  • 正文 為了忘掉前任,我火速辦了婚禮梆造,結(jié)果婚禮上缴守,老公的妹妹穿的比我還像新娘。我一直安慰自己镇辉,他們只是感情好屡穗,可當(dāng)我...
    茶點故事閱讀 69,130評論 6 398
  • 文/花漫 我一把揭開白布。 她就那樣靜靜地躺著忽肛,像睡著了一般村砂。 火紅的嫁衣襯著肌膚如雪。 梳的紋絲不亂的頭發(fā)上屹逛,一...
    開封第一講書人閱讀 52,736評論 1 312
  • 那天础废,我揣著相機(jī)與錄音,去河邊找鬼罕模。 笑死评腺,一個胖子當(dāng)著我的面吹牛,可吹牛的內(nèi)容都是我干的手销。 我是一名探鬼主播歇僧,決...
    沈念sama閱讀 41,179評論 3 422
  • 文/蒼蘭香墨 我猛地睜開眼,長吁一口氣:“原來是場噩夢啊……” “哼锋拖!你這毒婦竟也來了诈悍?” 一聲冷哼從身側(cè)響起,我...
    開封第一講書人閱讀 40,124評論 0 277
  • 序言:老撾萬榮一對情侶失蹤兽埃,失蹤者是張志新(化名)和其女友劉穎侥钳,沒想到半個月后,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體柄错,經(jīng)...
    沈念sama閱讀 46,657評論 1 320
  • 正文 獨居荒郊野嶺守林人離奇死亡舷夺,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點故事閱讀 38,723評論 3 342
  • 正文 我和宋清朗相戀三年苦酱,在試婚紗的時候發(fā)現(xiàn)自己被綠了。 大學(xué)時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片给猾。...
    茶點故事閱讀 40,872評論 1 353
  • 序言:一個原本活蹦亂跳的男人離奇死亡疫萤,死狀恐怖,靈堂內(nèi)的尸體忽然破棺而出敢伸,到底是詐尸還是另有隱情扯饶,我是刑警寧澤,帶...
    沈念sama閱讀 36,533評論 5 351
  • 正文 年R本政府宣布池颈,位于F島的核電站尾序,受9級特大地震影響,放射性物質(zhì)發(fā)生泄漏躯砰。R本人自食惡果不足惜每币,卻給世界環(huán)境...
    茶點故事閱讀 42,213評論 3 336
  • 文/蒙蒙 一、第九天 我趴在偏房一處隱蔽的房頂上張望琢歇。 院中可真熱鬧兰怠,春花似錦、人聲如沸李茫。這莊子的主人今日做“春日...
    開封第一講書人閱讀 32,700評論 0 25
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽涌矢。三九已至掖举,卻和暖如春,著一層夾襖步出監(jiān)牢的瞬間娜庇,已是汗流浹背塔次。 一陣腳步聲響...
    開封第一講書人閱讀 33,819評論 1 274
  • 我被黑心中介騙來泰國打工, 沒想到剛下飛機(jī)就差點兒被人妖公主榨干…… 1. 我叫王不留名秀,地道東北人励负。 一個月前我還...
    沈念sama閱讀 49,304評論 3 379
  • 正文 我出身青樓,卻偏偏與公主長得像匕得,于是被迫代替她去往敵國和親继榆。 傳聞我的和親對象是個殘疾皇子,可洞房花燭夜當(dāng)晚...
    茶點故事閱讀 45,876評論 2 361