本篇博客我會(huì)重點(diǎn)介紹對(duì)紅-黑樹(shù)的理解，重點(diǎn)介紹紅-黑樹(shù)的查找，這里我們將要討論的算法稱(chēng)為自頂向下插入，也就是把沿著樹(shù)向下查找插入點(diǎn)

?

Ⅰ、平衡樹(shù)和非平衡樹(shù)

?

　　平衡樹(shù)和非平衡樹(shù)：當(dāng)插入一組數(shù)據(jù)關(guān)鍵字是按照升序或者降序插入的話此時(shí)就是集中最極端的不平衡樹(shù)，此時(shí)也可看做是一個(gè)鏈表此時(shí)對(duì)于此樹(shù)的查找的時(shí)間復(fù)雜度為O(N),所以搜索不平衡樹(shù)的時(shí)間復(fù)雜度介于平衡樹(shù)時(shí)間復(fù)雜度O(logN)和O(N)之間時(shí)間具體取決于樹(shù)的不平衡度。

?

Ⅱ、紅-黑樹(shù)規(guī)則

?

　　接下來(lái)我們要討論的紅-黑樹(shù)具有以下幾個(gè)特征（紅-黑樹(shù)規(guī)則）：

• 　　1.每一個(gè)節(jié)點(diǎn)不是紅色就是黑色
• 　　2.根總是黑色的
• 　　3.若節(jié)點(diǎn)是紅色的，則它的子節(jié)點(diǎn)必須全是黑色的（反過(guò)來(lái)就不一定成立）
• 　　4.從根到葉節(jié)點(diǎn)或空子節(jié)點(diǎn)的每一條路徑必須包含相同數(shù)目的黑色節(jié)點(diǎn)

　　第四條中的“空子節(jié)點(diǎn)”指的是有右子節(jié)點(diǎn)的節(jié)點(diǎn)可能接左子節(jié)點(diǎn)的位置，或者說(shuō)有左子節(jié)點(diǎn)的節(jié)點(diǎn)可能接右子節(jié)點(diǎn)的位置。就是非葉節(jié)點(diǎn)本可能有，但是實(shí)際上沒(méi)有的那個(gè)子節(jié)點(diǎn)（若節(jié)點(diǎn)只有右子節(jié)點(diǎn)，那么空缺的左子節(jié)點(diǎn)就是空子節(jié)點(diǎn)，反之亦然）下圖中50→25→25的右子節(jié)點(diǎn)（空子節(jié)點(diǎn)）黑色高度為1，從根到6以及到75的黑色節(jié)點(diǎn)數(shù)都為2，這樣就違背了規(guī)則4，此樹(shù)到葉節(jié)點(diǎn)的黑色節(jié)點(diǎn)數(shù)相同，但是有一個(gè)空子節(jié)點(diǎn)的黑色節(jié)點(diǎn)數(shù)為1所以此樹(shù)不是紅-黑樹(shù)。

?

　　從根節(jié)點(diǎn)到葉節(jié)點(diǎn)路徑上面的黑色節(jié)點(diǎn)數(shù)目稱(chēng)為黑色高度，所以上面的規(guī)則四的另一種陳述方法是：所有從根到葉節(jié)點(diǎn)路徑上的黑色高度必須相同。

　　為了滿足紅黑樹(shù)規(guī)則我們可能會(huì)使用到下面兩種方式來(lái)進(jìn)行修正，從而使一棵樹(shù)滿足紅黑樹(shù)規(guī)則，

改變節(jié)點(diǎn)顏色

執(zhí)行旋轉(zhuǎn)操作

　　為什么保證上面四個(gè)紅-黑樹(shù)規(guī)則就能保證紅-黑樹(shù)是平衡樹(shù)呢？從紅黑樹(shù)規(guī)則分析我們可以得到若一棵樹(shù)超過(guò)了兩層不平衡怎這棵樹(shù)則不可能滿足紅-黑樹(shù)規(guī)則，超過(guò)兩層不平衡則表明有路徑的節(jié)點(diǎn)數(shù)比另外的路徑的節(jié)點(diǎn)數(shù)多一個(gè)以上，多出來(lái)的要么有更多的黑色節(jié)點(diǎn)，若這樣則違背了紅-黑樹(shù)規(guī)則4，要么至少有兩個(gè)相鄰接的紅色節(jié)點(diǎn)，這樣就違背了紅色節(jié)點(diǎn)的子節(jié)點(diǎn)必須全部是黑色節(jié)點(diǎn)。

?

Ⅲ、樹(shù)的旋轉(zhuǎn)：

?

　　利用樹(shù)的旋轉(zhuǎn)來(lái)重新排列一些節(jié)點(diǎn)，來(lái)平衡一棵樹(shù)，旋轉(zhuǎn)必須要做到兩件事情：

使一些節(jié)點(diǎn)上升，一些節(jié)點(diǎn)下降，幫助樹(shù)平衡

保證不破壞二叉搜索樹(shù)的特征（由于搜索算法依賴(lài)此特征，不然就沒(méi)意義）

　　上面利用紅黑樹(shù)的顏色規(guī)則和節(jié)點(diǎn)的顏色變化只是有助于決定何時(shí)執(zhí)行旋轉(zhuǎn)。光改變顏色并不能讓分樹(shù)達(dá)到平衡，旋轉(zhuǎn)才是讓樹(shù)平衡的關(guān)鍵操作，所以我們要好好理解樹(shù)的旋轉(zhuǎn)操作；做旋轉(zhuǎn)的時(shí)候要注意做右旋頂點(diǎn)必須要有一個(gè)左子節(jié)點(diǎn)，左旋頂端必須要有右子節(jié)點(diǎn)，不然旋轉(zhuǎn)后頂點(diǎn)會(huì)沒(méi)有節(jié)點(diǎn)，接下來(lái)我們看下圖的一個(gè)簡(jiǎn)單的旋轉(zhuǎn)：

　　上圖中a→b我們可以看到該樹(shù)進(jìn)行了一次右旋，a圖中節(jié)點(diǎn)37稱(chēng)為頂端節(jié)點(diǎn)50的內(nèi)側(cè)子孫（節(jié)點(diǎn)12是外側(cè)子孫點(diǎn)），對(duì)內(nèi)側(cè)子孫而言，如果他是上移的節(jié)點(diǎn)的子節(jié)點(diǎn)，它就必須要斷開(kāi)和父節(jié)點(diǎn)的連接并且重新連接到它以前的爺爺節(jié)點(diǎn)之上，就好像自己成為了自己的叔叔一樣。上圖是旋轉(zhuǎn)過(guò)程中單節(jié)點(diǎn)的位置變換，上面我們說(shuō)的內(nèi)側(cè)子孫也可以是一棵子樹(shù)，下圖我們展示了假如是子樹(shù)的節(jié)點(diǎn)的一個(gè)移動(dòng)情況，大致的原理差不多是相通的。

?

　　上圖中的樹(shù)進(jìn)行了一次右旋，做了以下幾個(gè)事情：

• 　頂端節(jié)點(diǎn)（50）移動(dòng)到他右子節(jié)點(diǎn)的位置
• 　頂端節(jié)點(diǎn)的左子節(jié)點(diǎn)（25）移動(dòng)到頂端的位置上
• 　以節(jié)點(diǎn)12為根的整棵子樹(shù)都向上移動(dòng)
• 　因節(jié)點(diǎn)為37為根的整棵子樹(shù)橫向移動(dòng)，成為節(jié)點(diǎn)50的左子節(jié)點(diǎn)
• 　以節(jié)點(diǎn)75為根的整棵子樹(shù)向下移動(dòng)

　　上面我們看到了旋轉(zhuǎn)一棵樹(shù)要進(jìn)行怎么樣的旋轉(zhuǎn)，接下來(lái)我們討論如何插入一個(gè)新節(jié)點(diǎn)（利用旋轉(zhuǎn)和顏色規(guī)則來(lái)保持樹(shù)的平衡）

Ⅳ、節(jié)點(diǎn)的插入

　　在我們向下查找插入點(diǎn)的時(shí)候我們主要討論一下三個(gè)方面

下行途中的顏色變化

向下路途上的旋轉(zhuǎn)

插入節(jié)點(diǎn)后的旋轉(zhuǎn)

　?、?下行途中的顏色變化

　　首先我們討論下行途中的顏色變化查找的方式和普通的二叉搜索樹(shù)是一樣的，只是在下行的途中會(huì)涉及到顏色的變化，規(guī)則如下：每當(dāng)遇到一個(gè)有兩個(gè)紅色子節(jié)點(diǎn)的黑色節(jié)點(diǎn)時(shí)，它必須把子節(jié)點(diǎn)變?yōu)楹谏?#xff0c;把父節(jié)點(diǎn)變?yōu)榧t色（除非父節(jié)點(diǎn)為根節(jié)點(diǎn)），如下圖就進(jìn)行了一次顏色變換

　　上圖中進(jìn)行顏色變化沒(méi)有改變從根向下過(guò)P到葉節(jié)點(diǎn)或空子節(jié)點(diǎn)路徑上的黑色節(jié)點(diǎn)的數(shù)目因此顏色變換并沒(méi)有違反規(guī)則4，這樣變化的好處是在不違背規(guī)則3的情況下連接新的紅色節(jié)點(diǎn)更容易。上面顏色變化雖然不會(huì)違背規(guī)則4但是有可能違背規(guī)則3，若上圖中P節(jié)點(diǎn)的父節(jié)點(diǎn)是紅色，那么變換之后就違背了規(guī)則3，那么此時(shí)就會(huì)對(duì)樹(shù)進(jìn)行旋轉(zhuǎn)操作，

　?、?在向下的路徑上的旋轉(zhuǎn)

　　向下路徑上的旋轉(zhuǎn)有兩種可能性，當(dāng)違背的節(jié)點(diǎn)是外側(cè)的子孫節(jié)點(diǎn)“違背規(guī)則的節(jié)點(diǎn)”是指在造成紅紅沖突的父子節(jié)點(diǎn)對(duì)中的子節(jié)點(diǎn)，我們從50開(kāi)始創(chuàng)建一棵新樹(shù)插入以下節(jié)點(diǎn)：25,75,12,37,6和18在插入12和6的時(shí)候需要做顏色變換。接下來(lái)我們要插入節(jié)點(diǎn)3，必須對(duì)節(jié)點(diǎn)12以及它的子節(jié)點(diǎn)6和18做顏色變換，此時(shí)生成的樹(shù)就是下圖中的a樹(shù)，此時(shí)節(jié)點(diǎn)25和12違背了紅黑樹(shù)規(guī)則3，此時(shí)需要對(duì)此樹(shù)進(jìn)行旋轉(zhuǎn)的操作，

?

　　這里我們?cè)O(shè)剛剛進(jìn)行顏色變換的三角形的頂點(diǎn)為X，X的父節(jié)點(diǎn)為p，祖父節(jié)點(diǎn)為G，此時(shí)我們對(duì)上圖中的a進(jìn)行如下的顏色變化和旋轉(zhuǎn)：

改變X的祖父節(jié)點(diǎn)P的顏色（本例中旋轉(zhuǎn)后還必須要改變根的顏色）

改變X父節(jié)點(diǎn)P的顏色

以X的祖父節(jié)點(diǎn)G為頂旋轉(zhuǎn)，向X上升的方向旋轉(zhuǎn)

　　這樣 就滿足了紅-黑樹(shù)的顏色規(guī)則，樹(shù)就成為了一棵平衡樹(shù)，此時(shí)就能很容易地插入節(jié)點(diǎn)3，插入之后如上圖中的b圖所示。

　　若插入的是內(nèi)側(cè)的子孫節(jié)點(diǎn)，此時(shí)我們以根為50，插入25,75,12,37,31和43.在插入12和31之前需要顏色變換，然后新插入節(jié)點(diǎn)28，向下查找插入點(diǎn)的時(shí)候，在37節(jié)點(diǎn)的時(shí)候需要執(zhí)行顏色變換，變換后如下圖的a樹(shù)所示，變換后25和37都是紅色需要進(jìn)行旋轉(zhuǎn)操作，此時(shí)顏色變換三角形的頂點(diǎn)X為37，P為25，G為50，執(zhí)行以下四步使樹(shù)從新平衡

改變G的顏色

改變X的顏色

以P為頂旋轉(zhuǎn)向X上升的方向旋轉(zhuǎn)，旋轉(zhuǎn)結(jié)果如下圖b所示

以G為頂旋轉(zhuǎn)，X上升方向旋轉(zhuǎn)，旋轉(zhuǎn)后即可輕松插入節(jié)點(diǎn)28

　?、?插入節(jié)點(diǎn)之后的旋轉(zhuǎn)

　　接下來(lái)我們討論插入節(jié)點(diǎn)之后的旋轉(zhuǎn)，這里我們討論插入的節(jié)點(diǎn)為X，其父節(jié)點(diǎn)為P，祖父節(jié)點(diǎn)為G。1.若節(jié)點(diǎn)X在P的一側(cè)與P在G的一側(cè)相同，則X就是一個(gè)外側(cè)的子孫節(jié)點(diǎn)（a，d），反之若不相同則X是一個(gè)內(nèi)側(cè)子孫節(jié)點(diǎn)（b，c）。下圖顯示了”指向“左右變化的多樣性

?

　　為恢復(fù)紅黑規(guī)則所執(zhí)行的操作是由X和它的親屬所決定的，節(jié)點(diǎn)只以三種當(dāng)時(shí)排列（上面的指向變換不算在內(nèi)）

P是黑色的。

P是紅色的，X是G的一個(gè)外側(cè)子孫節(jié)點(diǎn)

P是紅色的X是G的一個(gè)內(nèi)側(cè)的子孫節(jié)點(diǎn)，如下圖所示

可能性1：若P是黑色的 ：不需要做任何事情，由于插入的節(jié)點(diǎn)總是紅色的。若父節(jié)點(diǎn)是黑色的，則 沒(méi)有紅色節(jié)點(diǎn)連接紅色節(jié)點(diǎn)沖突也不會(huì)增加黑色節(jié)點(diǎn)數(shù)目，所以此時(shí)插入不需要做任何事情。

可能性2：P是紅色，X是G的一個(gè)外側(cè)子孫節(jié)點(diǎn)：這是插入后需要一次旋轉(zhuǎn)和一些顏色變化，此時(shí)我們可以創(chuàng)建一個(gè)根為50的樹(shù)，然后插入25,75和12。在插入12之前需要做一次顏色變換，然后向該樹(shù)中插入6，得到下圖中的a樹(shù)，此時(shí)違背了紅黑樹(shù)規(guī)則，需要進(jìn)行一下三個(gè)步驟的變換，

• 改變X的祖父節(jié)點(diǎn)G的顏色。
• 改變X父節(jié)點(diǎn)P的顏色。
• 以X的祖父節(jié)點(diǎn)G為頂旋轉(zhuǎn)，方向?yàn)閄的上升方向，變換后的樹(shù)如下圖中的b，再次成為一棵紅黑樹(shù)

可能性3：P是紅色的X是G的一個(gè)內(nèi)側(cè)的子孫節(jié)點(diǎn)，這時(shí)需要做兩次旋轉(zhuǎn)和一些顏色改變，首先我們創(chuàng)建一顆節(jié)點(diǎn)為50,25,75,12,18的樹(shù)（在插入節(jié)點(diǎn)12之前需要一次顏色變換）插入12后的樹(shù)如下圖a所示，插入節(jié)點(diǎn)18是一個(gè)內(nèi)側(cè)子孫節(jié)點(diǎn)，他和他的父節(jié)點(diǎn)都是紅色，首先第一次旋轉(zhuǎn)將子孫節(jié)點(diǎn)變?yōu)橥鈧?cè)子孫節(jié)點(diǎn)，下圖中的b->c然后就可以利用同情況1相同的旋轉(zhuǎn)，顏色轉(zhuǎn)換和旋轉(zhuǎn)的步驟如下：

• 改變X的祖父節(jié)點(diǎn)25的顏色
• 改變X節(jié)點(diǎn)18的顏色
• 用X的父節(jié)點(diǎn)P作為頂旋轉(zhuǎn)，方向?yàn)閄上升的方向
• 再以X的祖父節(jié)點(diǎn)25為頂旋轉(zhuǎn)，方向?yàn)閄上升的方向

?

　　接下來(lái)我們討論上面三種情況是否包含了所有的情況：

• 首先我們假設(shè)X有一個(gè)兄弟節(jié)點(diǎn)S，他是P的另外一個(gè)子節(jié)點(diǎn)，如果P是黑色的插入X沒(méi)有問(wèn)題（對(duì)應(yīng)情況1），如果P是紅色的那么他的兩個(gè)子節(jié)點(diǎn)必須是黑色，所以此時(shí)不能單獨(dú)存在一個(gè)黑色子節(jié)點(diǎn)S，否則路徑上的黑色高度就不一樣了，當(dāng)P為紅色的時(shí)候X不可能有兄弟節(jié)點(diǎn)。
• 另外一種可能是P的父節(jié)點(diǎn)G有一個(gè)子節(jié)點(diǎn)U，U是P的兄弟節(jié)點(diǎn)和X的樹(shù)節(jié)點(diǎn)，此時(shí)如果P是黑色的，插入X不需要進(jìn)行旋轉(zhuǎn)。假設(shè)P是紅色的，那么U必須也是紅色的，不然黑色高度就不同了，這種情況在當(dāng)我們沿路徑向下查找插入點(diǎn)的時(shí)候會(huì)變換顏色，會(huì)將P和U都變換成黑色節(jié)點(diǎn)，所以此時(shí)有變換回了情況1。

　　因此上面討論的三種可能性是全部可能存在的情況（在可能性2和3中X可能是右子節(jié)點(diǎn)或者左子節(jié)點(diǎn)，以及G可能是右子節(jié)點(diǎn)或者左子節(jié)點(diǎn)）

Ⅴ、紅-黑樹(shù)的刪除

　　之前我們討論的二叉搜索樹(shù)編寫(xiě)刪除的代碼比編寫(xiě)插入的操作的代碼要難很多，紅-黑樹(shù)也是如此，刪除節(jié)點(diǎn)后要恢復(fù)紅黑規(guī)則變得很復(fù)雜，一般我們會(huì)用其他的方法來(lái)回避，比如說(shuō)只將節(jié)點(diǎn)做刪除的標(biāo)記而不真正的刪除

Ⅵ、紅-黑樹(shù)的效率

　　和一般的二叉搜索樹(shù)類(lèi)似，紅-黑樹(shù)的查找，插入刪除的時(shí)間復(fù)雜度為O(log₂N),紅-黑樹(shù)的查找時(shí)間和普通的二叉搜索樹(shù)查找的時(shí)間幾乎完全一樣，額外的開(kāi)銷(xiāo)只是存儲(chǔ)空間增加了一個(gè)存儲(chǔ)紅黑顏色的空間。

　　插入和刪除的時(shí)間增加了一個(gè)常數(shù)因子，因?yàn)椴坏貌辉谙滦械穆窂缴虾筒迦朦c(diǎn)執(zhí)行顏色變換和旋轉(zhuǎn)。平均一次插入大概需要一次旋轉(zhuǎn)，因此插入的時(shí)間復(fù)雜度還是O(log₂N)但是比普通的二叉搜索樹(shù)要慢（不用做顏色變換和旋轉(zhuǎn)）

　　大多數(shù)應(yīng)用中查找的次數(shù)比插入和刪除的次數(shù)多，所以應(yīng)用紅-黑樹(shù)取代二叉搜索樹(shù)不會(huì)增加太多的時(shí)間開(kāi)銷(xiāo)，紅-黑樹(shù)最大的優(yōu)點(diǎn)就是對(duì)有序的數(shù)據(jù)的操作不會(huì)慢到O(N)的時(shí)間復(fù)雜度。

轉(zhuǎn)載于:https://www.cnblogs.com/zhoukebo/p/9307685.html

總結(jié)

以上是生活随笔為你收集整理的JAVA数据结构之红-黑树的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。