Java數(shù)據(jù)結(jié)構(gòu)之紅黑樹(shù)的實(shí)現(xiàn)方法和原理詳解

更新時(shí)間：2024年02月11日 09:39:48 作者：小扳

這篇文章主要介紹了Java數(shù)據(jù)結(jié)構(gòu)之紅黑樹(shù)的實(shí)現(xiàn)方法和原理,紅黑樹(shù)是一種特殊的二叉查找樹(shù),每個(gè)結(jié)點(diǎn)都要儲(chǔ)存位表示結(jié)點(diǎn)的顏色,或紅或黑,本文將通過(guò)示例為大家詳細(xì)講講紅黑樹(shù)的原理及實(shí)現(xiàn),感興趣的朋友可以了解一下

紅黑樹(shù)的說(shuō)明

紅黑樹(shù)是一種自平衡的二叉搜索樹(shù)，它在每個(gè)節(jié)點(diǎn)上增加了一個(gè)存儲(chǔ)位來(lái)表示節(jié)點(diǎn)的顏色，可以是紅色或黑色。

與 AVL 樹(shù)相比之下，紅黑樹(shù)放寬了對(duì)平衡的要求，通過(guò)犧牲一定的平衡性能來(lái)?yè)Q取更高的插入、刪除和查找操作的性能。紅黑樹(shù)的旋轉(zhuǎn)操作相對(duì)較少，因此在實(shí)際應(yīng)用中，紅黑樹(shù)更常用于需要高效的動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)，如集合、映射等。而 AVL 樹(shù)則更適用于對(duì)平衡性要求較高的場(chǎng)景，如數(shù)據(jù)庫(kù)索引等。

總的來(lái)說(shuō)，紅黑樹(shù)也是一種自平衡的二叉搜索樹(shù)，較之 AVL 樹(shù)，插入和刪除時(shí)旋轉(zhuǎn)次數(shù)更少。

紅黑樹(shù)的特性

所有節(jié)點(diǎn)都有兩種顏色：紅與黑
所有 null 視為黑色
紅色節(jié)點(diǎn)不能相鄰
根節(jié)點(diǎn)是黑色
從根節(jié)點(diǎn)到任意一個(gè)葉子節(jié)點(diǎn)，路徑中的黑色節(jié)點(diǎn)數(shù)一樣（黑色完美平衡）

前四個(gè)規(guī)則都很容易理解，接下來(lái)詳細(xì)說(shuō)明一下最后一個(gè)規(guī)則，到底什么是從根節(jié)點(diǎn)到葉子節(jié)點(diǎn)的所有路徑都要保證黑色節(jié)點(diǎn)數(shù)一樣？

如圖 1：

從根節(jié)點(diǎn)出發(fā)到葉子節(jié)點(diǎn)，首先從左子樹(shù)方向開(kāi)始，6 -> 2 -> 1 -> null ，這一條路徑的黑色節(jié)點(diǎn)一共有 3 個(gè)；現(xiàn)在從左子樹(shù)方向出發(fā)，6 -> 2 -> null ，這一條路徑的黑色節(jié)點(diǎn)一共有 3 個(gè)；現(xiàn)在從右子樹(shù)方向開(kāi)始，6 -> 8 -> null ，這一條路徑的黑色節(jié)點(diǎn)一共也是有 3 個(gè)黑色節(jié)點(diǎn)；這幾條路徑的黑色節(jié)點(diǎn)都為 3 。因此滿足紅黑樹(shù)的最后一條規(guī)則。

如圖 2：

同理，從根節(jié)點(diǎn)出發(fā)到葉子節(jié)點(diǎn)，先從左子樹(shù)方向開(kāi)始，6 -> 2 -> 1 -> null ，這一條路徑的黑色節(jié)點(diǎn)一共有三個(gè)；再?gòu)?6 -> 2 -> null ，但是這一條路徑的黑色節(jié)點(diǎn)只有 2 個(gè)黑色節(jié)點(diǎn)，不滿足紅黑樹(shù)的最后一個(gè)規(guī)則。

在構(gòu)建紅黑樹(shù)需要滿足以上規(guī)則，無(wú)論插入、刪除等都要滿足紅黑樹(shù)的特性。

紅黑樹(shù)的成員變量及其構(gòu)造方法

節(jié)點(diǎn)類 TreeNode 作為內(nèi)部類，該內(nèi)部類的成員變量有：

int key : 關(guān)鍵字，用于比較大小

Object value : 值

TreeNode left : 左節(jié)點(diǎn)

TreeNode right : 右節(jié)點(diǎn)

Color color ：顏色，默認(rèn)設(shè)置為紅色

TreeNode parent ：該節(jié)點(diǎn)的父親節(jié)點(diǎn)

該內(nèi)部類的構(gòu)造方法：

節(jié)點(diǎn)類的構(gòu)造方法主要是參數(shù)為 (int key, Object value) 的構(gòu)造方法

紅黑樹(shù)的外部類的成員變量主要為：

TreeNode root ：根節(jié)點(diǎn)，一般默認(rèn)為 null

紅黑樹(shù)的外部類的構(gòu)造方法：

主要采取默認(rèn)的參數(shù)為 null 的構(gòu)造方法

代碼如下：

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;
        //構(gòu)造方法
        public TreeNode(int key, Object value) {
            this.key = key;
            this.value = value;
        }
    }

實(shí)現(xiàn)紅黑樹(shù)的核心方法

為了更好的實(shí)現(xiàn)插入、刪除等方法，需要先實(shí)現(xiàn)基礎(chǔ)的方法 "打好基礎(chǔ)"。主要分為實(shí)現(xiàn)內(nèi)部類與外部類的核心方法。

紅黑樹(shù)內(nèi)部類的核心方法

判斷當(dāng)前節(jié)點(diǎn)是否為左孩子節(jié)點(diǎn) - isLeftChild(）

實(shí)現(xiàn)思路為：先判斷該父親節(jié)點(diǎn)是否為 null ，若 parent == null 時(shí)，則當(dāng)前節(jié)點(diǎn)為根節(jié)點(diǎn)；若 parent != null ，則需要繼續(xù)判斷 this == parent.left ，若滿足，則說(shuō)明當(dāng)前節(jié)點(diǎn)為左孩子節(jié)點(diǎn)，若不滿足，則說(shuō)明當(dāng)前節(jié)點(diǎn)為右孩子節(jié)點(diǎn)。

代碼如下：

        //判斷是否為左孩子
         public boolean isLeftChild() {
             return parent != null && parent.left == this;
         }

獲取叔叔節(jié)點(diǎn) - uncle()

叔叔節(jié)點(diǎn)即為跟父親節(jié)點(diǎn)的同一輩的節(jié)點(diǎn)，跟父親節(jié)點(diǎn)的父親是同一個(gè)父親。

實(shí)現(xiàn)思路為：需要先判斷該爺爺節(jié)點(diǎn)是否為 null 與父親節(jié)點(diǎn)是否為 null ，因?yàn)樵搩煞N情況都不具備叔叔節(jié)點(diǎn)。若以上情況都不為 null 時(shí)，接著還需要判斷當(dāng)前節(jié)點(diǎn)的父親節(jié)點(diǎn)的位置，若父親節(jié)點(diǎn)為左孩子，則叔叔節(jié)點(diǎn)為右孩子；若父親節(jié)點(diǎn)為右孩子，則叔叔節(jié)點(diǎn)為左孩子。

代碼如下：

         //獲取叔叔節(jié)點(diǎn)
         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é)點(diǎn) - brother()

跟當(dāng)前節(jié)點(diǎn)是同一輩的節(jié)點(diǎn)，同一個(gè)父親節(jié)點(diǎn)。

實(shí)現(xiàn)思路為：先判斷當(dāng)前節(jié)點(diǎn)的父親節(jié)點(diǎn)是否為 null ，若parent == null 時(shí)，說(shuō)明該節(jié)點(diǎn)不存在兄弟節(jié)點(diǎn)；若 parent != null 時(shí)，說(shuō)明該節(jié)點(diǎn)存在兄弟節(jié)點(diǎn)，然后繼續(xù)判斷當(dāng)前節(jié)點(diǎn)的位置，若當(dāng)前節(jié)點(diǎn)為左孩子，則兄弟節(jié)點(diǎn)為：parent.right ；若當(dāng)前節(jié)點(diǎn)為右孩子，則兄弟節(jié)點(diǎn)為：parent.left 。

代碼如下：

         //獲取兄弟節(jié)點(diǎn)
         public TreeNode brother() {
             if (this.parent == null) {
                 return null;
             }
             if (this.isLeftChild()) {
                 return this.parent.right;
             }else {
                 return this.parent.left;
             }
         }

紅黑樹(shù)外部類的核心方法

判斷是否為紅色節(jié)點(diǎn) isRed - (TreeNode node)

實(shí)現(xiàn)思路為：根據(jù)紅黑的規(guī)則可以知道，除了根節(jié)點(diǎn)與 null 之外，當(dāng)前節(jié)點(diǎn)的 color == RED 時(shí)，則該節(jié)點(diǎn)為紅色節(jié)點(diǎn)。

代碼如下：

    //判斷是否為紅色節(jié)點(diǎn)
    private boolean isRed(TreeNode node) {
        return node != null && node.color == RED;
    }

判斷是否為黑色節(jié)點(diǎn) isBlack - (TreeNode node)

實(shí)現(xiàn)思路為：有兩種情況下： null 或者 color == BLACK 的節(jié)點(diǎn)為黑色節(jié)點(diǎn)。

代碼如下：

    //判斷是否為黑色節(jié)點(diǎn)
    private  boolean isBlack(TreeNode node) {
        return node == null || node.color == BLACK;
    }

右旋 - rightRotate(TreeNode node)

實(shí)現(xiàn)思路為：跟 AVL 樹(shù)的右旋會(huì)有一定的區(qū)別，因?yàn)樾绿砑恿?parent 成員，所以正常右旋完之后，需要維護(hù) parent 變量。

1. parent 的處理

2. 旋轉(zhuǎn)后新根的父子關(guān)系

如圖：

現(xiàn)需要將節(jié)點(diǎn) 8 進(jìn)行右旋，假設(shè)節(jié)點(diǎn) 8 為 node ，那么先記錄節(jié)點(diǎn)5、節(jié)點(diǎn)6，nodeLeft = node.left、nodeLeftRight = nodeLeft.right 。接著更新節(jié)點(diǎn) 5 的右孩子，將其更新為節(jié)點(diǎn) 8 作為右孩子。還需要更新節(jié)點(diǎn) 8 的左孩子，將其更新為節(jié)點(diǎn) 6 作為左孩子。從表面上已經(jīng)完成右旋，但還需要維護(hù)節(jié)點(diǎn)的父親節(jié)點(diǎn) parent 。對(duì)于節(jié)點(diǎn) 6 來(lái)說(shuō)，之前的父親節(jié)點(diǎn)為節(jié)點(diǎn) 5 ，現(xiàn)在需要更新父親節(jié)點(diǎn)為節(jié)點(diǎn)8，不過(guò)需要先判斷節(jié)點(diǎn) 6 是否為 null ，若節(jié)點(diǎn) 6 為 null ，則不需要更新父親節(jié)點(diǎn)的操作。若節(jié)點(diǎn) 6 不為 null，則需要更新父親節(jié)點(diǎn)這一操作。對(duì)于節(jié)點(diǎn) 5 來(lái)說(shuō)，節(jié)點(diǎn) 5 的父親節(jié)點(diǎn)之前為節(jié)點(diǎn) 8，先父親節(jié)點(diǎn)更新為節(jié)點(diǎn) 8 的父親節(jié)點(diǎn)，因此還需要記錄節(jié)點(diǎn) 8 的父親節(jié)點(diǎn)。對(duì)于節(jié)點(diǎn) 8 來(lái)說(shuō)，將其父親節(jié)點(diǎn)更新為節(jié)點(diǎn) 5 。最后，由于現(xiàn)在的節(jié)點(diǎn)與節(jié)點(diǎn)之間時(shí)雙互的，所以還需要維護(hù)新根的父子關(guān)系，不過(guò)需要判斷節(jié)點(diǎn) 8 的父親節(jié)點(diǎn)是否為 null ，若為 parent == null 時(shí)，則說(shuō)明節(jié)點(diǎn) 5 為根節(jié)點(diǎn)，因此需要進(jìn)行 root = node.left 調(diào)整；若 parent != null ，需要判斷 node 的位置，若 node 是左孩子，那么 parent.left = node.left 進(jìn)行鏈接；若 node 是右孩子，那么 parent.right = node.left 進(jìn)行鏈接。那么現(xiàn)在就可以根據(jù)這個(gè)邏輯寫(xiě)代碼了。

最后調(diào)整完之后的圖：

代碼如下：

    //右旋
    //1.考慮旋轉(zhuǎn)后節(jié)點(diǎn)的維護(hù)parent 2.重新與上一個(gè)節(jié)點(diǎn)建立聯(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.考慮旋轉(zhuǎn)后節(jié)點(diǎn)的維護(hù)parent 2.重新與上一個(gè)節(jié)點(diǎn)建立聯(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.重新與上一個(gè)節(jié)點(diǎn)建立聯(lián)系
        if (parent == null) {
            root = nodeRight;
        } else if (parent.left == node) {
            parent.left = nodeRight;
        }else {
            parent.right = nodeRight;
        }
    }

更新、添加節(jié)點(diǎn) - put(int key，Object value)

實(shí)現(xiàn)思路為：正常刪除節(jié)點(diǎn)、更新節(jié)點(diǎn)，若遇到紅紅節(jié)點(diǎn)不平衡，則需要進(jìn)行調(diào)整

對(duì)于正常刪除、更新節(jié)點(diǎn)的邏輯為：根據(jù) key 來(lái)尋找需要更新或者刪除的節(jié)點(diǎn)、若找到了 key 的節(jié)點(diǎn)，那么直接更新該節(jié)點(diǎn)的 value 即可；若沒(méi)有找到 key 的節(jié)點(diǎn)，需要進(jìn)行添加節(jié)點(diǎn)。需要用到 parent 變量，記錄每一次的當(dāng)前節(jié)點(diǎn)，一旦當(dāng)前節(jié)點(diǎn)為 node == null 時(shí)，找到了相應(yīng)的空位，接著判斷 key 與 parent.key 的大小。若 parent.key > key ，則 parent.left = node;若 parent.key < key 則 parent.right = node;若 parent == null 時(shí)，說(shuō)明該紅黑樹(shù)為空樹(shù)，所以 root = node 。最后對(duì)于更新來(lái)說(shuō)，不會(huì)改變紅黑樹(shù)的平衡關(guān)系，對(duì)于添加完節(jié)點(diǎn)，很有可能會(huì)改變紅黑樹(shù)的平衡關(guān)系，所以需要進(jìn)行紅紅修復(fù)。

接下來(lái)詳細(xì)聊一下紅紅節(jié)點(diǎn)不平衡后進(jìn)行的調(diào)整：

插入節(jié)點(diǎn)均視為紅色

case 1：插入節(jié)點(diǎn)為根節(jié)點(diǎn)，將根節(jié)點(diǎn)變?yōu)楹谏?/li>
case 2：插入節(jié)點(diǎn)的父親若為黑色，樹(shù)的紅黑性質(zhì)不變，無(wú)需調(diào)整

插入節(jié)點(diǎn)的父親節(jié)點(diǎn)為紅色，觸發(fā)紅紅相鄰

case3：叔叔為紅色

將父親節(jié)點(diǎn)變?yōu)楹谏瑸榱吮ＷC黑色平衡，連帶的叔叔也變?yōu)楹谏?，祖父如果是黑色不變色，?huì)造成這顆子樹(shù)黑色過(guò)多，因此祖父節(jié)點(diǎn)變?yōu)榧t色。但是祖父變?yōu)榧t色，可能也會(huì)繼續(xù)觸發(fā)紅紅相鄰，因此對(duì)講祖父進(jìn)行遞歸調(diào)整。

如圖：對(duì)于 case 3 詳細(xì)說(shuō)明

插入節(jié)點(diǎn)為節(jié)點(diǎn) 1 設(shè)為 node ，該父親節(jié)點(diǎn)為節(jié)點(diǎn) 2 設(shè)為 parent 。對(duì)于 node 節(jié)點(diǎn)來(lái)說(shuō)，遇到了紅紅不平衡的情況，且該節(jié)點(diǎn) 4 即為叔叔節(jié)點(diǎn)為紅色。

調(diào)整紅黑樹(shù)平衡：需要將父親節(jié)點(diǎn)、叔叔節(jié)點(diǎn)的顏色都要置為黑色，parent.color = BLACK，uncle.color = BALCK ，將節(jié)點(diǎn) 3 即祖父節(jié)點(diǎn)的顏色置為紅色，parent.parent.color = RED ?？梢园l(fā)現(xiàn)節(jié)點(diǎn) 3 與節(jié)點(diǎn) 5 又再一次出現(xiàn)了觸發(fā)了紅紅相鄰了，那么利用遞歸來(lái)解決這一情況，一旦遇到 node == root 時(shí)，即可停止遞歸了。

最后調(diào)整后之后的圖：

case 4：叔叔為黑色

1. 父親為左孩子，插入節(jié)點(diǎn)也是左孩子，此時(shí)即 LL 不平衡

2. 父親為左孩子，插入節(jié)點(diǎn)是右孩子，此時(shí)即 LR 不平衡

3. 父親為右孩子，插入節(jié)點(diǎn)也是右孩子，此時(shí)即 RR 不平衡

4. 父親為右孩子，插入節(jié)點(diǎn)是左孩子，此時(shí)即 RL 不平衡

如圖：對(duì)于 case 4 中LL 不平衡的詳細(xì)說(shuō)明

插入節(jié)點(diǎn)為節(jié)點(diǎn) 2 設(shè)為 node，父親節(jié)點(diǎn)為節(jié)點(diǎn) 3 設(shè)為 parent ，該叔叔節(jié)點(diǎn)為 null 該節(jié)點(diǎn)為黑色，又滿足 node 為左孩子，parent 也為左孩子， LL 不平衡。該調(diào)整需要將 parent.color = BLACK，parent.parent.color = RED，把爺爺節(jié)點(diǎn) rightRotate(parent.parent) 右旋一次即可。

調(diào)整完之后的圖為：

如圖：對(duì)于 case 4 中 LR 不平衡的詳細(xì)說(shuō)明

插入節(jié)點(diǎn)為節(jié)點(diǎn) 4 設(shè)為 node，父親節(jié)點(diǎn)為節(jié)點(diǎn) 3 設(shè)為 parent，node 的叔叔節(jié)點(diǎn)為 null 所以該顏色為黑色。又 parent 是左孩子，node 是右孩子，滿足 LR 不平衡。

需要做的第一步，將 LR 轉(zhuǎn)變?yōu)?LL ，只需要將 node 節(jié)點(diǎn)左旋。

接著，將 node.color = BLACK，parent.parent.color = RED 處理，再將爺爺節(jié)點(diǎn)右旋，rightRotate(parent.parent) 即可。

調(diào)整完之后的圖：

其余的 case 4 的情況大致與以上的情況相同，所以這里不再過(guò)多贅述了。

代碼如下：

    //更新、增添節(jié)點(diǎn)
    //正常更新、刪除，遇到紅紅不平衡則需要進(jìn)行調(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;
        }
        //可能會(huì)發(fā)生紅紅不平衡，則需要調(diào)整
        fixRedRed(node);
    }
    //調(diào)整紅紅不平衡
    private void fixRedRed(TreeNode node) {
        //case1: 插入節(jié)點(diǎn)為根節(jié)點(diǎn)，將根節(jié)點(diǎn)變黑
        if(node == root) {
            node.color = BLACK;
            return;
        }
        if (isBlack(node.parent)) {
            //case2:插入節(jié)點(diǎn)的父親若為黑，樹(shù)的紅黑性質(zhì)不變，無(wú)需調(diào)整
            //無(wú)需調(diào)整
            return;
        }
        // 插入節(jié)點(diǎn)的父親為紅色，觸發(fā)紅紅相鄰
        //case3:叔叔為紅色
        TreeNode parent = node.parent;
        TreeNode grandparent = parent.parent;
        TreeNode uncle = node.uncle();
        if (isRed(uncle)) {
            //進(jìn)行變色處理即可
            //將其父親、叔叔變?yōu)楹谏瑺敔斪優(yōu)榧t色
            //若爺爺觸發(fā)了紅紅，則繼續(xù)遞歸調(diào)用該函數(shù)
            parent.color = BLACK;
            uncle.color = BLACK;
            grandparent.color = RED;
            fixRedRed(grandparent);
            return;
        }
        //case4:叔叔為黑色
        //該父親為左孩子，該插入點(diǎn)也為左孩子，則觸發(fā) ll
        if (parent.isLeftChild() && node.isLeftChild()) {
            //先將父親變?yōu)楹谏敔斪優(yōu)榧t色，再右旋轉(zhuǎn)
            parent.color = BLACK;
            grandparent.color = RED;
            rightRotate(grandparent);
        }else if (parent.isLeftChild()) {
            //該插入節(jié)點(diǎn)為右孩子、該父親為左孩子，則觸發(fā) lr
            //先左旋變?yōu)?ll 情況
            leftRotate(parent);
            node.color = BLACK;
            grandparent.color = RED;
            rightRotate(grandparent);
        } else if (!node.isLeftChild()) {
            //插入節(jié)點(diǎn)為右孩子、父親節(jié)點(diǎn)也為右孩子 rr
            parent.color = BLACK;
            grandparent.color = RED;
            leftRotate(grandparent);
        }else {
            //插入節(jié)點(diǎn)為左孩子、父親節(jié)點(diǎn)為右孩子 rl
            rightRotate(parent);
            node.color = BLACK;
            grandparent.color = RED;
            leftRotate(grandparent);
        }
    }

刪除節(jié)點(diǎn) - remove(int key)

實(shí)現(xiàn)思路：正常刪除節(jié)點(diǎn)，若遇到黑黑不平衡，則需要進(jìn)行調(diào)整

正常刪除節(jié)點(diǎn)的邏輯：先找到需要?jiǎng)h除的節(jié)點(diǎn)，為了后續(xù)的代碼簡(jiǎn)潔，因此單獨(dú)實(shí)現(xiàn)尋找刪除節(jié)點(diǎn)的方法，尋找代碼的邏輯這里就不過(guò)多展開(kāi)了。又單獨(dú)實(shí)現(xiàn)尋找刪除節(jié)點(diǎn)的替代節(jié)點(diǎn)的方法，這個(gè)方法的簡(jiǎn)單邏輯為：若刪除節(jié)點(diǎn)沒(méi)有左右孩子，則替代的節(jié)點(diǎn)為 null ;若刪除節(jié)點(diǎn)只有一個(gè)孩子，則返回不為 null 的孩子；若刪除節(jié)點(diǎn)有兩個(gè)節(jié)點(diǎn)，則找到右子樹(shù)的最小節(jié)點(diǎn)返回即可。

現(xiàn)在找到了刪除節(jié)點(diǎn)，判斷該刪除節(jié)點(diǎn)是否為 null ，若 delete == null ，則說(shuō)明沒(méi)有找到刪除節(jié)點(diǎn)，結(jié)束刪除過(guò)程；若 delete != null ，則說(shuō)明可以找到刪除節(jié)點(diǎn)，則繼續(xù)通過(guò)根據(jù)刪除節(jié)點(diǎn)查找替換節(jié)點(diǎn)的方法找到替換節(jié)點(diǎn)，最后就可以刪除節(jié)點(diǎn)了。對(duì)于刪除節(jié)點(diǎn)是一個(gè)復(fù)雜的操作，所以單獨(dú)為一個(gè)方法 doRemove(TreeNode deleted) 。

對(duì)于實(shí)現(xiàn) doRemove(TreeNode deleted) 方法，需要考慮以下情況：

case0: 對(duì)于刪除節(jié)點(diǎn)有兩個(gè)孩子來(lái)說(shuō)，需要將其轉(zhuǎn)換為只有一個(gè)孩子或者沒(méi)有孩子情況。這里用到了李代桃僵技巧，例如，需要?jiǎng)h除節(jié)點(diǎn) deleted ，替代節(jié)點(diǎn) replace ，將該兩個(gè)節(jié)點(diǎn)的關(guān)鍵字 key 與值 value 交換，那么現(xiàn)在需要?jiǎng)h除的節(jié)點(diǎn)不再是 deleted 了，而是 replace 。遞歸調(diào)用 doRemove(replace) 。這樣子就可以將兩個(gè)孩子的情況轉(zhuǎn)變?yōu)橐粋€(gè)孩子或者沒(méi)有孩子的情況了。
case1: 刪除節(jié)點(diǎn)為根節(jié)點(diǎn)的情況。先考慮根節(jié)點(diǎn)沒(méi)有左右孩子的情況，則直接將 root == null 。再考慮根節(jié)點(diǎn)有一個(gè)孩子的情況，則利用到李代桃僵的技巧，將孩子節(jié)點(diǎn)的關(guān)鍵字 key 與值 value 跟root 節(jié)點(diǎn)的關(guān)鍵字 key 與值 value 分別進(jìn)行交換，這樣刪除的節(jié)點(diǎn)就是孩子節(jié)點(diǎn)了，將根節(jié)點(diǎn)的左右孩子置為 null 即可。最后要不要考慮根節(jié)點(diǎn)有兩個(gè)孩子的情況呢？

其實(shí)是不用的，因?yàn)橐呀?jīng)通過(guò)李代桃僵的技巧將有兩個(gè)孩子節(jié)點(diǎn)轉(zhuǎn)換為一個(gè)孩子或者沒(méi)有孩子的節(jié)點(diǎn)。

case2: 刪除節(jié)點(diǎn)不為根節(jié)點(diǎn)的情況。同樣，先考慮刪除的節(jié)點(diǎn)沒(méi)有左右孩子的情況，也說(shuō)明刪除的節(jié)點(diǎn)就是葉子節(jié)點(diǎn)，所以先判斷該刪除節(jié)點(diǎn)的位置，若刪除節(jié)點(diǎn)是左孩子，那么父親節(jié)點(diǎn)的左孩子置為 null ，parent.left = null；若刪除節(jié)點(diǎn)是右孩子，那么父親節(jié)點(diǎn)的右孩子置為 null ，parent.right = null 。最后還需要將刪除節(jié)點(diǎn)的父親節(jié)點(diǎn)置為 null ，方便后續(xù)的內(nèi)存自動(dòng)回收。

接著再來(lái)考慮刪除節(jié)點(diǎn)有一個(gè)孩子的情況，刪除節(jié)點(diǎn)設(shè)為 deleted，替換節(jié)點(diǎn)設(shè)為 repalce 。先判斷 deleted 的位置，若 deleted 是左孩子，則 parent.left = repalce 進(jìn)行鏈接；若 deleted 是右孩子，則 parent.right = replace 進(jìn)行鏈接。由于紅黑樹(shù)的節(jié)點(diǎn)與節(jié)點(diǎn)之間鏈接是相互的，所以，replace 節(jié)點(diǎn)的父親節(jié)點(diǎn)需要鏈接到 parent 上， replace.parent = parent 。最后需要將刪除節(jié)點(diǎn)刪除干凈，方便內(nèi)存自動(dòng)回收，所以 deleted.left = deleted.right = deleted.parent = null 。同樣，對(duì)于刪除節(jié)點(diǎn)有兩個(gè)孩子的情況不需要考慮，已經(jīng)轉(zhuǎn)換為一個(gè)孩子或者沒(méi)有孩子的情況了。

刪除節(jié)點(diǎn)之后，很有可能會(huì)導(dǎo)致紅黑樹(shù)的性質(zhì)改變，所以刪除節(jié)點(diǎn)之前或者刪除節(jié)點(diǎn)之后，需要進(jìn)行調(diào)整，使其紅黑樹(shù)確保性質(zhì)不會(huì)發(fā)生改變。主要有以下情況：

對(duì)于刪除節(jié)點(diǎn)沒(méi)有左右孩子來(lái)說(shuō)：如果刪除節(jié)點(diǎn)的顏色是紅色，且沒(méi)有左右孩子，則直接刪除完之后，不會(huì)發(fā)生紅黑樹(shù)性質(zhì)改變；如果刪除節(jié)點(diǎn)的顏色是黑色，且沒(méi)有左右孩子，則會(huì)觸發(fā)黑黑相鄰，直接刪除會(huì)導(dǎo)致紅黑樹(shù)性質(zhì)發(fā)生改變，所以需要進(jìn)行復(fù)雜調(diào)整。

對(duì)于刪除節(jié)點(diǎn)有一個(gè)節(jié)點(diǎn)來(lái)說(shuō)：如果刪除節(jié)點(diǎn)的顏色為黑色，替換節(jié)點(diǎn)為紅色，則刪除節(jié)點(diǎn)之后，需要將替換節(jié)點(diǎn)的顏色變?yōu)楹谏纯桑蝗绻麆h除節(jié)點(diǎn)的顏色為黑色，替換節(jié)點(diǎn)也為黑色，則觸發(fā)了黑黑相鄰，需要進(jìn)行復(fù)雜的調(diào)整。

進(jìn)行復(fù)雜的調(diào)整，修復(fù)黑黑不平衡的方法 fixBlackBlack(TreeNode node)

刪除節(jié)點(diǎn)與剩下節(jié)點(diǎn)顏色都是黑色，觸發(fā)雙黑，雙黑意思是，少了一個(gè)黑。

case3: 刪除節(jié)點(diǎn)或者剩余節(jié)點(diǎn)的兄弟為紅色，此時(shí)兩個(gè)侄子定位黑色。

如圖：

刪除節(jié)點(diǎn)為節(jié)點(diǎn) 4 設(shè)為 deletde ，兄弟節(jié)點(diǎn)為節(jié)點(diǎn) 8 設(shè)為 brother，父親節(jié)點(diǎn)為節(jié)點(diǎn) 6 設(shè)為 parent ?，F(xiàn)在刪除節(jié)點(diǎn) 4 的顏色為黑色，且剩余節(jié)點(diǎn)為 null 該顏色為黑色，觸發(fā)雙黑，又兄弟節(jié)點(diǎn)為紅色。滿足以上情況時(shí)，先判斷兄弟節(jié)點(diǎn)的置為，若兄弟節(jié)點(diǎn)為右孩子，則需要將該父親節(jié)點(diǎn)進(jìn)行左旋；若兄弟節(jié)點(diǎn)為左孩子，則需要將該父親節(jié)點(diǎn)進(jìn)行右旋。旋轉(zhuǎn)完之后，需要變色處理，將父親節(jié)點(diǎn)的顏色變?yōu)榧t色，兄弟節(jié)點(diǎn)的顏色變?yōu)楹谏?。最后，繼續(xù)將刪除節(jié)點(diǎn)遞歸調(diào)用該函數(shù)。該方法的目的就是將刪除節(jié)點(diǎn)的兄弟節(jié)點(diǎn)的顏色由紅色變?yōu)楹谏?，好?duì)以下兩種情況處理。簡(jiǎn)單說(shuō)明，這個(gè)方法就是一個(gè)過(guò)度的方法。

case4: 被調(diào)整節(jié)點(diǎn)的兄弟為黑色，兩個(gè)侄子都為黑色

步驟一：將兄弟節(jié)點(diǎn)的顏色變?yōu)榧t，目的是將刪除節(jié)點(diǎn)和兄弟那邊的黑色高度同時(shí)減少1

步驟二：如果父親是紅，則需要將父親變?yōu)楹谏?，避免紅紅相鄰，此時(shí)路徑黑色節(jié)點(diǎn)數(shù)目不變。

步驟三：如果父親是黑色，說(shuō)明這條路徑則少了一個(gè)黑，再次讓父親節(jié)點(diǎn)觸發(fā)雙黑。

如圖：

調(diào)整節(jié)點(diǎn)為節(jié)點(diǎn) 1 設(shè)為 node ，兄弟節(jié)點(diǎn)為節(jié)點(diǎn) 2 設(shè)為 brother，父親節(jié)點(diǎn)為節(jié)點(diǎn) 2 設(shè)為 parent 。該情況滿足了刪除節(jié)點(diǎn)與剩余節(jié)點(diǎn)都是黑色，觸發(fā)雙黑，且兄弟節(jié)點(diǎn)的顏色也為黑色，父親節(jié)點(diǎn)的顏色為紅色。調(diào)整的方法為：將兄弟節(jié)點(diǎn)的顏色變?yōu)榧t色，將父親節(jié)點(diǎn)的顏色變?yōu)楹谏纯伞?/p>

調(diào)整完之后的圖：

如圖：

調(diào)整節(jié)點(diǎn)為節(jié)點(diǎn) 1 設(shè)為 node ，兄弟節(jié)點(diǎn)為節(jié)點(diǎn) 3 設(shè)為 brother ，父親節(jié)點(diǎn)為節(jié)點(diǎn) 2 設(shè)為 parent 。該情況滿足調(diào)整節(jié)點(diǎn)與剩余節(jié)點(diǎn)的顏色都為黑色，觸發(fā)雙黑，且兄弟節(jié)點(diǎn)的顏色也為黑色，父親節(jié)點(diǎn)也都為黑色。調(diào)整方法：將兄弟節(jié)點(diǎn)的顏色變?yōu)榧t色，再讓父親節(jié)點(diǎn)遞歸調(diào)用該函數(shù)，繼續(xù)觸發(fā)雙黑。

調(diào)整完之后的圖：

case5: 被調(diào)整節(jié)點(diǎn)的兄弟為黑色，至少有一個(gè)紅色節(jié)點(diǎn)的侄子節(jié)點(diǎn)。

如果兄弟是左孩子，左侄子是紅色，觸發(fā) LL 不平衡

如果兄弟是左孩子，右侄子是紅色，觸發(fā) LR 不平衡

如果兄弟是右孩子，右侄子是紅色，觸發(fā) RR 不平衡

如果兄弟是右孩子，左侄子是紅色，觸發(fā) RL 不平衡

如圖：觸發(fā) LL 不平衡情況

調(diào)整節(jié)點(diǎn)為節(jié)點(diǎn) 4 設(shè)為 node ，兄弟節(jié)點(diǎn)為節(jié)點(diǎn) 2 設(shè)為 brother ，父親節(jié)點(diǎn)為節(jié)點(diǎn) 3 設(shè)為 parent ，侄子節(jié)點(diǎn)為節(jié)點(diǎn) 1 。兄弟節(jié)點(diǎn)與侄子節(jié)點(diǎn)都是左孩子，且侄子節(jié)點(diǎn)為紅色。調(diào)整方法：將父親節(jié)點(diǎn)進(jìn)行右旋，再把侄子節(jié)點(diǎn)的顏色變?yōu)楹谏?，兄弟?jié)點(diǎn)的顏色變?yōu)樵瓉?lái)父親節(jié)點(diǎn)的顏色，父親節(jié)點(diǎn)的顏色變?yōu)楹谏?/p>

調(diào)整完之后的圖：

如圖：觸發(fā) LR 不平衡情況

調(diào)整節(jié)點(diǎn)為節(jié)點(diǎn) 4 設(shè)為 node ，父親節(jié)點(diǎn)為節(jié)點(diǎn) 3 設(shè)為 parent ，兄弟節(jié)點(diǎn)為節(jié)點(diǎn) 1 設(shè)為 brother ，侄子節(jié)點(diǎn)為節(jié)點(diǎn) 2 。兄弟節(jié)點(diǎn)是左孩子，侄子為右孩子，觸發(fā)了 LR 不平衡。調(diào)整方法：先將兄弟節(jié)點(diǎn)左旋，變成了 LL 不平衡情況。

再把侄子節(jié)點(diǎn)的顏色變?yōu)樵瓉?lái)父親節(jié)點(diǎn)的顏色，再到父親節(jié)點(diǎn)的顏色變?yōu)楹谏?，最后右旋父親節(jié)點(diǎn)即可。

調(diào)整完之后的圖：

還有 RR 、RL 的情況與以上的情況大致是一樣的，所以這里就不過(guò)多贅述了。

刪除節(jié)點(diǎn)的代碼如下：

    //查找刪除節(jié)點(diǎn)
    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;
            }
        }
        //若沒(méi)有找到則返回null
        return null;
    }
    //查找剩余節(jié)點(diǎn)
    private TreeNode findReplaced(TreeNode deleted) {
        //沒(méi)有孩子的情況:
        if (deleted.left == null && deleted.right == null) {
            return null;
        }
        if (deleted.left == null) {
            return deleted.right;
        }
        if (deleted.right == null) {
            return deleted.left;
        }
        //有兩個(gè)孩子的情況,找后繼節(jié)點(diǎn)即可
        TreeNode p = deleted.right;
        while(p.left != null) {
            p = p.left;
        }
        return p;
    }
    //刪除節(jié)點(diǎn)
    //正常刪除節(jié)點(diǎn)，遇到黑黑不平衡則需要進(jìn)行調(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;
        //沒(méi)有孩子的情況:
        if (replaced == null) {
            //刪除的節(jié)點(diǎn)為根節(jié)點(diǎn)情況下:
            if (deleted == root) {
                root = null;
                return;
            }else {
                if (isRed(deleted)) {
                    //無(wú)需任何操作
                }else {
                    //觸發(fā)黑黑不平衡，需要進(jìn)行復(fù)雜的操作
                    fixBlackBlack(deleted);
                }
                if (deleted.isLeftChild()) {
                    parent.left = null;
                }else {
                    parent.right = null;
                }
                deleted.parent = null;
            }
            return;
        }
        //有一個(gè)孩子的情況
        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)) {
                    //卻少一個(gè)黑色，則將替換的節(jié)點(diǎn)換為紅色即可
                    replaced.color = BLACK;
                }else {
                    //遇到黑黑不平衡情況，則需要進(jìn)行復(fù)雜調(diào)整
                    fixBlackBlack(replaced);
                }
            }
            return;
        }
        //有兩個(gè)孩子的情況,需要將用到李代桃僵技巧
        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())) {
            //先進(jìn)行旋轉(zhuǎn)調(diào)整，再換色暫時(shí)達(dá)到平衡
            if (brother.isLeftChild()) {
                rightRotate(parent);
            }else {
                leftRotate(parent);
            }
            parent.color = RED;
            brother.color = BLACK;
            fixBlackBlack(node);
            return;
        }
        //兩個(gè)侄子都為黑色
        if (brother == null) {
            fixBlackBlack(parent);
        }else {
            //case 4 兄弟是黑色，兩個(gè)侄子也是黑色
            if (isBlack(brother.left) && isBlack(brother.right)) {
                brother.color = RED;
                if (isRed(parent)) {
                    parent.color = BLACK;
                }else {
                    fixBlackBlack(parent);
                }
            }
            //case 5 兄弟是黑色，侄子有紅色
            else {
                //其中某一個(gè)侄子不為黑色
                //兄弟為左孩子、侄子為左孩子，觸發(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 轉(zhuǎn)變?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 轉(zhuǎn)變?yōu)?rr 情況再處理
                    brother.left.color = parent.color;
                    rightRotate(brother);
                    leftRotate(parent);
                    parent.color = BLACK;
                }
            }
        }
    }

實(shí)現(xiàn)紅黑樹(shù)核心方法的完整代碼

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;
        //構(gòu)造方法
        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é)點(diǎn)
         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é)點(diǎn)
         public TreeNode brother() {
             if (this.parent == null) {
                 return null;
             }
             if (this.isLeftChild()) {
                 return this.parent.right;
             }else {
                 return this.parent.left;
             }
         }
    }
    //判斷是否為紅色節(jié)點(diǎn)
    private boolean isRed(TreeNode node) {
        return node != null && node.color == RED;
    }
    //判斷是否為黑色節(jié)點(diǎn)
    private  boolean isBlack(TreeNode node) {
        return node == null || node.color == BLACK;
    }
    //右旋
    //1.考慮旋轉(zhuǎn)后節(jié)點(diǎn)的維護(hù)parent 2.重新與上一個(gè)節(jié)點(diǎn)建立聯(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.考慮旋轉(zhuǎn)后節(jié)點(diǎn)的維護(hù)parent 2.重新與上一個(gè)節(jié)點(diǎn)建立聯(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.重新與上一個(gè)節(jié)點(diǎn)建立聯(lián)系
        if (parent == null) {
            root = nodeRight;
        } else if (parent.left == node) {
            parent.left = nodeRight;
        }else {
            parent.right = nodeRight;
        }
    }
    //更新、增添節(jié)點(diǎn)
    //正常更新、刪除，遇到紅紅不平衡則需要進(jìn)行調(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;
        }
        //可能會(huì)發(fā)生紅紅不平衡，則需要調(diào)整
        fixRedRed(node);
    }
    //調(diào)整紅紅不平衡
    private void fixRedRed(TreeNode node) {
        //case1: 插入節(jié)點(diǎn)為根節(jié)點(diǎn)，將根節(jié)點(diǎn)變黑
        if(node == root) {
            node.color = BLACK;
            return;
        }
        if (isBlack(node.parent)) {
            //case2:插入節(jié)點(diǎn)的父親若為黑，樹(shù)的紅黑性質(zhì)不變，無(wú)需調(diào)整
            //無(wú)需調(diào)整
            return;
        }
        // 插入節(jié)點(diǎn)的父親為紅色，觸發(fā)紅紅相鄰
        //case3:叔叔為紅色
        TreeNode parent = node.parent;
        TreeNode grandparent = parent.parent;
        TreeNode uncle = node.uncle();
        if (isRed(uncle)) {
            //進(jìn)行變色處理即可
            //將其父親、叔叔變?yōu)楹谏?，爺爺變?yōu)榧t色
            //若爺爺觸發(fā)了紅紅，則繼續(xù)遞歸調(diào)用該函數(shù)
            parent.color = BLACK;
            uncle.color = BLACK;
            grandparent.color = RED;
            fixRedRed(grandparent);
            return;
        }
        //case4:叔叔為黑色
        //該父親為左孩子，該插入點(diǎn)也為左孩子，則觸發(fā) ll
        if (parent.isLeftChild() && node.isLeftChild()) {
            //先將父親變?yōu)楹谏?、爺爺變?yōu)榧t色，再右旋轉(zhuǎn)
            parent.color = BLACK;
            grandparent.color = RED;
            rightRotate(grandparent);
        }else if (parent.isLeftChild()) {
            //該插入節(jié)點(diǎn)為右孩子、該父親為左孩子，則觸發(fā) lr
            //先左旋變?yōu)?ll 情況
            leftRotate(parent);
            node.color = BLACK;
            grandparent.color = RED;
            rightRotate(grandparent);
        } else if (!node.isLeftChild()) {
            //插入節(jié)點(diǎn)為右孩子、父親節(jié)點(diǎn)也為右孩子 rr
            parent.color = BLACK;
            grandparent.color = RED;
            leftRotate(grandparent);
        }else {
            //插入節(jié)點(diǎn)為左孩子、父親節(jié)點(diǎn)為右孩子 rl
            rightRotate(parent);
            node.color = BLACK;
            grandparent.color = RED;
            leftRotate(grandparent);
        }
    }
    //查找刪除節(jié)點(diǎn)
    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;
            }
        }
        //若沒(méi)有找到則返回null
        return null;
    }
    //查找剩余節(jié)點(diǎn)
    private TreeNode findReplaced(TreeNode deleted) {
        //沒(méi)有孩子的情況:
        if (deleted.left == null && deleted.right == null) {
            return null;
        }
        if (deleted.left == null) {
            return deleted.right;
        }
        if (deleted.right == null) {
            return deleted.left;
        }
        //有兩個(gè)孩子的情況,找后繼節(jié)點(diǎn)即可
        TreeNode p = deleted.right;
        while(p.left != null) {
            p = p.left;
        }
        return p;
    }
    //刪除節(jié)點(diǎn)
    //正常刪除節(jié)點(diǎn)，遇到黑黑不平衡則需要進(jìn)行調(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;
        //沒(méi)有孩子的情況:
        if (replaced == null) {
            //刪除的節(jié)點(diǎn)為根節(jié)點(diǎn)情況下:
            if (deleted == root) {
                root = null;
                return;
            }else {
                if (isRed(deleted)) {
                    //無(wú)需任何操作
                }else {
                    //觸發(fā)黑黑不平衡，需要進(jìn)行復(fù)雜的操作
                    fixBlackBlack(deleted);
                }
                if (deleted.isLeftChild()) {
                    parent.left = null;
                }else {
                    parent.right = null;
                }
                deleted.parent = null;
            }
            return;
        }
        //有一個(gè)孩子的情況
        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)) {
                    //卻少一個(gè)黑色，則將替換的節(jié)點(diǎn)換為紅色即可
                    replaced.color = BLACK;
                }else {
                    //遇到黑黑不平衡情況，則需要進(jìn)行復(fù)雜調(diào)整
                    fixBlackBlack(replaced);
                }
            }
            return;
        }
        //有兩個(gè)孩子的情況,需要將用到李代桃僵技巧
        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())) {
            //先進(jìn)行旋轉(zhuǎn)調(diào)整，再換色暫時(shí)達(dá)到平衡
            if (brother.isLeftChild()) {
                rightRotate(parent);
            }else {
                leftRotate(parent);
            }
            parent.color = RED;
            brother.color = BLACK;
            fixBlackBlack(node);
            return;
        }
        //兩個(gè)侄子都為黑色
        if (brother == null) {
            fixBlackBlack(parent);
        }else {
            //case 4 兄弟是黑色，兩個(gè)侄子也是黑色
            if (isBlack(brother.left) && isBlack(brother.right)) {
                brother.color = RED;
                if (isRed(parent)) {
                    parent.color = BLACK;
                }else {
                    fixBlackBlack(parent);
                }
            }
            //case 5 兄弟是黑色，侄子有紅色
            else {
                //其中某一個(gè)侄子不為黑色
                //兄弟為左孩子、侄子為左孩子，觸發(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 轉(zhuǎn)變?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 轉(zhuǎn)變?yōu)?rr 情況再處理
                    brother.left.color = parent.color;
                    rightRotate(brother);
                    leftRotate(parent);
                    parent.color = BLACK;
                }
            }
        }
    }
}

到此這篇關(guān)于Java數(shù)據(jù)結(jié)構(gòu)之紅黑樹(shù)的實(shí)現(xiàn)方法和原理詳解的文章就介紹到這了,更多相關(guān)Java紅黑樹(shù)內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: