紅黑樹（一）

紅黑樹基本規則：

1. 根節點與  NULL葉節點   都是黑色節點
2. 每個紅色節點的兩個子節點都是黑色節點，換句話說就是不能有連續兩個紅色節點，但是黑色可以連續
3. 從  根節點   到所有 NULL葉子節點路徑 上的 黑色節點 數量是相同的

紅黑樹的難點在于插入。

插入的大體步驟：

1.根據 規則3 确定需要插入的子節點的顔色：根據規則3，從根節點到所有NULL葉子節點路徑上的黑色節點的數量是一緻的，是以可以計算出任意其他路徑上的黑色節點的數量，來确定最後插入的顔色（這裡未涉及到插入點的位置）

2.分情況進行顔色更改和旋轉。

上圖中存在以下情況：

1、違反規則2（每個紅色節點的兩個子節點都是黑色節點，換句話說就是不能有連續兩個紅色節點），但是在兼顧規則3（根節點到NULL葉子節點路徑上的黑色節點的數量相同）的情況下，隻能對插入節點X的Parent p以及P的Parent PP進行顔色反轉（如果y有子節點還涉及到y的子節點的顔色反轉）；

2、經過1的顔色反轉，會導緻圖B中的x和P的紅色，違反了規則2（每個紅色節點的兩個子節點都是黑色節點，換句話說就是不能有連續兩個紅色節點），但是并未違反規則3，需要旋轉調整（左旋還是右旋？）

3、左旋還是右旋的确定。如果目前插入的子節點是 某個沖突節點X 的左子樹，那麼進行的就應該是右旋；反之，目前插入的節點是沖突節點的右子樹就進行一次左旋。