紅黑樹算法介紹

一、紅黑樹的定義：

R-B Tree，全稱是Red-Black Tree，又稱為“紅黑樹”，它一種特殊的二叉查找樹。紅黑樹的每個節點上都有存儲位表示節點的顔色，可以是紅(Red)或黑(Black)。

1、紅黑樹的特性:

（1）每個節點或者是黑色，或者是紅色。

（2）根節點是黑色。

（3）每個葉子節點（NIL）是黑色。 [注意：這裡葉子節點，是指為空(NIL或NULL)的葉子節點！]

（4）如果一個節點是紅色的，則它的子節點必須是黑色的。

（5）從一個節點到該節點的子孫節點的所有路徑上包含相同數目的黑節點。

注意：

(01) 特性(3)中的葉子節點，是隻為空(NIL或null)的節點。

(02) 特性(5)，確定沒有一條路徑會比其他路徑長出倆倍。因而，紅黑樹是相對是接近平衡的二叉樹。

2、紅黑樹的應用：

紅黑樹的應用比較廣泛，主要是用它來存儲有序的資料，它的時間複雜度是O(lgn)，效率非常之高。

例如，Java中的TreeSet和TreeMap，C++ STL中的set、map，以及Linux虛拟記憶體的管理，都是通過紅黑樹去實作的。

3、R-B Tree時間複雜度

1）紅黑樹的時間複雜度為: O(lgn)。

2）高度為h的紅黑樹，它的包含的内節點個數至少為 2^bh(x)-1個”。是以，“一棵含有n個節點的紅黑樹的高度至多為2log(n+1)”。

二、紅黑樹的性能比較：

1、紅黑樹和AVL的共同點：

二叉查找樹的優化，保證動态集合操作在最壞情況下時間複雜度為O(lgn);

2、查找對比：

AVL查找最好最壞都是O(lgn);

R-B Tree查找基本維持在O(lgn),最壞比AVL略差(2lg(n+1)),但遠好于BST。

3、插入删除比較：

1）插入時，AVL和RBT都最多需要2次旋轉；删除時，AVL最多需要lgN次旋轉，而RBT最多需要3次旋轉；

2）RBT旋轉平衡時，需要變色操作，在O(lgN)數量級上，但操作簡單、速度快；

3）二者插入删除的代價主要消耗在查找操作上，都與O(lgN)成正比；

表明：R-B Tree的總體統計性能要好于AVL。

三、R-B Tree的插入和删除

紅黑樹節點插入和二叉搜尋樹插入相似，隻不過插入節點後可能會破壞紅黑樹平衡性，需要做平衡處理。為了繼續保持紅黑樹的性質，可以通過對結點進行重新着色，以及對樹進行相關的旋轉操作，即通過修改樹中某些結點的顔色及指針結構，來達到對紅黑樹進行插入或删除結點等操作後繼續保持它的性質或平衡的目的。

1、插入操作

1）首先以二叉查找樹的方法增加節點并标記它為紅色；并插入二叉樹時，有三種情況：

情況一：被插入的節點是根節點。

直接把此節點塗為黑色。

情況二：被插入的節點的父節點是黑色。

什麼也不需要做。節點被插入後，仍然是紅黑樹。

情況三：被插入的節點的父節點是紅色。

那麼，該情況與紅黑樹的“特性(5)”相沖突。情況三包含了“Case 1”、“Case 2” 和“Case 3”三種情況；情況三的目的是恢複紅黑樹的特性，它的處理思想是：将紅色的節點移到根節點；然後，将根節點設為黑色。下面介紹情況三的三種情況。

Case 1 現象：目前節點的父節點是紅色，且目前節點的祖父節點的另一個子節點（叔叔節點）也是紅色。

Case 1 處理政策：

(01) 将“父節點”設為黑色。

(02) 将“叔叔節點”設為黑色。

(03) 将“祖父節點”設為“紅色”。

(04) 将“祖父節點”設為“目前節點”(紅色節點)；即，之後繼續對“目前節點”進行操作。

Case 2 現象：目前節點的父節點是紅色，叔叔節點是黑色，且目前節點是其父節點的右孩子

Case 2 處理政策：

(01) 将“父節點”作為“新的目前節點”。

(02) 以“新的目前節點”為支點進行左旋。

Case 3 現象：目前節點的父節點是紅色，叔叔節點是黑色，且目前節點是其父節點的左孩子

Case 3 處理政策：

(01) 将“父節點”設為“黑色”。

(02) 将“祖父節點”設為“紅色”。

(03) 以“祖父節點”為支點進行右旋。

2、删除操作

将紅黑樹T内的節點z删除。需要執行的操作依次是：首先，将T當作一顆二叉樹，将節點删除；然後，通過RB-DELETE-FIXUP來對節點重新着色并旋轉，以此來保證删除節點後的樹仍然是一顆紅黑樹。

1）将T當作一顆二叉樹，将節點删除；

2）通過RB-DELETE-FIXUP來對節點重新着色并旋轉，以此來保證删除節點後的樹仍然是一顆紅黑樹；

會出現3種情況：

情況一：x是“紅+黑”節點。

直接把x設為黑色，結束。此時紅黑樹性質全部恢複。

情況二：x是“黑+黑”節點，且x是根。

什麼都不做，結束。此時紅黑樹性質全部恢複。

情況三：x是“黑+黑”節點，且x不是根。這又可以劃分了4種情況：Case 1、Case 2、Case 3、Case 4。情況三中RB-DELETE-FIXUP的思想是：将x所包含的額外的黑色不斷沿樹上移(向根方向移動)，直到：

(01) x指向一個“紅+黑”節點。此時，将x設為一個“黑”節點即可。

(02) x指向根。此時，将x設為一個“黑”節點即可。

(03) 做必要的旋轉和顔色修改。

Case 1 現象：x是“黑+黑”節點，x的兄弟節點是紅色。(此時x的父節點和x的兄弟節點的子節點都是黑節點)。

Case 1 處理政策：

(01) 将x的兄弟節點設為“黑色”。

(02) 将x的父節點設為“紅色”。

(03) 對x的父節點進行左旋。

(04) 左旋後，重新設定x的兄弟節點。

Case 2 現象：x是“黑+黑”節點，x的兄弟節點是黑色，x的兄弟節點的兩個孩子都是黑色。

Case 2 處理政策：

(01) 将x的兄弟節點設為“紅色”。

(02) 設定“x的父節點”為“新的x節點”。

Case 3 現象：x是“黑+黑”節點，x的兄弟節點是黑色；x的兄弟節點的左孩子是紅色，右孩子是黑色的。

Case 3 處理政策：

(01) 将x兄弟節點的左孩子設為“黑色”。

(02) 将x兄弟節點設為“紅色”。

(03) 對x的兄弟節點進行右旋。

(04) 右旋後，重新設定x的兄弟節點。

Case 4 現象1：x是“黑+黑”節點，x的兄弟節點是黑色；x的兄弟節點的左孩子是紅色，右孩子是黑色的。

Case 4 現象2：x是“黑+黑”節點，x的兄弟節點是黑色；x的兄弟節點的右孩子是紅色的。

Case 4 處理政策：

(01) 将x父節點顔色 指派給 x的兄弟節點。

(02) 将x父節點設為“黑色”。

(03) 将x兄弟節點的右子節設為“黑色”。

(04) 對x的父節點進行左旋。

(05) 設定“x”為“根節點”。