1.4.3.1 RB Tree Insertion

紅黑樹的插入演算法

紅黑樹的插入, 前面的部分跟二元搜尋樹一樣, 就是從根節點向下尋找節點要插入的位置, 找到後插入節點; 插入節點後, 多了這樣的一個操作: 檢查樹是否平衡, 如果不平衡, 就要做修復, 使樹重新變得平衡.

在開始討論插入演算法之前, 先釐清節點之間的關係與簡稱:

插入新的節點, 通常會設置這個節點為紅色, 因為這樣可以降低違反紅黑規則的機率, 而插入節點後, 會有以下幾點的情境出現:

1. 若插入的是根節點, 那麼違反規則2(根總是黑色的), 那就直接把節點改成黑色的

2. 若插入節點的P節點是黑色的, 即符合規則, 就什麼都不做

3. 若插入節點的P節點是紅色的, 且U節點也是紅色的, 那麼: 將G節點變紅, 而P與U節點變黑(遵守規則5), 然後設置G節點為current node, 並且重新開始調整
4. 若插入節點的P節點是紅色的, 而U節點是黑色或缺少, 且插入節點是其P節點的左子節點, 而P節點是G節點的左子節點, 那麼: 把P節點變成黑色, G節點變為紅色, 然後對G節點做右旋的動作, 最後重新開始調整
5. 若插入節點的P節點是紅色的, 而U節點是黑色或缺少, 且插入節點是其P節點的右子節點, 而P節點是G節點的右子節點, 那麼: 把P節點變成黑色, G節點變為紅色, 然後對G節點做左旋的動作, 最後重新開始調整
6. 若插入節點的P節點是紅色的, 而U節點是黑色或缺少, 且插入節點是其P節點的右子節點, 而P節點是G節點的左子節點, 那麼: 把當前節點的P節點作為新的當前節點, 對新的當前節點進行左旋, 並且重新開始調整
7. 若插入節點的P節點是紅色的, 而U節點是黑色或缺少, 且插入節點是其P節點的左子節點, 而P節點是G節點的右子節點, 那麼: 把當前節點的P節點作為新的當前節點, 對新的當前節點進行右旋, 最後重新開始調整