有關(guān)紅黑樹

這個(gè)呢,是我很久之前就寫了一部分的,本來想把插入刪除的都給寫了,后面由于我的懶惰,一直沒有更新刪除,但這次,我還是不會更,啊哈哈哈哈

迷之分割線,第一次使用Markdown,不太6啊
下面就是正題了.
首先呢,要知道什么是紅黑樹.

在算法導(dǎo)論對R-B Tree的介紹:紅黑樹庵佣,一種二叉查找樹歉胶,但在每個(gè)結(jié)點(diǎn)上增加一個(gè)存儲位表示結(jié)點(diǎn)的顏色,可以是Red或Black巴粪。通過對任何一條從根到葉子的路徑上各個(gè)結(jié)點(diǎn)著色方式的限制通今,紅黑樹確保沒有一條路徑會比其他路徑長出倆倍,因而是接近平衡的肛根。

紅黑樹有以下幾個(gè)特點(diǎn):
  • 每個(gè)結(jié)點(diǎn)要么是紅的要么是黑的辫塌。
  • 根結(jié)點(diǎn)是黑的。
  • 每個(gè)葉結(jié)點(diǎn)(葉結(jié)點(diǎn)即指樹尾端NIL指針或NULL結(jié)點(diǎn))都是黑的派哲。
  • 如果一個(gè)結(jié)點(diǎn)是紅的臼氨,那么它的兩個(gè)兒子都是黑的。
  • 對于任意結(jié)點(diǎn)而言狮辽,其到葉結(jié)點(diǎn)樹尾端NIL指針的每條路徑都包含相同數(shù)目的黑結(jié)點(diǎn)一也。

其次是為什么要用紅黑樹而不用AVL,我個(gè)人理解就是AVL是平衡的,每插入刪除一個(gè)節(jié)點(diǎn)都會調(diào)整,而且調(diào)整的效率并不高,很可能要調(diào)很多次.而紅黑樹是近似平衡的,最多3次即可調(diào)整完畢,是比較快速的.

接下來就是紅黑樹的插入刪除了.

PS:刪除等我哪天閑下來再更吧...雖然不難,但是我懶啊

紅黑樹的每次插入刪除的調(diào)整的目的都是為了使得這棵樹滿足上面的5個(gè)特點(diǎn).所以調(diào)整思路很容易就確定出來的(這里就當(dāng)我扯淡吧,在沒看例子的時(shí)候還是挺難想到想全的,膜一下魯?shù)婪颉へ悹柎蟠?.

插入部分

插入的過程相對來說還是比較容易的.因?yàn)樘攸c(diǎn)中說從根到葉節(jié)點(diǎn)的黑節(jié)點(diǎn)數(shù)要相同.所以每次插入的要是是紅色的節(jié)點(diǎn)那就肯定不會影響紅黑樹的這幾個(gè)特點(diǎn)了,所以我們就每次插入紅色的節(jié)點(diǎn).但又有個(gè)問題,紅節(jié)點(diǎn)的孩子不能是紅色的,所以要進(jìn)行變色調(diào)整.接下來就詳細(xì)描述一下這個(gè)過程好了.

  • 1.最簡單的情況插入的位置的父節(jié)點(diǎn)是黑色的,那就直接插就好了,不用做調(diào)整.因?yàn)樗牟迦氩粫绊懠t黑樹的性質(zhì).

  • 2.插入的是根節(jié)點(diǎn),那直接把這個(gè)節(jié)點(diǎn)變成黑色就好了,因?yàn)楦?jié)點(diǎn)必須是黑色的.

  • 3.插入的節(jié)點(diǎn)的父節(jié)點(diǎn)是紅色的,這個(gè)系列是最麻煩的. 詳細(xì)說一下.

  • 3.1父節(jié)點(diǎn)是紅色的且叔叔節(jié)點(diǎn)(叔叔節(jié)點(diǎn)就是父親的兄弟節(jié)點(diǎn))是紅色的.
    因?yàn)楦赣H是紅色的,所以必須有爺爺節(jié)點(diǎn)(父親的父節(jié)點(diǎn)).且爺爺是黑色的,那么解決策略就是:將當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)和叔叔節(jié)點(diǎn)涂黑,祖父結(jié)點(diǎn)涂紅喉脖,把當(dāng)前結(jié)點(diǎn)指向祖父節(jié)點(diǎn)椰苟,從新的當(dāng)前節(jié)點(diǎn)重新開始算法.
    插個(gè)圖說明下好了
    插入前:

    Paste_Image.png

    插入后:

Paste_Image.png

廢話下,說詳細(xì)點(diǎn)好了,為什么這么做呢.原因:它的插入使得紅黑樹的性質(zhì)被破壞了,所以,我們就先維護(hù)爺爺節(jié)點(diǎn)這一塊往下的子樹,使得其滿足紅黑樹的性質(zhì),然后再往上接著維護(hù).那這么維護(hù)真的可以么,嗯,因?yàn)槿绻麑⒏赣H和叔叔都變黑了,祖父變成紅色,那么這一整顆子樹的從祖父到葉子的黑節(jié)點(diǎn)數(shù)還是和插入這貨之前的一樣,所以這方法是可以的.

  • 3.2父節(jié)點(diǎn)是紅色,叔叔節(jié)點(diǎn)是黑色.這個(gè)可以用一個(gè)圖表來總結(jié).(本人寫字丑,忍忍吧).

20161008230546547.jpg

上面呢就是總結(jié)出來的.
下面引用個(gè)JULY(原文鏈接)的圖來說明下,圖上的圓圈呢是情況的號碼.如果5出現(xiàn),必定接著使用6的方法來進(jìn)行調(diào)整.先湊合著看看,下面詳細(xì)說下

Paste_Image.png
Paste_Image.png

56是配套的,因?yàn)椴豢赡苤怀霈F(xiàn)5,出現(xiàn)5都會轉(zhuǎn)到6.簡單的說,5就是將樹調(diào)整成6的適用條件.然后6的調(diào)整原理就是:(舉個(gè)例子,用圖中左左的的情況)因?yàn)椴迦胧羌t的,父是紅的,且插入的和父親都是左子,叔叔是黑的,那祖父肯定是黑的,所以變色后右旋一次,路徑中的黑子數(shù)還是一樣的,也沒有紅節(jié)點(diǎn)孩子是紅色,保證了紅黑樹的性質(zhì),所以這個(gè)解決方案就是可行的了.
到此插入就講完了,很簡單吧. 有空再更刪除.不用期待,很少有空的,啊哈哈哈.

最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 序言:七十年代末,一起剝皮案震驚了整個(gè)濱河市树叽,隨后出現(xiàn)的幾起案子舆蝴,更是在濱河造成了極大的恐慌,老刑警劉巖题诵,帶你破解...
    沈念sama閱讀 216,324評論 6 498
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件洁仗,死亡現(xiàn)場離奇詭異,居然都是意外死亡性锭,警方通過查閱死者的電腦和手機(jī)赠潦,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 92,356評論 3 392
  • 文/潘曉璐 我一進(jìn)店門,熙熙樓的掌柜王于貴愁眉苦臉地迎上來草冈,“玉大人她奥,你說我怎么就攤上這事≡趵猓” “怎么了哩俭?”我有些...
    開封第一講書人閱讀 162,328評論 0 353
  • 文/不壞的土叔 我叫張陵,是天一觀的道長拳恋。 經(jīng)常有香客問我凡资,道長,這世上最難降的妖魔是什么谬运? 我笑而不...
    開封第一講書人閱讀 58,147評論 1 292
  • 正文 為了忘掉前任隙赁,我火速辦了婚禮垦藏,結(jié)果婚禮上,老公的妹妹穿的比我還像新娘伞访。我一直安慰自己膝藕,他們只是感情好,可當(dāng)我...
    茶點(diǎn)故事閱讀 67,160評論 6 388
  • 文/花漫 我一把揭開白布咐扭。 她就那樣靜靜地躺著,像睡著了一般滑废。 火紅的嫁衣襯著肌膚如雪蝗肪。 梳的紋絲不亂的頭發(fā)上,一...
    開封第一講書人閱讀 51,115評論 1 296
  • 那天蠕趁,我揣著相機(jī)與錄音薛闪,去河邊找鬼。 笑死俺陋,一個(gè)胖子當(dāng)著我的面吹牛豁延,可吹牛的內(nèi)容都是我干的。 我是一名探鬼主播腊状,決...
    沈念sama閱讀 40,025評論 3 417
  • 文/蒼蘭香墨 我猛地睜開眼诱咏,長吁一口氣:“原來是場噩夢啊……” “哼!你這毒婦竟也來了缴挖?” 一聲冷哼從身側(cè)響起袋狞,我...
    開封第一講書人閱讀 38,867評論 0 274
  • 序言:老撾萬榮一對情侶失蹤,失蹤者是張志新(化名)和其女友劉穎映屋,沒想到半個(gè)月后苟鸯,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體,經(jīng)...
    沈念sama閱讀 45,307評論 1 310
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡棚点,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 37,528評論 2 332
  • 正文 我和宋清朗相戀三年早处,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片瘫析。...
    茶點(diǎn)故事閱讀 39,688評論 1 348
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡砌梆,死狀恐怖,靈堂內(nèi)的尸體忽然破棺而出颁股,到底是詐尸還是另有隱情么库,我是刑警寧澤,帶...
    沈念sama閱讀 35,409評論 5 343
  • 正文 年R本政府宣布甘有,位于F島的核電站诉儒,受9級特大地震影響,放射性物質(zhì)發(fā)生泄漏亏掀。R本人自食惡果不足惜忱反,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 41,001評論 3 325
  • 文/蒙蒙 一泛释、第九天 我趴在偏房一處隱蔽的房頂上張望。 院中可真熱鬧温算,春花似錦怜校、人聲如沸。這莊子的主人今日做“春日...
    開封第一講書人閱讀 31,657評論 0 22
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽。三九已至巩割,卻和暖如春裙顽,著一層夾襖步出監(jiān)牢的瞬間,已是汗流浹背宣谈。 一陣腳步聲響...
    開封第一講書人閱讀 32,811評論 1 268
  • 我被黑心中介騙來泰國打工愈犹, 沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留,地道東北人闻丑。 一個(gè)月前我還...
    沈念sama閱讀 47,685評論 2 368
  • 正文 我出身青樓漩怎,卻偏偏與公主長得像,于是被迫代替她去往敵國和親嗦嗡。 傳聞我的和親對象是個(gè)殘疾皇子勋锤,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 44,573評論 2 353

推薦閱讀更多精彩內(nèi)容

  • 一. 算法之變,結(jié)構(gòu)為宗 計(jì)算機(jī)在很多情況下被應(yīng)用于檢索數(shù)據(jù)侥祭,比如航空和鐵路運(yùn)輸業(yè)的航班信息和列車時(shí)刻表的查詢怪得,都...
    Leesper閱讀 6,895評論 13 42
  • 數(shù)據(jù)結(jié)構(gòu)與算法--從平衡二叉樹(AVL)到紅黑樹 上節(jié)學(xué)習(xí)了二叉查找樹。算法的性能取決于樹的形狀卑硫,而樹的形狀取決于...
    sunhaiyu閱讀 7,646評論 4 32
  • 原文鏈接 二叉查找樹 由于紅黑樹本質(zhì)上就是一棵二叉查找樹徒恋,所以在了解紅黑樹之前,咱們先來看下二叉查找樹欢伏。 二叉查找...
    非典型程序員閱讀 2,829評論 2 5
  • 最近花了些時(shí)間重拾數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)知識入挣,先嘗試了紅黑樹,花了大半個(gè)月的時(shí)間研究其原理和實(shí)現(xiàn)硝拧,下面是學(xué)習(xí)到的知識和一些...
    hoohack閱讀 1,520評論 8 30
  • B樹的定義 一棵m階的B樹滿足下列條件: 樹中每個(gè)結(jié)點(diǎn)至多有m個(gè)孩子径筏。 除根結(jié)點(diǎn)和葉子結(jié)點(diǎn)外,其它每個(gè)結(jié)點(diǎn)至少有m...
    文檔隨手記閱讀 13,218評論 0 25