<em>Mac</em>Book项目 2009年学校开始实施<em>Mac</em>Book项目,所有师生配备一本<em>Mac</em>Book,并同步更新了校园无线网络。学校每周进行电脑技术更新,每月发送技术支持资料,极大改变了教学及学习方式。因此2011
2021-06-01 09:32:01
Java資料結構之紅黑樹的原理及實現
2022-09-02 18:02:02
為什麼要有紅黑樹這種資料結構
我們知道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 rootn", tree.key);
} else // tree是分支節點
{
System.out.printf("%2d(%s) is %2d's %6s childn", 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紅黑樹的資料請關注it145.com其它相關文章！
相關文章
-
黑科技的輕簡出行，告別「電量焦慮症」：Anker氮化鎵超能充系列
综合看Anker超能充系列的性价比很高，并且与不仅和iPhone12/苹果<em>Mac</em>Book很配，而且适合多设备充电需求的日常使用或差旅场景，不管是安卓还是Switch同样也能用得上它，希望这次分享能给准备购入充电器的小伙伴们有所
2021-06-01 09:31:42
-
吳亦凡廠牌首秀，L4WUDU居然忘詞了，Rapper和明星比還是有差距！
除了L4WUDU与吴亦凡已经多次共事，成为了明面上的厂牌成员，吴亦凡还曾带领20XXCLUB全队参加2020年的一场音乐节，这也是20XXCLUB首次全员合照，王嗣尧Turbo、陈彦希Regi、<em>Mac</em> Ova Seas、林渝植等人全部出场。然而让
2021-06-01 09:31:34
-
IPFS、Chia、Bzz和ICP挖礦該怎麼選？哪一個更有優勢？
目前应用IPFS的机构：1 谷歌<em>浏览器</em>支持IPFS分布式协议 2 万维网 (历史档案博物馆)数据库 3 火狐<em>浏览器</em>支持 IPFS分布式协议 4 EOS 等数字货币数据存储 5 美国国会图书馆，历史资料永久保存在 IPFS 6 加
2021-06-01 09:31:24
-
有哪些事是買了雪佛蘭後才知道的？美事偷著樂，開拓者車主隨聊
开拓者的车机是兼容苹果和<em>安卓</em>，虽然我不怎么用，但确实兼顾了我家人的很多需求：副驾的门板还配有解锁开关，有的时候老婆开车，下车的时候偶尔会忘记解锁，我在副驾驶可以自己开门：第二排设计很好，不仅配置了一个很大的
2021-06-01 09:30:48
-
iPhone12在618最新定價，跌價幅度超過1400元，還等iPhone13嗎？
不仅是<em>安卓</em>手机，苹果手机的降价力度也是前所未有了，iPhone12也“跳水价”了，发布价是6799元，如今已经跌至5308元，降价幅度超过1400元，最新定价确认了。iPhone12是苹果首款5G手机，同时也是全球首款5nm芯片的智能机，它
2021-06-01 09:30:45