Java數(shù)據(jù)結構之紅黑樹的實現(xiàn)方法和原理詳解
紅黑樹的說明
紅黑樹是一種自平衡的二叉搜索樹，它在每個節(jié)點上增加了一個存儲位來表示節(jié)點的顏色，可以是紅色或黑色。
與 AVL 樹相比之下，紅黑樹放寬了對平衡的要求，通過犧牲一定的平衡性能來換取更高的插入、刪除和查找操作的性能。紅黑樹的旋轉操作相對較少，因此在實際應用中，紅黑樹更常用于需要高效的動態(tài)數(shù)據(jù)結構，如集合、映射等。而 AVL 樹則更適用于對平衡性要求較高的場景，如數(shù)據(jù)庫索引等。
總的來說，紅黑樹也是一種自平衡的二叉搜索樹，較之 AVL 樹，插入和刪除時旋轉次數(shù)更少。
紅黑樹的特性
- 所有節(jié)點都有兩種顏色：紅與黑
- 所有 null 視為黑色
- 紅色節(jié)點不能相鄰
- 根節(jié)點是黑色
- 從根節(jié)點到任意一個葉子節(jié)點，路徑中的黑色節(jié)點數(shù)一樣（黑色完美平衡）
前四個規(guī)則都很容易理解，接下來詳細說明一下最后一個規(guī)則，到底什么是從根節(jié)點到葉子節(jié)點的所有路徑都要保證黑色節(jié)點數(shù)一樣？
如圖 1：
從根節(jié)點出發(fā)到葉子節(jié)點，首先從左子樹方向開始，6 -> 2 -> 1 -> null ，這一條路徑的黑色節(jié)點一共有 3 個；現(xiàn)在從左子樹方向出發(fā)，6 -> 2 -> null ，這一條路徑的黑色節(jié)點一共有 3 個；現(xiàn)在從右子樹方向開始，6 -> 8 -> null ，這一條路徑的黑色節(jié)點一共也是有 3 個黑色節(jié)點；這幾條路徑的黑色節(jié)點都為 3 。因此滿足紅黑樹的最后一條規(guī)則。
如圖 2：
同理，從根節(jié)點出發(fā)到葉子節(jié)點，先從左子樹方向開始，6 -> 2 -> 1 -> null ，這一條路徑的黑色節(jié)點一共有三個；再從 6 -> 2 -> null ，但是這一條路徑的黑色節(jié)點只有 2 個黑色節(jié)點，不滿足紅黑樹的最后一個規(guī)則。
在構建紅黑樹需要滿足以上規(guī)則，無論插入、刪除等都要滿足紅黑樹的特性。
紅黑樹的成員變量及其構造方法
- 節(jié)點類 TreeNode 作為內(nèi)部類，該內(nèi)部類的成員變量有：
int key : 關鍵字，用于比較大小
Object value : 值
TreeNode left : 左節(jié)點
TreeNode right : 右節(jié)點
Color color ：顏色，默認設置為紅色
TreeNode parent ：該節(jié)點的父親節(jié)點
- 該內(nèi)部類的構造方法：
節(jié)點類的構造方法主要是參數(shù)為 (int key, Object value) 的構造方法
- 紅黑樹的外部類的成員變量主要為：
TreeNode root ：根節(jié)點，一般默認為 null
- 紅黑樹的外部類的構造方法：
主要采取默認的參數(shù)為 null 的構造方法
代碼如下：
import static TreeNode.RedBlackTree.Color.BLACK;
import static TreeNode.RedBlackTree.Color.RED;
public class RedBlackTree {
enum Color {
RED,BLACK;
}
private TreeNode root;
private static class TreeNode {
int key;
Object value;
TreeNode left;
TreeNode right;
TreeNode parent;
Color color = RED;
//構造方法
public TreeNode(int key, Object value) {
this.key = key;
this.value = value;
}
}實現(xiàn)紅黑樹的核心方法
為了更好的實現(xiàn)插入、刪除等方法，需要先實現(xiàn)基礎的方法 "打好基礎"。主要分為實現(xiàn)內(nèi)部類與外部類的核心方法。
紅黑樹內(nèi)部類的核心方法
判斷當前節(jié)點是否為左孩子節(jié)點 - isLeftChild(）
實現(xiàn)思路為：先判斷該父親節(jié)點是否為 null ，若 parent == null 時，則當前節(jié)點為根節(jié)點；若 parent != null ，則需要繼續(xù)判斷 this == parent.left ，若滿足，則說明當前節(jié)點為左孩子節(jié)點，若不滿足，則說明當前節(jié)點為右孩子節(jié)點。
代碼如下：
//判斷是否為左孩子
public boolean isLeftChild() {
return parent != null && parent.left == this;
}獲取叔叔節(jié)點 - uncle()
叔叔節(jié)點即為跟父親節(jié)點的同一輩的節(jié)點，跟父親節(jié)點的父親是同一個父親。
實現(xiàn)思路為：需要先判斷該爺爺節(jié)點是否為 null 與 父親節(jié)點是否為 null ，因為該兩種情況都不具備叔叔節(jié)點。若以上情況都不為 null 時，接著還需要判斷當前節(jié)點的父親節(jié)點的位置，若父親節(jié)點為左孩子，則叔叔節(jié)點為右孩子；若父親節(jié)點為右孩子，則叔叔節(jié)點為左孩子。
代碼如下：
//獲取叔叔節(jié)點
public TreeNode uncle() {
if (this.parent == null || this.parent.parent == null) {
return null;
}
if (this.isLeftChild()) {
return this.parent.parent.right;
} else {
return this.parent.parent.left;
}
}獲取兄弟節(jié)點 - brother()
跟當前節(jié)點是同一輩的節(jié)點，同一個父親節(jié)點。
實現(xiàn)思路為：先判斷當前節(jié)點的父親節(jié)點是否為 null ，若parent == null 時，說明該節(jié)點不存在兄弟節(jié)點；若 parent != null 時，說明該節(jié)點存在兄弟節(jié)點，然后繼續(xù)判斷當前節(jié)點的位置，若當前節(jié)點為左孩子，則兄弟節(jié)點為：parent.right ；若當前節(jié)點為右孩子，則兄弟節(jié)點為：parent.left 。
代碼如下：
//獲取兄弟節(jié)點
public TreeNode brother() {
if (this.parent == null) {
return null;
}
if (this.isLeftChild()) {
return this.parent.right;
}else {
return this.parent.left;
}
}紅黑樹外部類的核心方法
判斷是否為紅色節(jié)點 isRed - (TreeNode node)
實現(xiàn)思路為：根據(jù)紅黑的規(guī)則可以知道，除了根節(jié)點與 null 之外， 當前節(jié)點的 color == RED 時，則該節(jié)點為紅色節(jié)點。
代碼如下：
//判斷是否為紅色節(jié)點
private boolean isRed(TreeNode node) {
return node != null && node.color == RED;
}判斷是否為黑色節(jié)點 isBlack - (TreeNode node)
實現(xiàn)思路為：有兩種情況下： null 或者 color == BLACK 的節(jié)點為黑色節(jié)點。
代碼如下：
//判斷是否為黑色節(jié)點
private boolean isBlack(TreeNode node) {
return node == null || node.color == BLACK;
}右旋 - rightRotate(TreeNode node)
實現(xiàn)思路為：跟 AVL 樹的右旋會有一定的區(qū)別，因為新添加了 parent 成員，所以正常右旋完之后，需要維護 parent 變量。
1. parent 的處理
2. 旋轉后新根的父子關系
如圖：
現(xiàn)需要將節(jié)點 8 進行右旋，假設節(jié)點 8 為 node ，那么先記錄節(jié)點5、節(jié)點6，nodeLeft = node.left、nodeLeftRight = nodeLeft.right 。接著更新節(jié)點 5 的右孩子，將其更新為節(jié)點 8 作為右孩子。還需要更新節(jié)點 8 的左孩子 ，將其更新為節(jié)點 6 作為左孩子。從表面上已經(jīng)完成右旋，但還需要維護節(jié)點的父親節(jié)點 parent 。對于節(jié)點 6 來說，之前的父親節(jié)點為節(jié)點 5 ，現(xiàn)在需要更新父親節(jié)點為節(jié)點8，不過需要先判斷節(jié)點 6 是否為 null ，若節(jié)點 6 為 null ，則不需要更新父親節(jié)點的操作。若節(jié)點 6 不為 null，則需要更新父親節(jié)點這一操作。對于節(jié)點 5 來說，節(jié)點 5 的父親節(jié)點之前為節(jié)點 8，先父親節(jié)點更新為節(jié)點 8 的父親節(jié)點，因此還需要記錄節(jié)點 8 的父親節(jié)點。對于節(jié)點 8 來說，將其父親節(jié)點更新為節(jié)點 5 。最后，由于現(xiàn)在的節(jié)點與節(jié)點之間時雙互的，所以還需要維護新根的父子關系，不過需要判斷節(jié)點 8 的父親節(jié)點是否為 null ，若為 parent == null 時，則說明節(jié)點 5 為根節(jié)點，因此需要進行 root = node.left 調(diào)整；若 parent != null ，需要判斷 node 的位置，若 node 是左孩子，那么 parent.left = node.left 進行鏈接；若 node 是右孩子，那么 parent.right = node.left 進行鏈接。那么現(xiàn)在就可以根據(jù)這個邏輯寫代碼了。
最后調(diào)整完之后的圖：
代碼如下：
//右旋
//1.考慮旋轉后節(jié)點的維護parent 2.重新與上一個節(jié)點建立聯(lián)系
private void rightRotate(TreeNode node) {
TreeNode parent = node.parent;
TreeNode nodeLeft = node.left;
TreeNode nodeLeftRight = nodeLeft.right;
if (nodeLeftRight != null) {
nodeLeftRight.parent = node;
}
nodeLeft.right = node;
nodeLeft.parent = parent;
node.left = nodeLeftRight;
node.parent = nodeLeft;
if (parent == null) {
root = nodeLeft;
} else if (parent.left == node) {
parent.left = nodeLeft;
}else {
parent.right = nodeLeft;
}
}左旋 - leftRotate(TreeNode node)
跟右旋的邏輯是一摸一樣的，這里就不多贅述了。
代碼如下：
//左旋
//1.考慮旋轉后節(jié)點的維護parent 2.重新與上一個節(jié)點建立聯(lián)系
private void leftRotate(TreeNode node) {
TreeNode parent = node.parent;
TreeNode nodeRight = node.right;
TreeNode nodeRightLeft = nodeRight.left;
if (nodeRightLeft != null) {
nodeRightLeft.parent = node;
}
nodeRight.left = node;
nodeRight.parent = parent;
node.right = nodeRightLeft;
node.parent = nodeRight;
//2.重新與上一個節(jié)點建立聯(lián)系
if (parent == null) {
root = nodeRight;
} else if (parent.left == node) {
parent.left = nodeRight;
}else {
parent.right = nodeRight;
}
}更新、添加節(jié)點 - put(int key，Object value)
實現(xiàn)思路為：正常刪除節(jié)點、更新節(jié)點，若遇到紅紅節(jié)點不平衡，則需要進行調(diào)整
對于正常刪除、更新節(jié)點的邏輯為：根據(jù) key 來尋找需要更新或者刪除的節(jié)點、若找到了 key 的節(jié)點，那么直接更新該節(jié)點的 value 即可；若沒有找到 key 的節(jié)點，需要進行添加節(jié)點。需要用到 parent 變量，記錄每一次的當前節(jié)點，一旦當前節(jié)點為 node == null 時，找到了相應的空位，接著判斷 key 與 parent.key 的大小。若 parent.key > key ，則 parent.left = node;若 parent.key < key 則 parent.right = node;若 parent == null 時，說明該紅黑樹為空樹，所以 root = node 。最后對于更新來說，不會改變紅黑樹的平衡關系，對于添加完節(jié)點，很有可能會改變紅黑樹的平衡關系，所以需要進行紅紅修復。
接下來詳細聊一下紅紅節(jié)點不平衡后進行的調(diào)整：
插入節(jié)點均視為紅色
- case 1：插入節(jié)點為根節(jié)點，將根節(jié)點變?yōu)楹谏?/li>
- case 2：插入節(jié)點的父親若為黑色，樹的紅黑性質(zhì)不變，無需調(diào)整
插入節(jié)點的父親節(jié)點為紅色，觸發(fā)紅紅相鄰
- case3：叔叔為紅色
將父親節(jié)點變?yōu)楹谏?，為了保證黑色平衡，連帶的叔叔也變?yōu)楹谏娓溉绻呛谏蛔兩?，會造成這顆子樹黑色過多，因此祖父節(jié)點變?yōu)榧t色。但是祖父變?yōu)榧t色，可能也會繼續(xù)觸發(fā)紅紅相鄰，因此對講祖父進行遞歸調(diào)整。
如圖 ：對于 case 3 詳細說明
插入節(jié)點為節(jié)點 1 設為 node ，該父親節(jié)點為節(jié)點 2 設為 parent 。對于 node 節(jié)點來說，遇到了紅紅不平衡的情況，且該節(jié)點 4 即為叔叔節(jié)點為紅色。
調(diào)整紅黑樹平衡：需要將父親節(jié)點、叔叔節(jié)點的顏色都要置為黑色，parent.color = BLACK，uncle.color = BALCK ，將節(jié)點 3 即祖父節(jié)點的顏色置為紅色，parent.parent.color = RED ?？梢园l(fā)現(xiàn)節(jié)點 3 與節(jié)點 5 又再一次出現(xiàn)了觸發(fā)了紅紅相鄰了，那么利用遞歸來解決這一情況，一旦遇到 node == root 時，即可停止遞歸了。
最后調(diào)整后之后的圖：
- case 4：叔叔為黑色
1. 父親為左孩子，插入節(jié)點也是左孩子，此時即 LL 不平衡
2. 父親為左孩子，插入節(jié)點是右孩子，此時即 LR 不平衡
3. 父親為右孩子，插入節(jié)點也是右孩子，此時即 RR 不平衡
4. 父親為右孩子，插入節(jié)點是左孩子，此時即 RL 不平衡
如圖：對于 case 4 中LL 不平衡的詳細說明
插入節(jié)點為節(jié)點 2 設為 node，父親節(jié)點為節(jié)點 3 設為 parent ，該叔叔節(jié)點為 null 該節(jié)點為黑色，又滿足 node 為左孩子，parent 也為左孩子， LL 不平衡。該調(diào)整需要將 parent.color = BLACK，parent.parent.color = RED，把爺爺節(jié)點 rightRotate(parent.parent) 右旋一次即可。
調(diào)整完之后的圖為：
如圖：對于 case 4 中 LR 不平衡的詳細說明
插入節(jié)點為節(jié)點 4 設為 node，父親節(jié)點為節(jié)點 3 設為 parent，node 的叔叔節(jié)點為 null 所以該顏色為黑色。又 parent 是左孩子，node 是右孩子，滿足 LR 不平衡。
需要做的第一步，將 LR 轉變?yōu)?LL ，只需要將 node 節(jié)點左旋。
接著，將 node.color = BLACK，parent.parent.color = RED 處理，再將爺爺節(jié)點右旋，rightRotate(parent.parent) 即可。
調(diào)整完之后的圖：
其余的 case 4 的情況大致與以上的情況相同，所以這里不再過多贅述了。
代碼如下：
//更新、增添節(jié)點
//正常更新、刪除，遇到紅紅不平衡則需要進行調(diào)整
public void put (int key, Object value) {
TreeNode p = root;
TreeNode parent = null;
while (p != null) {
parent = p;
if (p.key > key) {
p = p.left;
}else if (p.key < key) {
p = p.right;
}else {
p.value = value;
return;
}
}
TreeNode node = new TreeNode(key,value);
if (parent == null) {
root = node;
}else {
if (node.key > parent.key) {
parent.right = node;
}else {
parent.left = node;
}
node.parent = parent;
}
//可能會發(fā)生紅紅不平衡，則需要調(diào)整
fixRedRed(node);
}
//調(diào)整紅紅不平衡
private void fixRedRed(TreeNode node) {
//case1: 插入節(jié)點為根節(jié)點，將根節(jié)點變黑
if(node == root) {
node.color = BLACK;
return;
}
if (isBlack(node.parent)) {
//case2:插入節(jié)點的父親若為黑，樹的紅黑性質(zhì)不變，無需調(diào)整
//無需調(diào)整
return;
}
// 插入節(jié)點的父親為紅色，觸發(fā)紅紅相鄰
//case3:叔叔為紅色
TreeNode parent = node.parent;
TreeNode grandparent = parent.parent;
TreeNode uncle = node.uncle();
if (isRed(uncle)) {
//進行變色處理即可
//將其父親、叔叔變?yōu)楹谏?，爺爺變?yōu)榧t色
//若爺爺觸發(fā)了紅紅，則繼續(xù)遞歸調(diào)用該函數(shù)
parent.color = BLACK;
uncle.color = BLACK;
grandparent.color = RED;
fixRedRed(grandparent);
return;
}
//case4:叔叔為黑色
//該父親為左孩子，該插入點也為左孩子，則觸發(fā) ll
if (parent.isLeftChild() && node.isLeftChild()) {
//先將父親變?yōu)楹谏?、爺爺變?yōu)榧t色，再右旋轉
parent.color = BLACK;
grandparent.color = RED;
rightRotate(grandparent);
}else if (parent.isLeftChild()) {
//該插入節(jié)點為右孩子、該父親為左孩子，則觸發(fā) lr
//先左旋變?yōu)?ll 情況
leftRotate(parent);
node.color = BLACK;
grandparent.color = RED;
rightRotate(grandparent);
} else if (!node.isLeftChild()) {
//插入節(jié)點為右孩子、父親節(jié)點也為右孩子 rr
parent.color = BLACK;
grandparent.color = RED;
leftRotate(grandparent);
}else {
//插入節(jié)點為左孩子、父親節(jié)點為右孩子 rl
rightRotate(parent);
node.color = BLACK;
grandparent.color = RED;
leftRotate(grandparent);
}
}刪除節(jié)點 - remove(int key)
實現(xiàn)思路：正常刪除節(jié)點，若遇到黑黑不平衡，則需要進行調(diào)整
正常刪除節(jié)點的邏輯：先找到需要刪除的節(jié)點，為了后續(xù)的代碼簡潔，因此單獨實現(xiàn)尋找刪除節(jié)點的方法，尋找代碼的邏輯這里就不過多展開了。又單獨實現(xiàn)尋找刪除節(jié)點的替代節(jié)點的方法，這個方法的簡單邏輯為：若刪除節(jié)點沒有左右孩子，則替代的節(jié)點為 null ;若刪除節(jié)點只有一個孩子，則返回不為 null 的孩子；若刪除節(jié)點有兩個節(jié)點，則找到右子樹的最小節(jié)點返回即可。
現(xiàn)在找到了刪除節(jié)點，判斷該刪除節(jié)點是否為 null ，若 delete == null ，則說明沒有找到刪除節(jié)點，結束刪除過程；若 delete != null ，則說明可以找到刪除節(jié)點，則繼續(xù)通過根據(jù)刪除節(jié)點查找替換節(jié)點的方法找到替換節(jié)點，最后就可以刪除節(jié)點了。對于刪除節(jié)點是一個復雜的操作，所以單獨為一個方法 doRemove(TreeNode deleted) 。
對于實現(xiàn) doRemove(TreeNode deleted) 方法，需要考慮以下情況：
- case0: 對于刪除節(jié)點有兩個孩子來說，需要將其轉換為只有一個孩子或者沒有孩子情況。這里用到了李代桃僵技巧，例如，需要刪除節(jié)點 deleted ，替代節(jié)點 replace ，將該兩個節(jié)點的關鍵字 key 與值 value 交換，那么現(xiàn)在需要刪除的節(jié)點不再是 deleted 了，而是 replace 。遞歸調(diào)用 doRemove(replace) 。這樣子就可以將兩個孩子的情況轉變?yōu)橐粋€孩子或者沒有孩子的情況了。
- case1: 刪除節(jié)點為根節(jié)點的情況。先考慮根節(jié)點沒有左右孩子的情況，則直接將 root == null 。再考慮根節(jié)點有一個孩子的情況，則利用到李代桃僵的技巧，將孩子節(jié)點的關鍵字 key 與值 value 跟root 節(jié)點的關鍵字 key 與值 value 分別進行交換，這樣刪除的節(jié)點就是孩子節(jié)點了，將根節(jié)點的左右孩子置為 null 即可。最后要不要考慮根節(jié)點有兩個孩子的情況呢？
其實是不用的，因為已經(jīng)通過李代桃僵的技巧將有兩個孩子節(jié)點轉換為一個孩子或者沒有孩子的節(jié)點。
- case2: 刪除節(jié)點不為根節(jié)點的情況。同樣，先考慮刪除的節(jié)點沒有左右孩子的情況，也說明刪除的節(jié)點就是葉子節(jié)點，所以先判斷該刪除節(jié)點的位置，若刪除節(jié)點是左孩子，那么父親節(jié)點的左孩子置為 null ，parent.left = null；若刪除節(jié)點是右孩子，那么父親節(jié)點的右孩子置為 null ，parent.right = null 。最后還需要將刪除節(jié)點的父親節(jié)點置為 null ，方便后續(xù)的內(nèi)存自動回收。
接著再來考慮刪除節(jié)點有一個孩子的情況，刪除節(jié)點設為 deleted，替換節(jié)點設為 repalce 。 先判斷 deleted 的位置，若 deleted 是左孩子，則 parent.left = repalce 進行鏈接；若 deleted 是右孩子，則 parent.right = replace 進行鏈接。由于紅黑樹的節(jié)點與節(jié)點之間鏈接是相互的，所以，replace 節(jié)點的父親節(jié)點需要鏈接到 parent 上， replace.parent = parent 。最后需要將刪除節(jié)點刪除干凈，方便內(nèi)存自動回收，所以 deleted.left = deleted.right = deleted.parent = null 。同樣，對于刪除節(jié)點有兩個孩子的情況不需要考慮，已經(jīng)轉換為一個孩子或者沒有孩子的情況了。
刪除節(jié)點之后，很有可能會導致紅黑樹的性質(zhì)改變，所以刪除節(jié)點之前或者刪除節(jié)點之后，需要進行調(diào)整，使其紅黑樹確保性質(zhì)不會發(fā)生改變。主要有以下情況：
對于刪除節(jié)點沒有左右孩子來說：如果刪除節(jié)點的顏色是紅色，且沒有左右孩子，則直接刪除完之后，不會發(fā)生紅黑樹性質(zhì)改變；如果刪除節(jié)點的顏色是黑色，且沒有左右孩子，則會觸發(fā)黑黑相鄰，直接刪除會導致紅黑樹性質(zhì)發(fā)生改變，所以需要進行復雜調(diào)整。
對于刪除節(jié)點有一個節(jié)點來說：如果刪除節(jié)點的顏色為黑色，替換節(jié)點為紅色，則刪除節(jié)點之后，需要將替換節(jié)點的顏色變?yōu)楹谏纯?；如果刪除節(jié)點的顏色為黑色，替換節(jié)點也為黑色，則觸發(fā)了黑黑相鄰，需要進行復雜的調(diào)整。
進行復雜的調(diào)整，修復黑黑不平衡的方法 fixBlackBlack(TreeNode node)
刪除節(jié)點與剩下節(jié)點顏色都是黑色，觸發(fā)雙黑，雙黑意思是，少了一個黑。
- case3: 刪除節(jié)點或者剩余節(jié)點的兄弟為紅色，此時兩個侄子定位黑色。
如圖：
刪除節(jié)點為節(jié)點 4 設為 deletde ，兄弟節(jié)點為節(jié)點 8 設為 brother，父親節(jié)點為節(jié)點 6 設為 parent ?，F(xiàn)在刪除節(jié)點 4 的顏色為黑色，且剩余節(jié)點為 null 該顏色為黑色，觸發(fā)雙黑，又兄弟節(jié)點為紅色。滿足以上情況時，先判斷兄弟節(jié)點的置為，若兄弟節(jié)點為右孩子，則需要將該父親節(jié)點進行左旋；若兄弟節(jié)點為左孩子，則需要將該父親節(jié)點進行右旋。旋轉完之后，需要變色處理，將父親節(jié)點的顏色變?yōu)榧t色，兄弟節(jié)點的顏色變?yōu)楹谏Ｗ詈?，繼續(xù)將刪除節(jié)點遞歸調(diào)用該函數(shù)。該方法的目的就是將刪除節(jié)點的兄弟節(jié)點的顏色由紅色變?yōu)楹谏?，好對以下兩種情況處理。簡單說明，這個方法就是一個過度的方法。
- case4: 被調(diào)整節(jié)點的兄弟為黑色，兩個侄子都為黑色
步驟一：將兄弟節(jié)點的顏色變?yōu)榧t，目的是將刪除節(jié)點和兄弟那邊的黑色高度同時減少1
步驟二：如果父親是紅，則需要將父親變?yōu)楹谏?，避免紅紅相鄰，此時路徑黑色節(jié)點數(shù)目不變。
步驟三：如果父親是黑色，說明這條路徑則少了一個黑，再次讓父親節(jié)點觸發(fā)雙黑。
如圖：
調(diào)整節(jié)點為節(jié)點 1 設為 node ，兄弟節(jié)點為節(jié)點 2 設為 brother，父親節(jié)點為節(jié)點 2 設為 parent 。該情況滿足了刪除節(jié)點與剩余節(jié)點都是黑色，觸發(fā)雙黑，且兄弟節(jié)點的顏色也為黑色，父親節(jié)點的顏色為紅色。調(diào)整的方法為：將兄弟節(jié)點的顏色變?yōu)榧t色，將父親節(jié)點的顏色變?yōu)楹谏纯伞?/p>
調(diào)整完之后的圖：
如圖：
調(diào)整節(jié)點為節(jié)點 1 設為 node ，兄弟節(jié)點為節(jié)點 3 設為 brother ，父親節(jié)點為節(jié)點 2 設為 parent 。該情況滿足調(diào)整節(jié)點與剩余節(jié)點的顏色都為黑色，觸發(fā)雙黑，且兄弟節(jié)點的顏色也為黑色，父親節(jié)點也都為黑色。調(diào)整方法：將兄弟節(jié)點的顏色變?yōu)榧t色，再讓父親節(jié)點遞歸調(diào)用該函數(shù)，繼續(xù)觸發(fā)雙黑。
調(diào)整完之后的圖：
- case5: 被調(diào)整節(jié)點的兄弟為黑色，至少有一個紅色節(jié)點的侄子節(jié)點。
如果兄弟是左孩子，左侄子是紅色，觸發(fā) LL 不平衡
如果兄弟是左孩子，右侄子是紅色，觸發(fā) LR 不平衡
如果兄弟是右孩子，右侄子是紅色，觸發(fā) RR 不平衡
如果兄弟是右孩子，左侄子是紅色，觸發(fā) RL 不平衡
如圖： 觸發(fā) LL 不平衡情況
調(diào)整節(jié)點為節(jié)點 4 設為 node ，兄弟節(jié)點為節(jié)點 2 設為 brother ，父親節(jié)點為節(jié)點 3 設為 parent ，侄子節(jié)點為節(jié)點 1 。兄弟節(jié)點與侄子節(jié)點都是左孩子，且侄子節(jié)點為紅色。調(diào)整方法：將父親節(jié)點進行右旋，再把侄子節(jié)點的顏色變?yōu)楹谏值芄?jié)點的顏色變?yōu)樵瓉砀赣H節(jié)點的顏色，父親節(jié)點的顏色變?yōu)楹谏?/p>
調(diào)整完之后的圖：
如圖：觸發(fā) LR 不平衡情況
調(diào)整節(jié)點為節(jié)點 4 設為 node ，父親節(jié)點為節(jié)點 3 設為 parent ，兄弟節(jié)點為節(jié)點 1 設為 brother ，侄子節(jié)點為節(jié)點 2 。兄弟節(jié)點是左孩子，侄子為右孩子，觸發(fā)了 LR 不平衡。調(diào)整方法：先將兄弟節(jié)點左旋，變成了 LL 不平衡情況。
再把侄子節(jié)點的顏色變?yōu)樵瓉砀赣H節(jié)點的顏色，再到父親節(jié)點的顏色變?yōu)楹谏?，最后右旋父親節(jié)點即可。
調(diào)整完之后的圖：
還有 RR 、RL 的情況與以上的情況大致是一樣的，所以這里就不過多贅述了。
刪除節(jié)點的代碼如下：
//查找刪除節(jié)點
private TreeNode findDelete(int key) {
TreeNode p = root;
while(p != null) {
if (p.key > key) {
p = p.left;
} else if (p.key < key) {
p = p.right;
}else {
return p;
}
}
//若沒有找到則返回null
return null;
}
//查找剩余節(jié)點
private TreeNode findReplaced(TreeNode deleted) {
//沒有孩子的情況:
if (deleted.left == null && deleted.right == null) {
return null;
}
if (deleted.left == null) {
return deleted.right;
}
if (deleted.right == null) {
return deleted.left;
}
//有兩個孩子的情況,找后繼節(jié)點即可
TreeNode p = deleted.right;
while(p.left != null) {
p = p.left;
}
return p;
}
//刪除節(jié)點
//正常刪除節(jié)點，遇到黑黑不平衡則需要進行調(diào)整
public void remove(int key) {
TreeNode delete = findDelete(key);
if (delete == null) {
return;
}
doRemove(delete);
}
private void doRemove(TreeNode deleted) {
TreeNode replaced = findReplaced(deleted);
TreeNode parent = deleted.parent;
//沒有孩子的情況:
if (replaced == null) {
//刪除的節(jié)點為根節(jié)點情況下:
if (deleted == root) {
root = null;
return;
}else {
if (isRed(deleted)) {
//無需任何操作
}else {
//觸發(fā)黑黑不平衡，需要進行復雜的操作
fixBlackBlack(deleted);
}
if (deleted.isLeftChild()) {
parent.left = null;
}else {
parent.right = null;
}
deleted.parent = null;
}
return;
}
//有一個孩子的情況
if (deleted.left == null || deleted.right == null) {
if (deleted == root) {
root.key = replaced.key;
root.value = replaced.value;
root.left = root.right = null;
}else {
if (deleted.isLeftChild()) {
parent.left = replaced;
} else {
parent.right = replaced;
}
replaced.parent = parent;
deleted.left = deleted.right = deleted.parent = null;
if (isRed(replaced) && isBlack(deleted)) {
//卻少一個黑色，則將替換的節(jié)點換為紅色即可
replaced.color = BLACK;
}else {
//遇到黑黑不平衡情況，則需要進行復雜調(diào)整
fixBlackBlack(replaced);
}
}
return;
}
//有兩個孩子的情況,需要將用到李代桃僵技巧
int key = deleted.key;
deleted.key = replaced.key;
replaced.key = key;
Object value = deleted.value;
deleted.value = replaced.value;
replaced.value = value;
doRemove(replaced);
}
private void fixBlackBlack(TreeNode node) {
if (node == root) {
return;
}
TreeNode parent = node.parent;
TreeNode brother = node.brother();
if (isRed(node.brother())) {
//先進行旋轉調(diào)整，再換色暫時達到平衡
if (brother.isLeftChild()) {
rightRotate(parent);
}else {
leftRotate(parent);
}
parent.color = RED;
brother.color = BLACK;
fixBlackBlack(node);
return;
}
//兩個侄子都為黑色
if (brother == null) {
fixBlackBlack(parent);
}else {
//case 4 兄弟是黑色，兩個侄子也是黑色
if (isBlack(brother.left) && isBlack(brother.right)) {
brother.color = RED;
if (isRed(parent)) {
parent.color = BLACK;
}else {
fixBlackBlack(parent);
}
}
//case 5 兄弟是黑色，侄子有紅色
else {
//其中某一個侄子不為黑色
//兄弟為左孩子、侄子為左孩子，觸發(fā) ll
if (brother.isLeftChild() && isRed(brother.left)) {
rightRotate(parent);
brother.left.color = BLACK;
brother.color = parent.color;
parent.color = BLACK;
} else if (brother.isLeftChild() && isRed(brother.right)) {
//兄弟為左孩子、侄子為右孩子，先觸發(fā) lr
//需要將 lr 轉變?yōu)?ll 情況再處理
brother.right.color = parent.color;
leftRotate(brother);
rightRotate(parent);
parent.color = BLACK;
} else if ( !brother.isLeftChild() && isRed(brother.right)) {
//兄弟為右孩子，侄子為右孩子，觸發(fā) rr
leftRotate(parent);
brother.right.color = BLACK;
brother.color = parent.color;
parent.color = BLACK;
}else {
//最后一種情況兄弟為右孩子、侄子為左孩子，觸發(fā) rl
//需要將 rl 轉變?yōu)?rr 情況再處理
brother.left.color = parent.color;
rightRotate(brother);
leftRotate(parent);
parent.color = BLACK;
}
}
}
}實現(xiàn)紅黑樹核心方法的完整代碼
import static TreeNode.RedBlackTree.Color.BLACK;
import static TreeNode.RedBlackTree.Color.RED;
public class RedBlackTree {
enum Color {
RED,BLACK;
}
private TreeNode root;
private static class TreeNode {
int key;
Object value;
TreeNode left;
TreeNode right;
TreeNode parent;
Color color = RED;
//構造方法
public TreeNode(int key, Object value) {
this.key = key;
this.value = value;
}
public TreeNode(int key, Object value, TreeNode left, TreeNode right, TreeNode parent) {
this.key = key;
this.value = value;
this.left = left;
this.right = right;
this.parent = parent;
}
//判斷是否為左孩子
public boolean isLeftChild() {
return parent != null && parent.left == this;
}
//獲取叔叔節(jié)點
public TreeNode uncle() {
if (this.parent == null || this.parent.parent == null) {
return null;
}
if (this.isLeftChild()) {
return this.parent.parent.right;
} else {
return this.parent.parent.left;
}
}
//獲取兄弟節(jié)點
public TreeNode brother() {
if (this.parent == null) {
return null;
}
if (this.isLeftChild()) {
return this.parent.right;
}else {
return this.parent.left;
}
}
}
//判斷是否為紅色節(jié)點
private boolean isRed(TreeNode node) {
return node != null && node.color == RED;
}
//判斷是否為黑色節(jié)點
private boolean isBlack(TreeNode node) {
return node == null || node.color == BLACK;
}
//右旋
//1.考慮旋轉后節(jié)點的維護parent 2.重新與上一個節(jié)點建立聯(lián)系
private void rightRotate(TreeNode node) {
TreeNode parent = node.parent;
TreeNode nodeLeft = node.left;
TreeNode nodeLeftRight = nodeLeft.right;
if (nodeLeftRight != null) {
nodeLeftRight.parent = node;
}
nodeLeft.right = node;
nodeLeft.parent = parent;
node.left = nodeLeftRight;
node.parent = nodeLeft;
if (parent == null) {
root = nodeLeft;
} else if (parent.left == node) {
parent.left = nodeLeft;
}else {
parent.right = nodeLeft;
}
}
//左旋
//1.考慮旋轉后節(jié)點的維護parent 2.重新與上一個節(jié)點建立聯(lián)系
private void leftRotate(TreeNode node) {
TreeNode parent = node.parent;
TreeNode nodeRight = node.right;
TreeNode nodeRightLeft = nodeRight.left;
if (nodeRightLeft != null) {
nodeRightLeft.parent = node;
}
nodeRight.left = node;
nodeRight.parent = parent;
node.right = nodeRightLeft;
node.parent = nodeRight;
//2.重新與上一個節(jié)點建立聯(lián)系
if (parent == null) {
root = nodeRight;
} else if (parent.left == node) {
parent.left = nodeRight;
}else {
parent.right = nodeRight;
}
}
//更新、增添節(jié)點
//正常更新、刪除，遇到紅紅不平衡則需要進行調(diào)整
public void put (int key, Object value) {
TreeNode p = root;
TreeNode parent = null;
while (p != null) {
parent = p;
if (p.key > key) {
p = p.left;
}else if (p.key < key) {
p = p.right;
}else {
p.value = value;
return;
}
}
TreeNode node = new TreeNode(key,value);
if (parent == null) {
root = node;
}else {
if (node.key > parent.key) {
parent.right = node;
}else {
parent.left = node;
}
node.parent = parent;
}
//可能會發(fā)生紅紅不平衡，則需要調(diào)整
fixRedRed(node);
}
//調(diào)整紅紅不平衡
private void fixRedRed(TreeNode node) {
//case1: 插入節(jié)點為根節(jié)點，將根節(jié)點變黑
if(node == root) {
node.color = BLACK;
return;
}
if (isBlack(node.parent)) {
//case2:插入節(jié)點的父親若為黑，樹的紅黑性質(zhì)不變，無需調(diào)整
//無需調(diào)整
return;
}
// 插入節(jié)點的父親為紅色，觸發(fā)紅紅相鄰
//case3:叔叔為紅色
TreeNode parent = node.parent;
TreeNode grandparent = parent.parent;
TreeNode uncle = node.uncle();
if (isRed(uncle)) {
//進行變色處理即可
//將其父親、叔叔變?yōu)楹谏瑺敔斪優(yōu)榧t色
//若爺爺觸發(fā)了紅紅，則繼續(xù)遞歸調(diào)用該函數(shù)
parent.color = BLACK;
uncle.color = BLACK;
grandparent.color = RED;
fixRedRed(grandparent);
return;
}
//case4:叔叔為黑色
//該父親為左孩子，該插入點也為左孩子，則觸發(fā) ll
if (parent.isLeftChild() && node.isLeftChild()) {
//先將父親變?yōu)楹谏?、爺爺變?yōu)榧t色，再右旋轉
parent.color = BLACK;
grandparent.color = RED;
rightRotate(grandparent);
}else if (parent.isLeftChild()) {
//該插入節(jié)點為右孩子、該父親為左孩子，則觸發(fā) lr
//先左旋變?yōu)?ll 情況
leftRotate(parent);
node.color = BLACK;
grandparent.color = RED;
rightRotate(grandparent);
} else if (!node.isLeftChild()) {
//插入節(jié)點為右孩子、父親節(jié)點也為右孩子 rr
parent.color = BLACK;
grandparent.color = RED;
leftRotate(grandparent);
}else {
//插入節(jié)點為左孩子、父親節(jié)點為右孩子 rl
rightRotate(parent);
node.color = BLACK;
grandparent.color = RED;
leftRotate(grandparent);
}
}
//查找刪除節(jié)點
private TreeNode findDelete(int key) {
TreeNode p = root;
while(p != null) {
if (p.key > key) {
p = p.left;
} else if (p.key < key) {
p = p.right;
}else {
return p;
}
}
//若沒有找到則返回null
return null;
}
//查找剩余節(jié)點
private TreeNode findReplaced(TreeNode deleted) {
//沒有孩子的情況:
if (deleted.left == null && deleted.right == null) {
return null;
}
if (deleted.left == null) {
return deleted.right;
}
if (deleted.right == null) {
return deleted.left;
}
//有兩個孩子的情況,找后繼節(jié)點即可
TreeNode p = deleted.right;
while(p.left != null) {
p = p.left;
}
return p;
}
//刪除節(jié)點
//正常刪除節(jié)點，遇到黑黑不平衡則需要進行調(diào)整
public void remove(int key) {
TreeNode delete = findDelete(key);
if (delete == null) {
return;
}
doRemove(delete);
}
private void doRemove(TreeNode deleted) {
TreeNode replaced = findReplaced(deleted);
TreeNode parent = deleted.parent;
//沒有孩子的情況:
if (replaced == null) {
//刪除的節(jié)點為根節(jié)點情況下:
if (deleted == root) {
root = null;
return;
}else {
if (isRed(deleted)) {
//無需任何操作
}else {
//觸發(fā)黑黑不平衡，需要進行復雜的操作
fixBlackBlack(deleted);
}
if (deleted.isLeftChild()) {
parent.left = null;
}else {
parent.right = null;
}
deleted.parent = null;
}
return;
}
//有一個孩子的情況
if (deleted.left == null || deleted.right == null) {
if (deleted == root) {
root.key = replaced.key;
root.value = replaced.value;
root.left = root.right = null;
}else {
if (deleted.isLeftChild()) {
parent.left = replaced;
} else {
parent.right = replaced;
}
replaced.parent = parent;
deleted.left = deleted.right = deleted.parent = null;
if (isRed(replaced) && isBlack(deleted)) {
//卻少一個黑色，則將替換的節(jié)點換為紅色即可
replaced.color = BLACK;
}else {
//遇到黑黑不平衡情況，則需要進行復雜調(diào)整
fixBlackBlack(replaced);
}
}
return;
}
//有兩個孩子的情況,需要將用到李代桃僵技巧
int key = deleted.key;
deleted.key = replaced.key;
replaced.key = key;
Object value = deleted.value;
deleted.value = replaced.value;
replaced.value = value;
doRemove(replaced);
}
private void fixBlackBlack(TreeNode node) {
if (node == root) {
return;
}
TreeNode parent = node.parent;
TreeNode brother = node.brother();
if (isRed(node.brother())) {
//先進行旋轉調(diào)整，再換色暫時達到平衡
if (brother.isLeftChild()) {
rightRotate(parent);
}else {
leftRotate(parent);
}
parent.color = RED;
brother.color = BLACK;
fixBlackBlack(node);
return;
}
//兩個侄子都為黑色
if (brother == null) {
fixBlackBlack(parent);
}else {
//case 4 兄弟是黑色，兩個侄子也是黑色
if (isBlack(brother.left) && isBlack(brother.right)) {
brother.color = RED;
if (isRed(parent)) {
parent.color = BLACK;
}else {
fixBlackBlack(parent);
}
}
//case 5 兄弟是黑色，侄子有紅色
else {
//其中某一個侄子不為黑色
//兄弟為左孩子、侄子為左孩子，觸發(fā) ll
if (brother.isLeftChild() && isRed(brother.left)) {
rightRotate(parent);
brother.left.color = BLACK;
brother.color = parent.color;
parent.color = BLACK;
} else if (brother.isLeftChild() && isRed(brother.right)) {
//兄弟為左孩子、侄子為右孩子，先觸發(fā) lr
//需要將 lr 轉變?yōu)?ll 情況再處理
brother.right.color = parent.color;
leftRotate(brother);
rightRotate(parent);
parent.color = BLACK;
} else if ( !brother.isLeftChild() && isRed(brother.right)) {
//兄弟為右孩子，侄子為右孩子，觸發(fā) rr
leftRotate(parent);
brother.right.color = BLACK;
brother.color = parent.color;
parent.color = BLACK;
}else {
//最后一種情況兄弟為右孩子、侄子為左孩子，觸發(fā) rl
//需要將 rl 轉變?yōu)?rr 情況再處理
brother.left.color = parent.color;
rightRotate(brother);
leftRotate(parent);
parent.color = BLACK;
}
}
}
}
}到此這篇關于Java數(shù)據(jù)結構之紅黑樹的實現(xiàn)方法和原理詳解的文章就介紹到這了,更多相關Java紅黑樹內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！
相關文章
這篇文章主要介紹了在springboot中如何給mybatis加攔截器，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2022-08-08
這個概念估計懂C++的人不會陌生，但是很多朋友并不了解，概括起來將淺拷貝就是指兩個對象公用一個值，一個的改變了另一個也會隨之改變，深拷貝則是兩個對象值相等，但是相互獨立互不影響。下面我們將關于java的淺拷貝和深拷貝做一個詳細講解2021-06-06
Jmeter對響應數(shù)據(jù)實現(xiàn)斷言代碼實例
這篇文章主要介紹了Jmeter對響應數(shù)據(jù)實現(xiàn)斷言代碼實例,文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值,需要的朋友可以參考下2020-09-09
SpringBoot使用@SpringBootTest注解開發(fā)單元測試教程
這篇文章主要介紹了SpringBoot使用@SpringBootTest注解開發(fā)單元測試教程,本文通過詳細的案例過程來說明如何使用該項技術,需要的朋友可以參考下2021-06-06
作為程序員,多多少少都會遇到一些內(nèi)存溢出的場景,如果你還沒遇到,說明你工作的年限可能比較短,或者你根本就是個假程序員！哈哈,開個玩笑.今天分享給大家Java內(nèi)存溢出的相關案例,希望大家在日常工作中,盡量避免寫這些low水平的代碼,需要的朋友可以參考下2021-06-06
Yml轉properties文件工具類YmlUtils的詳細過程(不用引任何插件和依賴)
這篇文章主要介紹了Yml轉properties文件工具類YmlUtils（不用引任何插件和依賴）,本文給大家介紹的非常詳細，對大家的學習或工作具有一定的參考借鑒價值，需要的朋友可以參考下2021-08-08
解決引入Redisson可能會出現(xiàn)項目啟動失敗的問題
這篇文章主要介紹了解決引入Redisson可能會出現(xiàn)項目啟動失敗的問題,具有很好的參考價值,希望對大家有所幫助,如有錯誤或未考慮完全的地方,望不吝賜教2024-06-06
這篇文章主要介紹了關于@Autowired注入依賴失敗的問題及解決方案，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2022-08-08
MapStruct是一個強大的Java映射框架,它能夠在編譯時生成映射代碼,,本文主要介紹了Java中MapStruct映射處理器報錯的問題解決,具有一定的參考價值,感興趣的可以了解一下2024-03-03
下面小編就為大家?guī)硪黄贘SON和java對象的互轉方法。小編覺得挺不錯的，現(xiàn)在就分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2017-09-09