# 紅黑樹性質 ??????紅黑樹是廣泛應用的平衡二叉搜索樹之一（另外一種常見的平衡二叉搜索樹是AVL樹）。它是[SGI STL](http://blog.csdn.net/u013074465/article/details/42432179)唯一實現的一種搜索樹；是關聯容器的底部機制。 ?????和AVL樹所實現的平衡機制不同，但是同樣適用了單旋轉和雙旋轉操作修正樹以保證平衡。 ?????紅黑樹的性質： ???????????? 1. 每個節點都被著上黑色或者紅色。 ???????????? 2. 根節點是黑色。 ???????????? 3. 如果一個節點為紅色，那么其子節點必須都為黑色。 ???????????? 4. 任一節點到NULL指針的每條路徑上必須包含相同數目的黑節點（將NULL視為黑色）。 ?????? 根據性質4，新插入的節點必須為紅色，否則若新插入節點為黑色，則會使得該節點所在的路徑上的黑節點個數增加。 ?????? 根據性質3，新插入節點的父節點必須為黑色（因為上面已經證明新插入節點必須為紅色）。如果新節點插入后其父節點不為黑色則就要通過改變節點顏色和旋轉樹來保證紅黑樹性質。這就是下邊插入操作比較麻煩所在。 # 紅黑樹的插入操作 約定： X為新節點，P為父節點，G為祖父節點，S為叔節點，GG為曾祖父節點。 分以下兩種情況（父節點為黑或紅）討論插入操作： **一、 父節點為黑色** ???? ?? 直接插入X，插入操作完成。 **二、父節點為紅色** 在第一部分已經討論了，當父節點為紅色，就會違背紅黑樹的性質，要調整樹、改變節點顏色；此時，根據X插做左孩子還是右孩子和外圍節點（S和GG）的顏色，再分以下幾種情況討論： **情況1： S為黑且X為左孩子** ???? ???在P和G之間做一次右旋轉并改變G和P的顏色，即可。 ???? ? 注意，旋轉后可能會使樹的高度相差大于1，例如當圖中A、B為空但D或E不為空時。但這沒關系，因為紅黑樹的平衡性本來就比AVL樹弱，然而紅黑樹通常能導致良好的平衡狀態。紅黑樹與AVL樹平均效率相當，最壞情況下花費O(logN)。  **情況2：S為黑且X為右孩子** ???? ? 將P和X經過一次左旋轉便可以變回情況1的情形；改變G和X的顏色，然后再對G做一次右旋轉，即可。從這里的操作可以看出，所謂的雙旋轉其實就是兩次單旋轉。  **情況3：S為紅** ????? 分析此時所存在的問題：當S為紅色的時候，如圖5-15c所示，此時對P和G做一次旋轉并改變X的顏色。此時，如果GG為黑色，那么該操作完成。但是，如果GG為紅色，那么，旋轉后的G和GG均為紅色，不符合紅黑樹性質。 ?????? **解決方法**：當遇到這種情況的時候，我們可以采取的方式有兩種：上濾和自頂向下。以下分別介紹這兩種方法。  **上濾法**： ?????? 當GG也為紅色時，將情況3中提到的方法繼續沿著根的方向上濾，直到不再有父子連續為紅色的情況。 **自頂向下法**： ??????? 該方法是自上而下來保證S不會為紅色的過程。在向下的過程中，當遇到一個節點X的兩個兒子都是紅色，就將X改為紅色，而將兩個兒子改為黑色。這種翻轉只在X的父節點也為紅色時才會破壞紅黑樹的性質，但是可以使用情況1或情況2中的方法做調整。這個過程能夠保證不會遇到S節點為紅色的情況；因為我們是自上而下調整的，在調整到G節點時，已經將可能存在的、P和S同時為紅的情況破壞了。 ?????? 例如5-15e中，在尋找35插入的位置的過程中，我們從根節點開始尋找35應該插入的位置，其尋找的路徑為圖中虛箭頭所示的方向，在該向下找過程中，當X為50的時候，X的兩個孩子都是紅色，此時將X改為紅色，而將它的兩個孩子改為黑色；然后繼續找35應該插入的位置，這樣就確保了不會存在S為紅色的情況。  # 紅黑樹的刪除操作的