紅黑樹是一個平衡的二叉樹，但不是一個完美的平衡二叉樹。雖然我們希望一個所有查找都能在~lgN次比較内結束，但是這樣在動态插入中保持樹的完美平衡代價太高，所以，我們稍微放松逛一下限制，希望找到一個能在對數時間内完成查找的數據結構。這個時候，紅黑樹站了出來。

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

紅黑樹是在普通二叉樹上，對沒個節點添加一個顔色屬性形成的，同時整個紅黑二叉樹需要同時滿足一下五條性質

紅黑樹需要滿足的五條性質：

性質一：節點是紅色或者是黑色；

在樹裡面的節點不是紅色的就是黑色的，沒有其他顔色，要不怎麼叫紅黑樹呢，是吧。

性質二：根節點是黑色；

根節點總是黑色的。它不能為紅。

性質三：每個葉節點（NIL或空節點）是黑色；

這個可能有點理解困難，可以看圖：

這個圖片就是一個紅黑樹，NIL節點是個空節點，并且是黑色的。

性質四：每個紅色節點的兩個子節點都是黑色的（也就是說不存在兩個連續的紅色節點）；

就是連續的兩個節點不能是連續的紅色，連續的兩個節點的意思就是父節點與子節點不能是連續的紅色。

性質五：從任一節點到其沒個葉節點的所有路徑都包含相同數目的黑色節點；

從上圖可以看見相同數量的黑色節點有三個；

當我們進行插入或者删除操作時所作的一切操作都是為了調整樹使之符合這五條性質。

下面我們先介紹兩個基本操作，旋轉。

旋轉的目的是将節點多的一支出讓節點給另一個節點少的一支，旋轉操作在插入和删除操作中經常會用到，所以要熟記。

下面是左旋和右旋：

左旋：

右旋：

下面講講插入

我們先明确一下各節點的叫法

因為要滿足紅黑樹的這五條性質，如果我們插入的是黑色節點，那就違反了性質五，需要進行大規模調整，如果我們插入的是紅色節點，那就隻有在要插入節點的父節點也是紅色的時候違反性質四或者是當插入的節點是根節點時，違反性質二，所以，我們把要插入的節點的顔色變成紅色。

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

1、當插入的節點是根節點時，直接塗黑即可；

2、當要插入的節點的父節點是黑色的時候。

這個時候插入一個紅色的節點并沒有對這五個性質産生破壞。所以直接插入不用在進行調整操作。

3、如果要插入的節點的父節點是紅色且父節點是祖父節點的左支的時候。

這個要分兩種情況，一種是叔叔節點為黑的情況，一種是叔叔節點為紅的情況。

當叔叔為黑時，也分為兩種情況，一種是要插入的節點是父節點的左支，另一種是要插入的節點是父親的右支。

我們先看一下當要插入的節點是父節點的左支的情況：

這個時候違反了性質四，我們就需要進行調整操作，使之符合性質四，我們可以通過對祖父節點進行右旋同時将祖父節點和父節點的顔色進行互換，這樣就變成了：

經過這樣的調整可以符合性質四并且不對其他性質産生破壞。

當插入的節點是父節點的右支的時候：

當要插入的節點是父節點的右支的時候，我們可以先對父節點進行左旋，變成如下：

如果我們把原先的父節點看做是新的要插入的節點，把原先要插入的節點看做是新的父節點，那就變成了當要插入的節點在父節點的左支的情況，對，是的，就是按照當要插入的節點在父節點的左支的情況進行旋轉，旋轉完之後變成如下：

4、如果要插入的節點的父節點是紅色且父節點是祖父節點的右支的時候；

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

5、如果要插入的節點的父節點是紅色并且叔叔節點也為紅色，如下：

這個時候，隻需将父親節點和叔叔節點塗黑，将祖父節點塗紅。

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

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

1.如果删除的是葉節點，可以直接删除；

2.如果被删除的元素有一個子節點，可以将子節點直接移到被删除元素的位置；

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

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

然後再将被删除元素删除：

我們下面所稱的被删除元素，皆是指已經互換之後的被删除元素。

加入顔色之後，被删除元素和後繼元素互換隻是值得互換，并不互換顔色，這個要注意。

下面開始講一下紅黑樹删除的規則：

1.當被删除元素為紅時，對五條性質沒有什麼影響，直接删除。

2.當被删除元素為黑且為根節點時，直接删除。

3.當被删除元素為黑，且有一個右子節點為紅時，将右子節點塗黑放到被删除元素的位置，如圖：

由

變成

4.當被删除元素為黑，且兄弟節點為黑，兄弟節點兩個孩子也為黑，父節點為紅，此時，交換兄弟節點與父節點的顔色；NIL元素是指每個葉節點都有兩個空的，顔色為黑的NIL元素，需要他的時候就可以把它看成兩個黑元素，不需要的時候可以忽視他。

如圖：

由

變成：

5.當被删除元素為黑、并且為父節點的左支，且兄弟顔色為黑，兄弟的右支為紅色，這個時候需要交換兄弟與父親的顔色，并把父親塗黑、兄弟的右支塗黑，并以父節點為中心左轉。如圖：

由：

變成：

6.當被删除元素為黑、并且為父節點的左支，且兄弟顔色為黑，兄弟的左支為紅色，這個時候需要先把兄弟與兄弟的左子節點顔色互換，進行右轉，然後就變成了規則5一樣了，在按照規則5進行旋轉。如圖：

由

先兄弟與兄弟的左子節點顔色互換，進行右轉，變成：

然後在按照規則5進行旋轉，變成：

7.當被删除元素為黑且為父元素的右支時，跟情況5.情況6 互為鏡像。

8.被删除元素為黑且兄弟節點為黑，兄弟節點的孩子為黑，父親為黑，這個時候需要将兄弟節點變為紅，再把父親看做那個被删除的元素（隻是看做，實際上不删除），看看父親符和哪一條删除規則，進行處理變化如圖：

由：

變成：

8.當被删除的元素為黑，且為父元素的左支，兄弟節點為紅色的時候，需要交換兄弟節點與父親結點的顔色，以父親結點進行左旋，就變成了情況4，在按照情況四進行操作即可，變化如下：

由：

交換兄弟節點與父親結點的顔色，以父親結點進行左旋 變成：

在按照情況四進行操作，變成：

好了，删除的步驟也講完，沒有講到的一點就是，在添加删除的時候，時刻要記得更改根元素的顔色為黑。

這裡并沒有語言實現，隻是講了一下紅黑樹的插入删除步驟，你可以根據步驟自己把紅黑樹實現。

點擊這裡，照着規則一步一步的構建一個紅黑樹吧。

最後：

1.紅黑樹的實現其實是一個2、3、4樹，隻是将雙節點或者三節點用紅色進行了标示，如果你将紅色節點放到和它父元素相同的高度，并把它和父元素看做是一個元素，你就會發現，變成了一個高度為lgN的二叉樹，這個2.3.4樹對紅黑樹很有啟發意義。

2.上面的步驟其實可以不用死記硬背，是可以推導出來的，因為我們是把一個平衡但通過插入或者删除破壞了平衡的紅黑樹再次平衡，同過旋轉讓位，改變紅黑顔色，使之符合那五條基本性質。比如遇到删除操作情況四的時候，我們可以把那個删除元素去除，發現左邊比右邊少一個黑元素，這個時候，怎麼辦，我們發現兄弟節點的子元素有一個紅元素，操作這個不會影響那五條性質，所以我們通過變換顔色，旋轉，即可讓左右兩邊的的黑色數目一樣。

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

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

最後的最後，其實還有一種更為簡單的紅黑二叉樹，這個簡單的紅黑二叉樹實際上是一個2.3樹，他隻允許左節點為紅節點，但是性能上肯定是不如這個紅黑樹。這個簡單的紅黑二叉樹在《算法》第四版有介紹，掌握完之後再看這個簡單的紅黑二叉樹，就會覺着簡單 easy。

最後的最後的最後，一定要嘗試着自己推導一下插入删除規則啊，不然經常忘，是睡一覺起來再看就有點懵逼的那種忘。