目錄
- 紅黑樹定義
- 1. 紅黑樹增加節點程序
- 2. 紅黑樹洗掉節點程序
- 3. 紅黑樹修改&查找節點程序
紅黑樹定義
1. 節點顏色非紅即黑
2. 根節點顏色是黑色
3. 葉子節點（空節點）顏色為黑色
4. 紅色節點的子節點（包括空節點）為黑色
5. 某個節點下的所有路徑，有相同的黑色節點（包括空節點（黑色））
紅黑樹增刪改查演示地址：https://www.cs.usfca.edu/~galles/visualization/RedBlack.html
示例資料：12,1,9,2,3,0,11,7,19,4,15,18,5,14,13,10,16,6,8,17
1. 紅黑樹增加節點程序
增加一個節點，節點顏色默認為紅色，對紅黑樹進行二分查找，對比，
直至整個紅黑樹的葉子節點，確定當前節點插入紅黑樹的初始位置（插入節點
初始位置為整個紅黑樹的葉子節點）
1、判斷插入節點是否為根節點，如果是根節點
把當前節點置為根節點，并把顏色置為黑色
2、判斷父節點的顏色，如果父節點的顏色為黑色
不用處理，不違反紅黑樹的性質
3、父節點是紅色，叔叔節點也是紅色
3.1、將父節點和叔叔節點設定為黑色，祖父節點設定為紅色
3.2、以祖父節點為插入節點，在進行判斷
4、父節點是紅色，叔叔節點是黑色
4.1、左左插入
父節點變成黑色，祖父節點變成紅色，祖父節點右旋
4.2、左右插入
父節左旋，之后父節點就變成了子節點
按照父節點為當前插入的紅色節點，進行左左插入處理
4.3、右右插入
父節點變成黑色，祖父節點變成紅色，祖父節點左旋
4.4、右左插入
父節點右旋，之后父節點變成了子節點
按照父節點為當前插入的紅色節點，進行右右插入處理
演示：
假如需要插入數字3，則查找節點，數字3的初始位置為 數字2 節點的右子樹，如下圖：
根據插入的判斷條件，從第一條依次向下進行判斷，符合4.3：父節點（數字2）是紅色，叔叔節點（數字2 的左子節點空節點）為黑色（空節點）條件，右右的情況，父節點（數字2）變成黑色，祖父節點（數字1）變成紅色，祖父節點（數字1）左旋，得到最終的結果，如下圖：
2. 紅黑樹洗掉節點程序
總結：
洗掉節點時，先看洗掉節點的顏色，再看兄弟節點的顏色，再看侄子節點的顏色（先看遠侄子，再看近侄子）
最后看父節點的顏色
當前節點->兄弟節點->遠侄子節點->近侄子節點->父節點
（補充）洗掉節點分兩種情況，一種是葉子節點，一種不是葉子節點，如果不是葉子節點，進行和子節點值
的交換，直至節點沒有葉子節點，變成洗掉葉子節點
1、洗掉的是葉子節點，并且葉子節點為紅色
直接洗掉，不需要后續處理
2、洗掉的是葉子節點，并且葉子節點為黑色
需要處理
3、洗掉節點下有一個子節點
將當前洗掉的節點和子節點的值進行交換，就變成了洗掉葉子節點
3.1、如果葉子節點是紅色，對應情況1，直接洗掉
3.2、如果葉子節點是黑色，對應情況2，進行后續處理
4、洗掉節點有兩個子節點
將當前節點和后續節點中的一個節點值進行交換，改為洗掉葉子節點
4.1、沒有葉子節點
對應情況1、2
4.2、有一個葉子節點
對應情況3
4.2、有兩個葉子節點
對應情況4
經過上述步驟的轉換，將情況轉換為洗掉葉子節點，其中葉子節點為紅色的已經處理過，現在只需要考慮，
洗掉葉子節點為黑色的情況
5、洗掉的葉子節點為黑色
5.1、洗掉節點的兄弟節點為紅色
洗掉節點為左節點：
將父節點和兄弟節點顏色互換，對父節點進行左旋
洗掉節點為右節點：
將父節點和兄弟節點顏色互換，對父節點進行右旋
5.2、洗掉節點兄弟節點為黑色，遠侄子節點為紅色
洗掉節點為左節點：
這時洗掉節點的遠侄子節點為兄弟節點的右節點
將父節點和兄弟節點顏色對調，并把遠侄子節點變成黑色，對父節點進行左旋
洗掉當前需要洗掉的節點
洗掉節點為右節點：
這時洗掉節點的遠侄子節點為兄弟節點的左節點
將父節點和兄弟節點顏色對調，并把遠侄子節點變成黑色，對父節點進行右旋
洗掉當前需要洗掉的節點
5.3、洗掉節點兄弟節點是黑色，遠侄子節點是紅色
洗掉節點為左節點：
近侄子節點和兄弟節點顏色互換，并將近侄子節點進行右旋
這時候就變成了5.2情況
洗掉節點為右節點：
近侄子節點和兄弟節點顏色互換，將近侄子節點進行左旋
這時候就變成了5.2情況
5.4、父節點是紅色，兄弟節點和兄弟節點的兩個孩子（只能是空節點）都是黑色的情況
將父節點變成黑色，兄弟節點變成紅色
洗掉當前節點
5.5、父節點和兄弟節點及兄弟節點的兩個子節點，都是黑色
將兄弟節點變成紅色，洗掉節點
這樣洗掉節點后，父節點的左右兩個黑色節點數就相等了，但是經過祖父節點的路徑黑色節點
的數就少1個，這個時候，我們再以父節點為起始節點（不用洗掉節點了），繼續根據情況進行
平衡操作，在看是哪種情況，在進行對應的調整，這樣一直向上，直到新的起始節點為根節點
示例：
初始紅黑樹結構如下圖所示：
假如需要洗掉數字4，經過判斷，滿足 5.5、父節點（數字3）和兄弟節點（數字2）及兄弟節點的兩個子節點（空節點），都是黑色，將兄弟節點（數字2）變成紅色，并洗掉當前節點（數字4），如下圖所示：
這時以父節點（數字3）為當前節點進行后續操作（不在洗掉資料），經過判斷，滿足5.2、洗掉節點兄弟節點為黑色，遠侄子節點為紅色，并且洗掉節點為左節點，將父節點（數字9）和兄弟節點（數字14）顏色對調，并把遠侄子節點（數字18）變成黑色，對父節點（數字9）進行左旋，如下圖所示：
至此，洗掉節點（數字4）流程完畢
3. 紅黑樹修改&查找節點程序
修改和查找節點程序相同，列舉查找程序
1、以根節點進行和查找值進行對比
1.1、等于當前值
直接回傳
1.2、小于當前值
以左節點為當前節點進行對比，重復情況1
1.3、大于當前值
以右節點為當前節點進行對比，重復情況1
2、當遍歷到葉子節點，而且沒有找到對應的值，則回傳空
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/395330.html
標籤：其他