Java數據結構之紅黑樹的原理及實現
為什麼要有紅黑樹這種數據結構
我們知道ALV樹是一種嚴格按照定義來實現的平衡二叉查找樹，所以它查找的效率非常穩定，為O(log n),由於其嚴格按照左右子樹高度差不大於1的規則，插入和刪除操作中需要大量且復雜的操作來保持ALV樹的平衡（左旋和右旋），因此ALV樹適用於大量查詢，少量插入和刪除的場景中
那麼假設現在假設有這樣一種場景：大量查詢，大量插入和刪除，現在使用ALV樹就不太合適瞭，因為ALV樹大量的插入和刪除會非常耗時間，那麼我們是否可以降低ALV樹對平衡性的要求從而達到快速的插入和刪除呢？
答案肯定是有的，紅黑樹這種數據結構就應運而生瞭（因為ALV樹是高度平衡的，所以查找起來肯定比紅黑樹快，但是紅黑樹在插入和刪除方面的性能就遠遠不是ALV樹所能比的瞭）
紅黑樹的簡介
紅黑樹是一種特殊的二叉查找樹，每個結點都要儲存位表示結點的顏色，或紅或黑
紅黑樹的特性(紅黑樹必須滿足的5個條件)：
1）每個結點或紅或黑
2）根結點是黑色
3）空葉子結點是黑色
4）如果一個結點是紅色，那麼它的子節點是黑色
5）從任意一個結點出發到空的葉子結點經過的黑結點個數相同
示意圖：(紅黑樹首先是一顆搜索樹，所以左子樹點小於根結點，右子樹大於根節點，等於根結點的按照自己的需要放左邊和右邊都是可以的）（紅黑樹不僅是一顆搜索樹還是一顆非嚴格的平衡樹）
現在有個問題：紅黑樹是怎麼通過上面5條性質保證任意結點到空的葉子結點的所有路徑中，沒有一條路徑會大於其他路徑的兩倍的呢？（換句話說就是它是如何確保任何一個結點的左右子樹的高度差不會超過二者中較低那個的一倍的呢？）
先結合紅黑樹的5個性質分析一下紅黑樹的一些操作，我們可能就明白瞭！
建議學習紅黑樹前瞭解AVL樹
紅黑樹的基本操作之旋轉
紅黑樹的基本操作是添加和刪除，在對紅黑樹進行添加和刪除之後，都會用到旋轉方法，為什麼呢？道理很簡單，因為添加或者刪除紅黑樹中的結點之後，紅黑樹就發生瞭變化，可能不滿足上面的5條性質瞭，這個時候就需要通過旋轉操作來保證它依舊是一棵紅黑樹，旋轉分為左旋和右旋（旋轉操作僅僅隻是用來調節結點的位置的，就是為瞭滿足紅黑樹的性質5）
左旋
左旋是將X的右子樹繞X逆時針旋轉，使得X的右子樹成為X的父親，同時修改相關結點的引用，旋轉之後，要求二叉查找樹的屬性依然滿足
右旋
右旋是將X的左子樹繞X順時針旋轉，使得X的左子樹成為X的父親，同時註意修改相關結點的引用，旋轉之後要求仍然滿足搜索樹的屬性
紅黑樹之添加元素
添加操作宏觀過程：首先將紅黑樹當作一顆查找樹一樣將結點插入，然後將結點著為紅色，最後通過旋轉和重新著色的方法使之重新成為紅黑樹
將新加入的結點塗成紅色的原因：
1）不違背紅黑樹的性質5：從任意一個結點出發到空葉子結點，經過的黑色結點個數相同
2）按照紅黑樹的性質4我們知道紅黑樹中黑結點的個數至少是紅結點個數的兩倍，所以新增結點的父親結點是黑結點的概率比較大，如果新增結點的父節點為黑色，那麼此時不需要再去進行任何調整操作，因此效率很高，所以新結點應該塗成紅色
少違背一條性質，意味著我們後續的旋轉和重新著色操作會簡單很多
現在我們來看看新增一個紅色的結點會違背紅黑樹的5條性質中的哪些？
1）每個結點或紅或黑
2）根結點是黑色
3）空葉子結點是黑色
4）如果一個結點是紅色，那麼它的子節點是黑色
5）從任意一個結點出發到空的葉子結點經過的黑結點個數相同
1.顯然沒有違背
2.根據查找樹的特定，插入操作不好改變根結點，所以也沒有違背
3.插入的肯定不是空葉子結點，所以也沒有違背
4.有可能違背！！！
5.插入結點塗成紅色就是為瞭不違背第5條性質
現在我們來分析一下新增的結點（紅色）插入之後可能面臨的幾種情況，以及他們的處理措施
1.插入的結點為根結點
將新插入的紅色結點變成黑色結點，滿足根結點為黑色結點的要求！
2.父親結點為黑色結點
這個時候不需要進行任何調整操作，此時的樹仍然是一顆標準的紅黑樹
3.父親結點為紅色結點的情況下，叔叔結點為紅色結點（不用考慮左右）
解決方案：將叔叔和父親結點改為黑色，爺爺結點改為紅色，然後又將爺爺結點當作插入結點看待，一直進行上面的操作，直到當前結點為根結點，然後將根結點變成黑色
插入一個125的結點：
現在125結點和130結點都是紅色的，顯然違背瞭規則4，所以將新插入結點的父親130結點和插入結點的叔叔結點150變成黑色，並將新插入結點的爺爺結點140變成紅色，圖如下：
然後又將140結點當作新插入結點處理（因為140結點和新插入結點面臨的情況都是一樣的：和父親結點都是紅色），也就是做如下處理：將140結點的父親結點120和140的叔叔結點60變成黑色結點，將140結點的爺爺結點變成紅色，因為遍歷到瞭根結點，要滿足根結點是黑色的性質要求，所以又將140的爺爺結點也就是根結點變成黑色，圖如下：
到這裡，為新插入結點125所做的某些結點重新著色的操作就完成瞭，現在該樹是標準的紅黑樹瞭！
4.新插入的結點的父親結點為紅色，其叔叔結點為黑色
1）父親結點為爺爺結點的左孩子，新插入結點為父節點的左孩子（左左情況）
2）父親結點為爺爺結點的右孩子，新插入結點為父親結點的右孩子（右右情況）
上述兩種情況都是同一個處理辦法
比如下圖，新插入結點為25，其父親結點30為紅色，其叔叔結點為空黑色葉子結點，且新插入結點和其父節點都是左孩子：
我們將其父親結點和爺爺結點顏色互換，然後針對爺爺結點進行一次左旋，圖如下：
現在這顆樹完全滿足紅黑樹的5個性質瞭（最好自己對照5個性質看一下）
現在又一個問題，我們為什麼要進行旋轉？
假設我們隻將新增結點的父親結點和其爺爺結點的顏色互換瞭，圖如下：
我們發現上述兩條到葉子結點的路徑經過的黑色結點數量不一樣！！！，所以它不滿足紅黑樹的第5條性質，所以這就是我們旋轉的意義所在！！！（因為無論你這麼旋轉都沒有改變結點顏色，改變的是結點的位置，而這位置改變剛好能使得樹滿足紅黑樹的第5條性質！）
5.新插入的結點的父親結點是紅色，其叔叔結點是黑色
1）插入結點是右結點，父節點是左結點
2）插入結點是左結點，父親結點是右結點
上述兩種情況都是同一個處理辦法
比如下圖，新插入結點是126，其父結點125為紅色，其叔叔結點為空的黑色結點，而且插入結點是右結點，父結點是左結點
我們將父親結點125看作當前結點進行左旋，旋轉結果如下：
現在我們的當前結點是125，現在125的處境和上面的情況4是一樣的（父節點為紅，叔叔結點為黑，插入結點為左結點，父親結點也為左孩子）現在我們繼續按照情況4的處理辦法處理上述情況（措施和情況4一樣，父親結點和爺爺結點互換顏色，然後針對爺爺結點進行左旋），處理後情況如下：
現在樹就是一顆標準的紅黑樹瞭！
我們現在總結一下插入結點面臨的幾種情況以及采取的措施：
1.樹為空，插入的結點為根結點
直接將插入的結點變成黑色
2.父親結點為黑色結點
不需要任何操作
3.父親結點為紅色結點的情況下：
3.1 叔叔結點也為紅色結點
將叔叔和父親結點改為黑色，爺爺結點改為紅色，未完，然後又將爺爺結點當作插入結點看待，一直進行上
面的操作，直到當前結點為根結點，然後將根結點變成黑色
3.2 叔叔結點為黑色結點的情況下：
3.2.1 （父親結點為左孩子，插入結點也為左孩子）||（父親結點為右孩子，插入結點也為右孩子）
將父親結點和爺爺結點的顏色互換，然後針對爺爺結點進行一次左旋
3.2.2 （父親結點為左孩子，插入結點為右孩子）||（父親結點為右孩子，插入結點為左孩子）
針對父結點進行左旋，此時左旋後的情況必定是3.2.1的情況，然後按照3.2.1的情況處理
現在我們來推導一下，為什麼插入的情況隻有上面這些：
1.爺爺結點為紅色結點的情況下，父親結點隻能為黑色（紅黑樹的性質4），處理操作：上面情況2
2.爺爺結點為黑色的情況下，父親結點和叔叔結點：可以為紅色，也可以為黑色
2.1 父親結點為黑，叔叔結點為黑：處理操作：上面情況2
2.2 父親結點為黑，叔叔結點為紅：處理操作：上面情況2
2.3 父親結點為紅，叔叔結點為紅：處理操作：上面情況3.1
（上面3種情況都是不用考慮左右的）
2.4 父親結點為紅，叔叔結點為黑：
- 2.4.1 父親結點為左孩子，叔叔結點為左孩子：處理操作：上面情況3.2.1
- 2.4.2 父親結點為右孩子，叔叔結點為右孩子：處理操作：上面情況3.2.1
- 2.4.3 父親結點為左孩子，插入結點為右孩子：處理操作：上面情況3.2.2
- 2.4.4 父親結點為右孩子，插入結點為左孩子：處理操作：上面情況3.2.2
總結：可以發現我們沒有遺漏任何情況，所有可能面臨的情況我們都處理瞭
紅黑樹之刪除結點
先說一個刪除結點的過程原理：首先將紅黑樹當作一個二叉查找樹，將該結點從二叉查找樹種刪除，然後通過一些列重新著色操作等一系列措施來修正該樹，使之重新成為一顆紅黑樹, 刪除結點其實很容易，難的是如何使得刪除結點後的樹重新成為一個紅黑樹
我們可以根據刪除結點N的兒子個數分為三種情況：
刪除結點沒有兒子
刪除結點有1個兒子
刪除結點有2個兒子
接下來我們又可以對以上三種情況繼續進行細分:
一.刪除結點沒有兒子的情況：
- 1）刪除結點為紅色
- 2）刪除結點為黑色，其兄弟結點沒有兒子
- 3）刪除結點為黑色，其兄弟結點有一個孩子不空，並且該孩子為右孩子
- 4）刪除結點為黑色，其兄弟結點有一個孩子不空，並且該孩子為左孩子
- 5）刪除結點為黑色，其兄弟結點有兩個孩子，而且兄弟結點為紅色
- 6）刪除結點為黑色，其兄弟結點有兩個孩子，而且兄弟結點為黑色
二. 刪除結點隻有一個兒子的情況：
- 1）刪除結點為黑色，其唯一的兒子結點為紅色（必定是紅色，要不然不符合紅黑樹的第5條性質）
- 2）刪除結點為紅色，其兒子結點隻能為黑：(紅黑樹中不存在這種情況，要不然無法滿足紅黑樹第5條性質)
三. 刪除結點有兩個兒子的情況： 找到刪除結點的右子樹中最左的結點，兩兩值交換，然後刪除結點的情況就變成瞭上面兩種情況中的一種瞭
現在我們就具體分析一下面臨不同的操作到達該這麼操作：
刪除結點沒有兒子的情況
1）刪除結點為紅色
直接刪除，比如下圖，想要刪除130結點
直接刪除130結點，結果圖如下：
因為刪除的是紅色結點，不會影響紅黑樹第5條性質，所以可以直接刪除
2）刪除結點為黑色，其兄弟結點沒有兒子
這種情況下其兄弟結點也肯定是黑色的（要滿足紅黑樹第5條性質），假設現在要刪除的是150這個結點，原圖如下：
先刪除結點150，然後將兄弟結點126變成紅色，父親結點140變成黑色，結果如下：
這樣做的目的是為瞭滿足紅黑樹的第5條性質，要不然根到最右邊的葉子結點經過的黑色結點隻有3個，而其他路徑有4個
3）刪除結點為黑色，其兄弟結點有一個孩子不空，並且該孩子和兄弟結點在同一邊（同為左子樹或者同為右子樹）
假設現在要刪除的結點為110，其兄弟結點140隻有一個孩子150，而且都是右子樹，滿足上述條件，原圖如下：
先把需要刪除的結點110刪除，然後這個時候需要交換兄弟結點140和父親結點120的顏色，並且把父親結點120塗成黑色，把兄弟結點的子節點150塗成黑色
如果兄弟結點和兄弟結點的兒子都在右子樹的話：對父親結點進行左旋如果兄弟結點和兄弟結點的兒子都在左子樹的話：對父親結點進行右旋
上圖是第一種情況，所以對父結點120進行左旋，結果如下：
通過對某些結點重新著色和旋轉，又將該樹變成瞭一個標準的紅黑樹瞭
4）刪除結點為黑色，其兄弟結點有一個孩子不空，並且該孩子和兄弟結點不在同一邊（右左或者左右的情況）
假設我們現在要刪除的結點是80結點，其兄弟結點隻有一個兒子，而且兄弟結點和兄弟結點的兒子是左右的情況（兄弟結點為左結點，兄弟結點的兒子為右結點），符合上述要求，原圖如下：
現在我們先將需要刪除的80結點刪除，然後將兄弟結點和兄弟結點的兒子結點顏色互換
如果兄弟結點是左子樹，兄弟結點的兒子結點是右子樹：對兄弟結點進行左旋
如果兄弟結點是右子樹，兄弟結點的兒子結點是左子樹：對兄弟結點進行右旋
上圖的情況是進行左旋，也就是對兄弟結點30進行左旋，結果如下圖：
註意！！，現在還沒有結束變換，我們發現變換之後的紅黑樹和情況3中的情況很相似，兄弟結點50和兄弟結點的子節點30處在同一邊，我們可以按照情況3的處理辦法進行處理：
交換兄弟結點50和父親結點60的顏色，把父親結點60和兄弟結點的子節點30塗成黑色
如果兄弟結點和兄弟結點的兒子都在右子樹的話：對父親結點進行左旋如果兄弟結點和兄弟結點的兒子都在左子樹的話，對父親結點進行右旋
上圖的情況是第2中，所以對父親結點60進行右旋，結果如下：
5)刪除結點為黑色，其兄弟結點有兩個孩子，兄弟結點為黑色而且兩個孩子結點也為黑色
現在我們假設要刪除的結點是130結點，其兄弟結點有兩個孩子（可以把空的葉子結點看成黑色的兒子結點），而且兄弟結點和兄弟結點的兒子結點都是黑色，符合上述情況，原圖如下：
先直接刪除需要刪除的結點130，然後將父親結點140和兄弟結點150顏色互換即可，結果如下：
6)刪除結點為黑色，其兄弟結點有兩個孩子，而且兄弟結點為紅色
假設我們要刪除的結點是110，其兄弟結點140為紅色而且有兩個孩子，原圖如下：
我們先交換兄弟結點140和父親結點120的顏色
1.被刪除的元素為左子樹：對父親結點左旋
2.被刪除的元素為右子樹：對父親結點右旋
上圖的情況是第一種情況，所以我們對父親結點140進行左旋，按照上面操作之後（未完），結果如下：
我們發現完成上述操作之後樹還不是一個標準的紅黑樹（到葉子結點的一條路徑黑色結點隻有3個，而其他的路徑有4個），我們發現現在紅黑樹的情況又和情況5的很像，所以我們按照情況5的做法繼續：
我們要需要刪除的結點還沒有被刪除（我特意留到最後刪除的，就是為瞭在這裡表示父親結點是誰的父親結點…）,現在我們將父親結點120和兄弟結點130的顏色互換即可，結果如下：
我們現在對刪除結點沒有兒子結點的6種刪除情況進行一下總結：
刪除結點沒有兒子結點：
1）刪除結點為紅色：
直接刪除
2）刪除結點為黑色，其兄弟結點沒有兒子：
兄弟結點變紅，父親結點變黑，然後將父親結點當作當前結點按照這幾種情形處理，直到當前結點為根結點
3）刪除結點為黑色，其兄弟結點有一個孩子不空，並且該孩子和兄弟結點在同一邊（同為左子樹或者同為右子樹）：
1.不管是括號中那種情況，先交換兄弟結點和父親結點的顏色，並且把父親結點和兄弟結點的子結點塗成黑色
2.1如果兄弟結點和兄弟結點的兒子都在右子樹的話：對父親結點進行左旋
2.2如果兄弟結點和兄弟結點的兒子都在左子樹的話：對父親結點進行右旋
4）刪除結點為黑色，其兄弟結點有一個孩子不空，並且該孩子和兄弟結點不在同一邊（右左或者左右的情況）：
1.先將兄弟結點和兄弟結點的兒子結點顏色互換
2.1如果兄弟結點是左子樹，兄弟結點的兒子結點是右子樹：對兄弟結點進行左旋
2.2如果兄弟結點是右子樹，兄弟結點的兒子結點是左子樹：對兄弟結點進行右旋
3.將後續變換按照第3條處理
5)刪除結點為黑色，其兄弟結點有兩個孩子，兄弟結點為黑色而且兩個孩子結點也為黑色：
1.將父親結點和兄弟結點顏色互換
6）刪除結點為黑色，其兄弟結點有兩個孩子，而且兄弟結點為紅色：
1.將兄弟結點和父親結點的顏色互換
2.1 被刪除的元素為左子樹：對父親結點左旋
2.2 被刪除的元素為右子樹：對父親結點右旋
3.將後續變換按照第5條進行處理
以上6種情況討論的都是刪除結點沒有兒子的情況（空葉子結點不算兒子結點）
現在我們來看看刪除結點僅有一個兒子結點的情況！
刪除結點僅有一個兒子結點的情況
1）刪除結點為黑色，兒子結點無論左右都可以
比如我們要刪除的結點是120結點，刪除結點為黑色，唯一的兒子結點130為紅色（必須是紅色，不然違背紅黑樹第5條性質）原圖如下：
我們將需要刪除的結點120刪除，然後將子節點130塗黑放到被刪除結點120的位置，結果如下：
2）刪除結點為紅色：其兒子結點隻能為黑，紅黑樹中不存在這種情況，要不然無法滿足紅黑樹第5條性質
總結一下刪除結點隻有一個兒子的情況：
1）刪除結點為黑色，兒子結點無論左右都可以(將兒子結點塗成黑色放到被刪除結點的位置)
下面我們來看看刪除結點有兩個兒子結點的情況
刪除結點有兩個兒子結點
找到刪除結點的右子樹中最左的結點，兩兩值交換，然後刪除結點的情況就變成瞭上面兩種情況中的一種瞭
刪除結點隻有一個兒子的情況
刪除結點沒有兒子的情況
比如下圖
假設要刪除的結點是120，先找到結點120右子樹中最左的結點125，交換兩者的值，圖如下：
現在120仍然是要刪除的結點，我們發現刪除結點120沒有一個兒子，而且其兄弟結點也沒有兒子，那麼其對應的情況為：
2）刪除結點為黑色，其兄弟結點沒有兒子：兄弟結點變紅，父親結點變黑
經過上面的變形，結果如下：
經過變換，該樹變成瞭一顆標準的紅黑樹
所以當刪除結點右兩個兒子結點的時候，我們隻需要按照搜索二叉樹的刪除方法替換刪除值，這樣就可以將情況變成刪除結點沒有兒子結點或者1個兒子結點的情況處理瞭
紅黑樹動態可視化網站
https://www.cs.usfca.edu/~galles/visualization/RedBlack.html
紅黑樹參考代碼
package com.tree.rbtree;
/**
* Java 語言: 紅黑樹
*
* @author huanmin
*/
public class RBTree<T extends Comparable<T>> {
private RBTNode<T> mRoot; // 根結點
private static final boolean RED = false;
private static final boolean BLACK = true;
public class RBTNode<T extends Comparable<T>> {
boolean color; // 顏色
T key; // 關鍵字(鍵值)
RBTNode<T> left; // 左孩子
RBTNode<T> right; // 右孩子
RBTNode<T> parent; // 父結點
public RBTNode(T key, boolean color, RBTNode<T> parent, RBTNode<T> left, RBTNode<T> right) {
this.key = key;
this.color = color;
this.parent = parent;
this.left = left;
this.right = right;
}
public T getKey() {
return key;
}
@Override
public String toString() {
return ""+key+(this.color==RED?"(R)":"B");
}
}
public RBTree() {
mRoot=null;
}
private RBTNode<T> parentOf(RBTNode<T> node) {
return node!=null ? node.parent : null;
}
private boolean colorOf(RBTNode<T> node) {
return node!=null ? node.color : BLACK;
}
private boolean isRed(RBTNode<T> node) {
return ((node!=null)&&(node.color==RED)) ? true : false;
}
private boolean isBlack(RBTNode<T> node) {
return !isRed(node);
}
private void setBlack(RBTNode<T> node) {
if (node!=null) {
node.color = BLACK;
}
}
private void setRed(RBTNode<T> node) {
if (node!=null) {
node.color = RED;
}
}
private void setParent(RBTNode<T> node, RBTNode<T> parent) {
if (node!=null) {
node.parent = parent;
}
}
private void setColor(RBTNode<T> node, boolean color) {
if (node!=null) {
node.color = color;
}
}
/*
* 前序遍歷"紅黑樹"
*/
private void preOrder(RBTNode<T> tree) {
if(tree != null) {
System.out.print(tree.key+" ");
preOrder(tree.left);
preOrder(tree.right);
}
}
public void preOrder() {
preOrder(mRoot);
}
/*
* 中序遍歷"紅黑樹"
*/
private void inOrder(RBTNode<T> tree) {
if(tree != null) {
inOrder(tree.left);
System.out.print(tree.key+" ");
inOrder(tree.right);
}
}
public void inOrder() {
inOrder(mRoot);
}
/*
* 後序遍歷"紅黑樹"
*/
private void postOrder(RBTNode<T> tree) {
if(tree != null)
{
postOrder(tree.left);
postOrder(tree.right);
System.out.print(tree.key+" ");
}
}
public void postOrder() {
postOrder(mRoot);
}
/*
* (遞歸實現)查找"紅黑樹x"中鍵值為key的節點
*/
private RBTNode<T> search(RBTNode<T> x, T key) {
if (x==null) {
return x;
}
int cmp = key.compareTo(x.key);
if (cmp < 0) {
return search(x.left, key);
} else if (cmp > 0) {
return search(x.right, key);
} else {
return x;
}
}
public RBTNode<T> search(T key) {
return search(mRoot, key);
}
/*
* (非遞歸實現)查找"紅黑樹x"中鍵值為key的節點
*/
private RBTNode<T> iterativeSearch(RBTNode<T> x, T key) {
while (x!=null) {
int cmp = key.compareTo(x.key);
if (cmp < 0) {
x = x.left;
} else if (cmp > 0) {
x = x.right;
} else {
return x;
}
}
return x;
}
public RBTNode<T> iterativeSearch(T key) {
return iterativeSearch(mRoot, key);
}
/*
* 查找最小結點：返回tree為根結點的紅黑樹的最小結點。
*/
private RBTNode<T> minimum(RBTNode<T> tree) {
if (tree == null) {
return null;
}
while(tree.left != null) {
tree = tree.left;
}
return tree;
}
public T minimum() {
RBTNode<T> p = minimum(mRoot);
if (p != null) {
return p.key;
}
return null;
}
/*
* 查找最大結點：返回tree為根結點的紅黑樹的最大結點。
*/
private RBTNode<T> maximum(RBTNode<T> tree) {
if (tree == null) {
return null;
}
while(tree.right != null) {
tree = tree.right;
}
return tree;
}
public T maximum() {
RBTNode<T> p = maximum(mRoot);
if (p != null) {
return p.key;
}
return null;
}
/*
* 找結點(x)的後繼結點。即，查找"紅黑樹中數據值大於該結點"的"最小結點"。
*/
public RBTNode<T> successor(RBTNode<T> x) {
// 如果x存在右孩子，則"x的後繼結點"為 "以其右孩子為根的子樹的最小結點"。
if (x.right != null) {
return minimum(x.right);
}
// 如果x沒有右孩子。則x有以下兩種可能：
// (01) x是"一個左孩子"，則"x的後繼結點"為 "它的父結點"。
// (02) x是"一個右孩子"，則查找"x的最低的父結點，並且該父結點要具有左孩子"，找到的這個"最低的父結點"就是"x的後繼結點"。
RBTNode<T> y = x.parent;
while ((y!=null) && (x==y.right)) {
x = y;
y = y.parent;
}
return y;
}
/*
* 找結點(x)的前驅結點。即，查找"紅黑樹中數據值小於該結點"的"最大結點"。
*/
public RBTNode<T> predecessor(RBTNode<T> x) {
// 如果x存在左孩子，則"x的前驅結點"為 "以其左孩子為根的子樹的最大結點"。
if (x.left != null) {
return maximum(x.left);
}
// 如果x沒有左孩子。則x有以下兩種可能：
// (01) x是"一個右孩子"，則"x的前驅結點"為 "它的父結點"。
// (01) x是"一個左孩子"，則查找"x的最低的父結點，並且該父結點要具有右孩子"，找到的這個"最低的父結點"就是"x的前驅結點"。
RBTNode<T> y = x.parent;
while ((y!=null) && (x==y.left)) {
x = y;
y = y.parent;
}
return y;
}
/*
* 對紅黑樹的節點(x)進行左旋轉
*
* 左旋示意圖(對節點x進行左旋)：
* px px
* / /
* x y
* / \ --(左旋)-. / \ #
* lx y x ry
* / \ / \
* ly ry lx ly
*
*
*/
private void leftRotate(RBTNode<T> x) {
// 設置x的右孩子為y
RBTNode<T> y = x.right;
// 將 “y的左孩子” 設為 “x的右孩子”；
// 如果y的左孩子非空，將 “x” 設為 “y的左孩子的父親”
x.right = y.left;
if (y.left != null) {
y.left.parent = x;
}
// 將 “x的父親” 設為 “y的父親”
y.parent = x.parent;
if (x.parent == null) {
this.mRoot = y; // 如果 “x的父親” 是空節點，則將y設為根節點
} else {
if (x.parent.left == x) {
x.parent.left = y; // 如果 x是它父節點的左孩子，則將y設為“x的父節點的左孩子”
} else {
x.parent.right = y; // 如果 x是它父節點的左孩子，則將y設為“x的父節點的左孩子”
}
}
// 將 “x” 設為 “y的左孩子”
y.left = x;
// 將 “x的父節點” 設為 “y”
x.parent = y;
}
/*
* 對紅黑樹的節點(y)進行右旋轉
*
* 右旋示意圖(對節點y進行左旋)：
* py py
* / /
* y x
* / \ --(右旋)-. / \ #
* x ry lx y
* / \ / \ #
* lx rx rx ry
*
*/
private void rightRotate(RBTNode<T> y) {
// 設置x是當前節點的左孩子。
RBTNode<T> x = y.left;
// 將 “x的右孩子” 設為 “y的左孩子”；
// 如果"x的右孩子"不為空的話，將 “y” 設為 “x的右孩子的父親”
y.left = x.right;
if (x.right != null) {
x.right.parent = y;
}
// 將 “y的父親” 設為 “x的父親”
x.parent = y.parent;
if (y.parent == null) {
this.mRoot = x; // 如果 “y的父親” 是空節點，則將x設為根節點
} else {
if (y == y.parent.right) {
y.parent.right = x; // 如果 y是它父節點的右孩子，則將x設為“y的父節點的右孩子”
} else {
y.parent.left = x; // (y是它父節點的左孩子) 將x設為“x的父節點的左孩子”
}
}
// 將 “y” 設為 “x的右孩子”
x.right = y;
// 將 “y的父節點” 設為 “x”
y.parent = x;
}
/*
* 紅黑樹插入修正函數
*
* 在向紅黑樹中插入節點之後(失去平衡)，再調用該函數；
* 目的是將它重新塑造成一顆紅黑樹。
*
* 參數說明：
* node 插入的結點 // 對應《算法導論》中的z
*/
private void insertFixUp(RBTNode<T> node) {
RBTNode<T> parent, gparent;
// 若“父節點存在，並且父節點的顏色是紅色”
while (((parent = parentOf(node))!=null) && isRed(parent)) {
gparent = parentOf(parent);
//若“父節點”是“祖父節點的左孩子”
if (parent == gparent.left) {
// Case 1條件：叔叔節點是紅色
RBTNode<T> uncle = gparent.right;
if ((uncle!=null) && isRed(uncle)) {
setBlack(uncle);
setBlack(parent);
setRed(gparent);
node = gparent;
continue;
}
// Case 2條件：叔叔是黑色，且當前節點是右孩子
if (parent.right == node) {
RBTNode<T> tmp;
leftRotate(parent);
tmp = parent;
parent = node;
node = tmp;
}
// Case 3條件：叔叔是黑色，且當前節點是左孩子。
setBlack(parent);
setRed(gparent);
rightRotate(gparent);
} else { //若“z的父節點”是“z的祖父節點的右孩子”
// Case 1條件：叔叔節點是紅色
RBTNode<T> uncle = gparent.left;
if ((uncle!=null) && isRed(uncle)) {
setBlack(uncle);
setBlack(parent);
setRed(gparent);
node = gparent;
continue;
}
// Case 2條件：叔叔是黑色，且當前節點是左孩子
if (parent.left == node) {
RBTNode<T> tmp;
rightRotate(parent);
tmp = parent;
parent = node;
node = tmp;
}
// Case 3條件：叔叔是黑色，且當前節點是右孩子。
setBlack(parent);
setRed(gparent);
leftRotate(gparent);
}
}
// 將根節點設為黑色
setBlack(this.mRoot);
}
/*
* 將結點插入到紅黑樹中
*
* 參數說明：
* node 插入的結點 // 對應《算法導論》中的node
*/
private void insert(RBTNode<T> node) {
int cmp;
RBTNode<T> y = null;
RBTNode<T> x = this.mRoot;
// 1. 將紅黑樹當作一顆二叉查找樹，將節點添加到二叉查找樹中。
while (x != null) {
y = x;
cmp = node.key.compareTo(x.key);
if (cmp < 0) {
x = x.left;
} else {
x = x.right;
}
}
node.parent = y;
if (y!=null) {
cmp = node.key.compareTo(y.key);
if (cmp < 0) {
y.left = node;
} else {
y.right = node;
}
} else {
this.mRoot = node;
}
// 2. 設置節點的顏色為紅色
node.color = RED;
// 3. 將它重新修正為一顆二叉查找樹
insertFixUp(node);
}
/*
* 新建結點(key)，並將其插入到紅黑樹中
*
* 參數說明：
* key 插入結點的鍵值
*/
public void insert(T key) {
RBTNode<T> node=new RBTNode<T>(key,BLACK,null,null,null);
// 如果新建結點失敗，則返回。
if (node != null) {
insert(node);
}
}
/*
* 紅黑樹刪除修正函數
*
* 在從紅黑樹中刪除插入節點之後(紅黑樹失去平衡)，再調用該函數；
* 目的是將它重新塑造成一顆紅黑樹。
*
* 參數說明：
* node 待修正的節點
*/
private void removeFixUp(RBTNode<T> node, RBTNode<T> parent) {
RBTNode<T> other;
while ((node==null || isBlack(node)) && (node != this.mRoot)) {
if (parent.left == node) {
other = parent.right;
if (isRed(other)) {
// Case 1: x的兄弟w是紅色的
setBlack(other);
setRed(parent);
leftRotate(parent);
other = parent.right;
}
if ((other.left==null || isBlack(other.left)) &&
(other.right==null || isBlack(other.right))) {
// Case 2: x的兄弟w是黑色，且w的倆個孩子也都是黑色的
setRed(other);
node = parent;
parent = parentOf(node);
} else {
if (other.right==null || isBlack(other.right)) {
// Case 3: x的兄弟w是黑色的，並且w的左孩子是紅色，右孩子為黑色。
setBlack(other.left);
setRed(other);
rightRotate(other);
other = parent.right;
}
// Case 4: x的兄弟w是黑色的；並且w的右孩子是紅色的，左孩子任意顏色。
setColor(other, colorOf(parent));
setBlack(parent);
setBlack(other.right);
leftRotate(parent);
node = this.mRoot;
break;
}
} else {
other = parent.left;
if (isRed(other)) {
// Case 1: x的兄弟w是紅色的
setBlack(other);
setRed(parent);
rightRotate(parent);
other = parent.left;
}
if ((other.left==null || isBlack(other.left)) &&
(other.right==null || isBlack(other.right))) {
// Case 2: x的兄弟w是黑色，且w的倆個孩子也都是黑色的
setRed(other);
node = parent;
parent = parentOf(node);
} else {
if (other.left==null || isBlack(other.left)) {
// Case 3: x的兄弟w是黑色的，並且w的左孩子是紅色，右孩子為黑色。
setBlack(other.right);
setRed(other);
leftRotate(other);
other = parent.left;
}
// Case 4: x的兄弟w是黑色的；並且w的右孩子是紅色的，左孩子任意顏色。
setColor(other, colorOf(parent));
setBlack(parent);
setBlack(other.left);
rightRotate(parent);
node = this.mRoot;
break;
}
}
}
if (node!=null) {
setBlack(node);
}
}
/*
* 刪除結點(node)，並返回被刪除的結點
*
* 參數說明：
* node 刪除的結點
*/
private void
remove(RBTNode<T> node) {
RBTNode<T> child, parent;
boolean color;
// 被刪除節點的"左右孩子都不為空"的情況。
if ( (node.left!=null) && (node.right!=null) ) {
// 被刪節點的後繼節點。(稱為"取代節點")
// 用它來取代"被刪節點"的位置，然後再將"被刪節點"去掉。
RBTNode<T> replace = node;
// 獲取後繼節點
replace = replace.right;
while (replace.left != null) {
replace = replace.left;
}
// "node節點"不是根節點(隻有根節點不存在父節點)
if (parentOf(node)!=null) {
if (parentOf(node).left == node) {
parentOf(node).left = replace;
} else {
parentOf(node).right = replace;
}
} else {
// "node節點"是根節點，更新根節點。
this.mRoot = replace;
}
// child是"取代節點"的右孩子，也是需要"調整的節點"。
// "取代節點"肯定不存在左孩子！因為它是一個後繼節點。
child = replace.right;
parent = parentOf(replace);
// 保存"取代節點"的顏色
color = colorOf(replace);
// "被刪除節點"是"它的後繼節點的父節點"
if (parent == node) {
parent = replace;
} else {
// child不為空
if (child!=null) {
setParent(child, parent);
}
parent.left = child;
replace.right = node.right;
setParent(node.right, replace);
}
replace.parent = node.parent;
replace.color = node.color;
replace.left = node.left;
node.left.parent = replace;
if (color == BLACK) {
removeFixUp(child, parent);
}
node = null;
return ;
}
if (node.left !=null) {
child = node.left;
} else {
child = node.right;
}
parent = node.parent;
// 保存"取代節點"的顏色
color = node.color;
if (child!=null) {
child.parent = parent;
}
// "node節點"不是根節點
if (parent!=null) {
if (parent.left == node) {
parent.left = child;
} else {
parent.right = child;
}
} else {
this.mRoot = child;
}
if (color == BLACK) {
removeFixUp(child, parent);
}
node = null;
}
/*
* 刪除結點(z)，並返回被刪除的結點
*
* 參數說明：
* tree 紅黑樹的根結點
* z 刪除的結點
*/
public void remove(T key) {
RBTNode<T> node;
if ((node = search(mRoot, key)) != null) {
remove(node);
}
}
/*
* 銷毀紅黑樹
*/
private void destroy(RBTNode<T> tree) {
if (tree==null) {
return ;
}
if (tree.left != null) {
destroy(tree.left);
}
if (tree.right != null) {
destroy(tree.right);
}
tree=null;
}
public void clear() {
destroy(mRoot);
mRoot = null;
}
/*
* 打印"紅黑樹"
*
* key -- 節點的鍵值
* direction -- 0，表示該節點是根節點;
* -1，表示該節點是它的父結點的左孩子;
* 1，表示該節點是它的父結點的右孩子。
*/
private void print(RBTNode<T> tree, T key, int direction) {
if(tree != null) {
if(direction==0) // tree是根節點
{
System.out.printf("%2d(B) is root\n", tree.key);
} else // tree是分支節點
{
System.out.printf("%2d(%s) is %2d's %6s child\n", tree.key, isRed(tree)?"R":"B", key, direction==1?"right" : "left");
}
print(tree.left, tree.key, -1);
print(tree.right,tree.key, 1);
}
}
public void print() {
if (mRoot != null) {
print(mRoot, mRoot.key, 0);
}
}
}
以上就是Java數據結構之紅黑樹的原理及實現的詳細內容，更多關於Java紅黑樹的資料請關註WalkonNet其它相關文章！