介紹

紅黑樹是一個平衡的二叉樹，但不是一個完美的平衡二叉樹。雖然我們希望一個所有查找都能在~lgN次比較內(nèi)結(jié)束，但是這樣在動態(tài)插入中保持樹的完美平衡代價太高，所以，我們稍微放松逛一下限制，希望找到一個能在對數(shù)時間內(nèi)完成查找的數(shù)據(jù)結(jié)構(gòu)。這個時候，紅黑樹站了出來。

閱讀以下需要了解普通二叉樹的插入以及刪除操作。

紅黑樹是在普通二叉樹上，對沒個節(jié)點(diǎn)添加一個顏色屬性形成的，同時整個紅黑二叉樹需要同時滿足一下五條性質(zhì)

紅黑樹需要滿足的五條性質(zhì)：

性質(zhì)一：節(jié)點(diǎn)是紅色或者是黑色；

在樹里面的節(jié)點(diǎn)不是紅色的就是黑色的，沒有其他顏色，要不怎么叫紅黑樹呢，是吧。

性質(zhì)二：根節(jié)點(diǎn)是黑色；

根節(jié)點(diǎn)總是黑色的。它不能為紅。

性質(zhì)三：每個葉節(jié)點(diǎn)（NIL或空節(jié)點(diǎn)）是黑色；

這個可能有點(diǎn)理解困難，可以看圖：

這個圖片就是一個紅黑樹，NIL節(jié)點(diǎn)是個空節(jié)點(diǎn)，并且是黑色的。

性質(zhì)四：每個紅色節(jié)點(diǎn)的兩個子節(jié)點(diǎn)都是黑色的（也就是說不存在兩個連續(xù)的紅色節(jié)點(diǎn)）；

就是連續(xù)的兩個節(jié)點(diǎn)不能是連續(xù)的紅色，連續(xù)的兩個節(jié)點(diǎn)的意思就是父節(jié)點(diǎn)與子節(jié)點(diǎn)不能是連續(xù)的紅色。

**性質(zhì)五：從任一節(jié)點(diǎn)到其沒個葉節(jié)點(diǎn)的所有路徑都包含相同數(shù)目的黑色節(jié)點(diǎn)；**

還是看圖：

1

2

3

從根節(jié)點(diǎn)到每一個NIL節(jié)點(diǎn)的路徑中，都包含了相同數(shù)量的黑色節(jié)點(diǎn)。

這五條性質(zhì)約束了紅黑樹，可以通過數(shù)學(xué)證明來證明，滿足這五條性質(zhì)的二叉樹可以將查找刪除維持在對數(shù)時間內(nèi)。

當(dāng)我們進(jìn)行插入或者刪除操作時所作的一切操作都是為了調(diào)整樹使之符合這五條性質(zhì)。

下面我們先介紹兩個基本操作，旋轉(zhuǎn)。

旋轉(zhuǎn)的目的是將節(jié)點(diǎn)多的一支出讓節(jié)點(diǎn)給另一個節(jié)點(diǎn)少的一支，旋轉(zhuǎn)操作在插入和刪除操作中經(jīng)常會用到，所以要熟記。

右旋：

下面講講插入

我們先明確一下各節(jié)點(diǎn)的叫法

因?yàn)橐獫M足紅黑樹的這五條性質(zhì)，如果我們插入的是黑色節(jié)點(diǎn)，那就違反了性質(zhì)五，需要進(jìn)行大規(guī)模調(diào)整，如果我們插入的是紅色節(jié)點(diǎn)，那就只有在要插入節(jié)點(diǎn)的父節(jié)點(diǎn)也是紅色的時候違反性質(zhì)四或者是當(dāng)插入的節(jié)點(diǎn)是根節(jié)點(diǎn)時，違反性質(zhì)二，所以，我們把要插入的節(jié)點(diǎn)的顏色變成紅色。

下面是可能遇到的插入的幾種狀況：

1、當(dāng)插入的節(jié)點(diǎn)是根節(jié)點(diǎn)時，直接涂黑即可；

2、當(dāng)要插入的節(jié)點(diǎn)的父節(jié)點(diǎn)是黑色的時候。

這個時候插入一個紅色的節(jié)點(diǎn)并沒有對這五個性質(zhì)產(chǎn)生破壞。所以直接插入不用在進(jìn)行調(diào)整操作。

3、如果要插入的節(jié)點(diǎn)的父節(jié)點(diǎn)是紅色且父節(jié)點(diǎn)是祖父節(jié)點(diǎn)的左支的時候。

這個要分兩種情況，一種是叔叔節(jié)點(diǎn)為黑的情況，一種是叔叔節(jié)點(diǎn)為紅的情況。

當(dāng)叔叔為黑時，也分為兩種情況，一種是要插入的節(jié)點(diǎn)是父節(jié)點(diǎn)的左支，另一種是要插入的節(jié)點(diǎn)是父親的右支。

我們先看一下當(dāng)要插入的節(jié)點(diǎn)是父節(jié)點(diǎn)的左支的情況：

這個時候違反了性質(zhì)四，我們就需要進(jìn)行調(diào)整操作，使之符合性質(zhì)四，我們可以通過對祖父節(jié)點(diǎn)進(jìn)行右旋同時將祖父節(jié)點(diǎn)和父節(jié)點(diǎn)的顏色進(jìn)行互換，這樣就變成了：

經(jīng)過這樣的調(diào)整可以符合性質(zhì)四并且不對其他性質(zhì)產(chǎn)生破壞。

當(dāng)插入的節(jié)點(diǎn)是父節(jié)點(diǎn)的右支的時候：

當(dāng)要插入的節(jié)點(diǎn)是父節(jié)點(diǎn)的右支的時候，我們可以先對父節(jié)點(diǎn)進(jìn)行左旋，變成如下：

如果我們把原先的父節(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)在父節(jié)點(diǎn)的左支的情況進(jìn)行旋轉(zhuǎn)，旋轉(zhuǎn)完之后變成如下：

4、如果要插入的節(jié)點(diǎn)的父節(jié)點(diǎn)是紅色且父節(jié)點(diǎn)是祖父節(jié)點(diǎn)的右支的時候；

這個時候的情況跟情況3所表述的情況是一個鏡像，將情況3的左和右互換一下就可以了。

5、如果要插入的節(jié)點(diǎn)的父節(jié)點(diǎn)是紅色并且叔叔節(jié)點(diǎn)也為紅色，如下：

這個時候，只需將父親節(jié)點(diǎn)和叔叔節(jié)點(diǎn)涂黑，將祖父節(jié)點(diǎn)涂紅。

以上就是插入的全部過程。

下面我們再講講刪除的操作：

首先你要了解普通二叉樹的刪除操作：

1.如果刪除的是葉節(jié)點(diǎn)，可以直接刪除；

2.如果被刪除的元素有一個子節(jié)點(diǎn)，可以將子節(jié)點(diǎn)直接移到被刪除元素的位置；

3.如果有兩個子節(jié)點(diǎn)，這時候就可以把被刪除元素的右支的最小節(jié)點(diǎn)（被刪除元素右支的最左邊的節(jié)點(diǎn)）和被刪除元素互換，我們把被刪除元素右支的最左邊的節(jié)點(diǎn)稱之為后繼節(jié)點(diǎn)（后繼元素），然后在根據(jù)情況1或者情況2進(jìn)行操作。如圖：

將被刪除元素與其右支的最小元素互換，變成如下圖所示：

然后再將被刪除元素刪除：

我們下面所稱的被刪除元素，皆是指已經(jīng)互換之后的被刪除元素。

加入顏色之后，被刪除元素和后繼元素互換只是值得互換，并不互換顏色，這個要注意。

下面開始講一下紅黑樹刪除的規(guī)則：

1.當(dāng)被刪除元素為紅時，對五條性質(zhì)沒有什么影響，直接刪除。

2.當(dāng)被刪除元素為黑且為根節(jié)點(diǎn)時，直接刪除。

3.當(dāng)被刪除元素為黑，且有一個右子節(jié)點(diǎn)為紅時，將右子節(jié)點(diǎn)涂黑放到被刪除元素的位置，如圖：

由

變成

4.當(dāng)被刪除元素為黑，且兄弟節(jié)點(diǎn)為黑，兄弟節(jié)點(diǎn)兩個孩子也為黑，父節(jié)點(diǎn)為紅，此時，交換兄弟節(jié)點(diǎn)與父節(jié)點(diǎn)的顏色；NIL元素是指每個葉節(jié)點(diǎn)都有兩個空的，顏色為黑的NIL元素，需要他的時候就可以把它看成兩個黑元素，不需要的時候可以忽視他。

如圖：

由

變成：

5.當(dāng)被刪除元素為黑、并且為父節(jié)點(diǎn)的左支，且兄弟顏色為黑，兄弟的右支為紅色，這個時候需要交換兄弟與父親的顏色，并把父親涂黑、兄弟的右支涂黑，并以父節(jié)點(diǎn)為中心左轉(zhuǎn)。如圖：

由：

變成：

6.當(dāng)被刪除元素為黑、并且為父節(jié)點(diǎn)的左支，且兄弟顏色為黑，兄弟的左支為紅色，這個時候需要先把兄弟與兄弟的左子節(jié)點(diǎn)顏色互換，進(jìn)行右轉(zhuǎn)，然后就變成了規(guī)則5一樣了，在按照規(guī)則5進(jìn)行旋轉(zhuǎn)。如圖：

由

先兄弟與兄弟的左子節(jié)點(diǎn)顏色互換，進(jìn)行右轉(zhuǎn)，變成：

然后在按照規(guī)則5進(jìn)行旋轉(zhuǎn)，變成：

7.當(dāng)被刪除元素為黑且為父元素的右支時，跟情況5.情況6 互為鏡像。

8.被刪除元素為黑且兄弟節(jié)點(diǎn)為黑，兄弟節(jié)點(diǎn)的孩子為黑，父親為黑，這個時候需要將兄弟節(jié)點(diǎn)變?yōu)榧t，再把父親看做那個被刪除的元素（只是看做，實(shí)際上不刪除），看看父親符和哪一條刪除規(guī)則，進(jìn)行處理變化如圖：

由：

變成：

8.當(dāng)被刪除的元素為黑，且為父元素的左支，兄弟節(jié)點(diǎn)為紅色的時候，需要交換兄弟節(jié)點(diǎn)與父親結(jié)點(diǎn)的顏色，以父親結(jié)點(diǎn)進(jìn)行左旋，就變成了情況4，在按照情況四進(jìn)行操作即可，變化如下：

由：

交換兄弟節(jié)點(diǎn)與父親結(jié)點(diǎn)的顏色，以父親結(jié)點(diǎn)進(jìn)行左旋 變成：

在按照情況四進(jìn)行操作，變成：

好了，刪除的步驟也講完，沒有講到的一點(diǎn)就是，在添加刪除的時候，時刻要記得更改根元素的顏色為黑。

這里并沒有語言實(shí)現(xiàn)，只是講了一下紅黑樹的插入刪除步驟，你可以根據(jù)步驟自己把紅黑樹實(shí)現(xiàn)。

點(diǎn)擊這里，照著規(guī)則一步一步的構(gòu)建一個紅黑樹吧。

最后：

1.紅黑樹的實(shí)現(xiàn)其實(shí)是一個2、3、4樹，只是將雙節(jié)點(diǎn)或者三節(jié)點(diǎn)用紅色進(jìn)行了標(biāo)示，如果你將紅色節(jié)點(diǎn)放到和它父元素相同的高度，并把它和父元素看做是一個元素，你就會發(fā)現(xiàn)，變成了一個高度為lgN的二叉樹，這個2.3.4樹對紅黑樹很有啟發(fā)意義。

2.上面的步驟其實(shí)可以不用死記硬背，是可以推導(dǎo)出來的，因?yàn)槲覀兪前岩粋€平衡但通過插入或者刪除破壞了平衡的紅黑樹再次平衡，同過旋轉(zhuǎn)讓位，改變紅黑顏色，使之符合那五條基本性質(zhì)。比如遇到刪除操作情況四的時候，我們可以把那個刪除元素去除，發(fā)現(xiàn)左邊比右邊少一個黑元素，這個時候，怎么辦，我們發(fā)現(xiàn)兄弟節(jié)點(diǎn)的子元素有一個紅元素，操作這個不會影響那五條性質(zhì)，所以我們通過變換顏色，旋轉(zhuǎn)，即可讓左右兩邊的的黑色數(shù)目一樣。

3.旋轉(zhuǎn)操作的目的是出讓一個元素到另外的地方并且符合二叉樹左小右大的性質(zhì)，交換顏色的目的是為了保持紅黑樹的那五條性質(zhì)。

4.要時刻記得 ，一切的操作都是為了保持那五條性質(zhì)。

最后的最后，其實(shí)還有一種更為簡單的紅黑二叉樹，這個簡單的紅黑二叉樹實(shí)際上是一個2.3樹，他只允許左節(jié)點(diǎn)為紅節(jié)點(diǎn)，但是性能上肯定是不如這個紅黑樹。這個簡單的紅黑二叉樹在《算法》第四版有介紹，掌握完之后再看這個簡單的紅黑二叉樹，就會覺著簡單 easy。

最后的最后的最后，一定要嘗試著自己推導(dǎo)一下插入刪除規(guī)則啊，不然經(jīng)常忘，是睡一覺起來再看就有點(diǎn)懵逼的那種忘。

http://blog.csdn.net/sun_tttt/article/details/65445754

http://www.cnblogs.com/CarpenterLee/p/5525688.html

http://www.cnblogs.com/skywang12345/p/3245399.html#!comments