紅黑樹的原理以及實現(xiàn)
點擊上方藍(lán)色字體，選擇“標(biāo)星公眾號”
優(yōu)質(zhì)文章，第一時間送達(dá)
作者 | DeusJin
來源 | urlify.cn/VZvqI3
紅黑樹基于二叉查找樹的附加特性
節(jié)點是紅色或黑色。
根節(jié)點是黑色。
每個葉子節(jié)點都是黑色的空節(jié)點（葉子結(jié)點指為空的葉子結(jié)點）。
每個紅色節(jié)點的兩個子節(jié)點都是黑色的（從每個葉子到根的所有路徑上不能有兩個連續(xù)的紅色節(jié)點）。
從任意節(jié)點到其每個葉子的所有路徑都包含相同數(shù)目的黑色節(jié)點。
1. 數(shù)據(jù)結(jié)構(gòu)
class TreeNode{
private Boolean color;
private int val;
private TreeNode left;
private TreeNode right;
private TreeNode parent;
get,set...
}
class RBTree{
public boolean add(int val){...}
public boolean delete(int val){...}
public void display(){...}
}
2. 左旋以及右旋
2.1 左旋
2.2 右旋
3. 插入
新插入的節(jié)點（newNode）為紅色。
按照二分查找樹插入規(guī)則插入。
分情況討論（以下情況基本都是為了保持上文所講的的紅黑樹特性4和特5）
1、若newNode為根節(jié)點，則變?yōu)楹谏迦胪戤叄祷?true。
2、若newNode父節(jié)點為黑色，則插入完畢，返回 true。
3、如下圖所示，若newNode父節(jié)點為紅色，且叔叔節(jié)點存在且為紅色，則父節(jié)點與叔叔節(jié)點變?yōu)楹谏娓腹?jié)點變?yōu)榧t色，newNode = 祖父節(jié)點。
4、如下圖所示，若newNode父節(jié)點為紅色，叔叔節(jié)點不存在或為黑色，且newNode為父節(jié)點右孩子，父節(jié)點為祖父節(jié)點左孩子，則以父節(jié)點為軸左旋，進(jìn)入情況6.
5、如下圖所示，若newNode父節(jié)點為紅色，叔叔節(jié)點不存在或為黑色，且newNode為父節(jié)點左孩子，父節(jié)點為祖父節(jié)點右孩子，則以父節(jié)點為軸右旋，進(jìn)入情況7
6、如下圖，此時以祖父節(jié)點為軸進(jìn)行右旋，將祖父節(jié)點變?yōu)榧t色，newNode變?yōu)楹谏?/span>
7、如下圖，此時以祖父節(jié)點為軸進(jìn)行左旋，將祖父節(jié)點變?yōu)榧t色，newNode變?yōu)楹谏?/span>
4. 刪除
分情況討論（和插入一樣，以下情況基本都是為了保持上文所講的的紅黑樹特性4和特5）
如下圖，如果待刪除節(jié)點B有兩個非空的孩子節(jié)點，轉(zhuǎn)化成待刪除節(jié)點只有右孩子（或沒有孩子）的情況，習(xí)慣性選取待刪除節(jié)點右子樹最小節(jié)點E替換待刪除節(jié)點（只是值替換，顏色不變），并將待刪除節(jié)點變?yōu)镋。
根據(jù)待刪除節(jié)點和唯一子節(jié)點顏色，分情況處理：
自身O是紅色，子節(jié)點N是黑色，直接刪除。
自身O是黑色，子節(jié)點N是紅色，直接刪除并將子節(jié)點N變?yōu)楹谏?/span>
自身O是黑色，子節(jié)點N不存在(不存在即子節(jié)點為空黑色節(jié)點，也可以用來判斷)或也是黑色，較為復(fù)雜，先刪除，再分情況討論：
1、N是根節(jié)點，則不需要調(diào)整。
2、如下圖，N的父親、兄弟、侄子都是黑色，則將兄弟變?yōu)榧t色，父親視作N，進(jìn)行遞歸處理。
3、（存在鏡像）N的兄弟節(jié)點是紅色，且N為父親節(jié)點左兒子，則以父親節(jié)點為軸左旋（否則右旋），并將旋轉(zhuǎn)后N的祖父節(jié)點變?yōu)楹谏琋的父節(jié)點變?yōu)榧t色，進(jìn)入情況4,5或6.
4、N的父親節(jié)點是紅色，兄弟和侄子節(jié)點是黑色，父親節(jié)點變?yōu)楹谏值芄?jié)點變?yōu)榧t色。
5、（存在鏡像）N的父節(jié)點顏色隨意，兄弟節(jié)點為父節(jié)點黑色右孩子，左侄子節(jié)點為紅色，右侄子節(jié)點為黑色，以兄弟節(jié)點為軸進(jìn)行右旋，將旋轉(zhuǎn)后N的兄弟節(jié)點變?yōu)楹谏琋的右侄子節(jié)點變?yōu)榧t色，進(jìn)入情況6
6、（存在鏡像）N的父節(jié)點隨意，兄弟節(jié)點為父節(jié)點的黑色右兒子，右侄子節(jié)點為紅色，以N的父節(jié)點為軸進(jìn)行左旋，左旋后的N的祖父節(jié)點變?yōu)楦腹?jié)點顏色，父節(jié)點變黑，叔叔節(jié)點變黑。
測試
原樹（上右下左）
刪除53
刪除23
刪除54
添加67
代碼：
https://github.com/DEUSJIN/RBTree
粉絲福利：Java從入門到入土學(xué)習(xí)路線圖
??????
??長按上方微信二維碼 2 秒
感謝點贊支持下哈 