> For the complete documentation index, see [llms.txt](https://clu.gitbook.io/data-structure-note/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://clu.gitbook.io/data-structure-note/1.4.1.1-rb-tree-insert.md).

# 1.4.3.1 RB Tree Insertion

紅黑樹的插入演算法

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

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

![](https://649506553-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M523o38bFiI5-RlHn7V%2F-M523rpyYLd_bz4SsJlN%2F-M523tnYGLLrug_gH2GC%2Frbtree-3.png?generation=1587042034394096\&alt=media)

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

1. 若插入的是根節點, 那麼**違反規則2**(根總是黑色的), 那就直接把節點改成黑色的
2. 若插入節點的P節點是黑色的, 即符合規則, 就什麼都不做
3. 若插入節點的P節點是紅色的, 且U節點也是紅色的, 那麼: 將G節點變紅, 而P與U節點變黑(**遵守規則5**), 然後設置G節點為current node, 並且重新開始調整\
   ![](https://649506553-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M523o38bFiI5-RlHn7V%2F-M523rpyYLd_bz4SsJlN%2F-M523tn_UQc2LNwQQK9f%2Frbtree-4.png?generation=1587042034216515\&alt=media)
4. 若插入節點的P節點是紅色的, 而U節點是黑色或缺少, 且插入節點是其P節點的左子節點, 而P節點是G節點的左子節點, 那麼: 把P節點變成黑色, G節點變為紅色, 然後對G節點做右旋的動作, 最後重新開始調整\
   ![](https://649506553-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M523o38bFiI5-RlHn7V%2F-M523rpyYLd_bz4SsJlN%2F-M523tnbsbMDml8zYznJ%2Frbtree-5.png?generation=1587042034778805\&alt=media)
5. 若插入節點的P節點是紅色的, 而U節點是黑色或缺少, 且插入節點是其P節點的右子節點, 而P節點是G節點的右子節點, 那麼: 把P節點變成黑色, G節點變為紅色, 然後對G節點做左旋的動作, 最後重新開始調整\
   ![](https://649506553-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M523o38bFiI5-RlHn7V%2F-M523rpyYLd_bz4SsJlN%2F-M523tndyuKzyk629Qeb%2Frbtree-6.png?generation=1587042034281686\&alt=media)
6. 若插入節點的P節點是紅色的, 而U節點是黑色或缺少, 且插入節點是其P節點的右子節點, 而P節點是G節點的左子節點, 那麼: 把當前節點的P節點作為新的當前節點, 對新的當前節點進行左旋, 並且重新開始調整\
   ![](https://649506553-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M523o38bFiI5-RlHn7V%2F-M523rpyYLd_bz4SsJlN%2F-M523tnfDY2MhUoXDKGm%2Frbtree-7.png?generation=1587042034627571\&alt=media)
7. 若插入節點的P節點是紅色的, 而U節點是黑色或缺少, 且插入節點是其P節點的左子節點, 而P節點是G節點的右子節點, 那麼: 把當前節點的P節點作為新的當前節點, 對新的當前節點進行右旋, 最後重新開始調整\
   ![](https://649506553-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M523o38bFiI5-RlHn7V%2F-M523rpyYLd_bz4SsJlN%2F-M523tnhgzoJAOxEIGYg%2Frbtree-8.png?generation=1587042034137597\&alt=media)