紅黑樹(shù)的簡(jiǎn)單實(shí)現(xiàn)（java）

最近研究紅黑樹(shù)，簡(jiǎn)單的實(shí)現(xiàn)了一個(gè)java的紅黑樹(shù)代碼，親測(cè)沒(méi)有問(wèn)題，相關(guān)實(shí)現(xiàn)的說(shuō)明都在注釋中。
實(shí)現(xiàn)時(shí)遇到的坑：
實(shí)現(xiàn)的時(shí)候遇到的坑出現(xiàn)在紅黑樹(shù)的刪除階段，網(wǎng)上各種資料都是說(shuō)刪除的時(shí)候按照二叉查找樹(shù)進(jìn)行刪除就好了，結(jié)果這塊在進(jìn)行紅黑樹(shù)平衡的時(shí)候，待刪除的節(jié)點(diǎn)是誰(shuí)，替換的節(jié)點(diǎn)是誰(shuí)很容易搞混，下面代碼在寫(xiě)刪除這塊代碼的時(shí)候特意標(biāo)明了待刪除節(jié)點(diǎn)和替換的節(jié)點(diǎn)是誰(shuí)，便于在看原理的時(shí)候可以更好的理解。

/**
 * Created by xiaosong on 2017/12/27.
 * 紅黑樹(shù)的簡(jiǎn)單實(shí)現(xiàn)
 * 紅黑樹(shù)的特性:
 * （1）每個(gè)節(jié)點(diǎn)或者是黑色，或者是紅色。
 * （2）根節(jié)點(diǎn)是黑色。
 * （3）每個(gè)葉子節(jié)點(diǎn)（NIL）是黑色。 [注意：這里葉子節(jié)點(diǎn)，是指為空(NIL或NULL)的葉子節(jié)點(diǎn)！]
 * （4）如果一個(gè)節(jié)點(diǎn)是紅色的，則它的子節(jié)點(diǎn)必須是黑色的。
 * （5）從一個(gè)節(jié)點(diǎn)到該節(jié)點(diǎn)的子孫節(jié)點(diǎn)的所有路徑上包含相同數(shù)目的黑節(jié)點(diǎn)。
 */

public class RBTree<T> {
    public static class TreeNode<T> {
        private T data;//數(shù)據(jù)值
        private TreeNode<T> left;
        private TreeNode<T> right;
        private TreeNode<T> parent;
        private Color color;
        private int value;//數(shù)據(jù)的權(quán)重

        public T getData() {
            return data;
        }

        public void setData(T data) {
            this.data = data;
        }

        public int getValue() {
            return value;
        }

        public void setValue(int value) {
            this.value = value;
        }
    }

    enum Color {
        BLACK, RED
    }

    private TreeNode<T> root;

    /**
     * 插入節(jié)點(diǎn)
     * 首先將該節(jié)點(diǎn)以二叉平衡樹(shù)的方式插入到相應(yīng)位置，然后使其滿(mǎn)足紅黑樹(shù)的性質(zhì)
     *
     * @param node
     */
    public void insert(TreeNode<T> node) {
        if (root == null) {//樹(shù)中無(wú)元素，則將插入元素當(dāng)做根結(jié)點(diǎn)
            root = node;
            root.parent = null;
            root.left = null;
            root.right = null;
            root.color = Color.BLACK;//根節(jié)點(diǎn)必是黑色
            return;
        }
        //按二叉查找樹(shù)的方式將該節(jié)點(diǎn)插入
        TreeNode<T> comNode = root;
        while (comNode != null) {
            if (comNode.value >= node.value) {
                if (comNode.left == null) {
                    comNode.left = node;
                    break;
                } else {
                    comNode = comNode.left;
                }
            } else {
                if (comNode.right == null) {
                    comNode.right = node;
                    break;
                } else {
                    comNode = comNode.right;
                }
            }
        }
        node.parent = comNode;
        node.color = Color.RED;//當(dāng)前新插入且非根節(jié)點(diǎn)初始必為紅色
        node.left = null;
        node.right = null;
        doAddBalance(node);//插入節(jié)點(diǎn)后，將紅黑樹(shù)進(jìn)行變換，使其繼續(xù)符合紅黑樹(shù)的性質(zhì)
    }

    /**
     * 刪除節(jié)點(diǎn)
     *
     * @param node
     */
    public void delete(TreeNode<T> node) {
        delete(node.value);
    }

    public void delete(int value) {
        //找到要?jiǎng)h除的節(jié)點(diǎn)
        TreeNode<T> needDelete = null;
        TreeNode<T> currentNode = root;
        while (currentNode != null) {
            if (currentNode.value == value) {
                needDelete = currentNode;
                break;
            } else if (currentNode.value > value) {
                currentNode = currentNode.left;
            } else {
                currentNode = currentNode.right;
            }
        }
        if (needDelete != null) {
            doDelete(needDelete);
        }
    }

    /**
     * 添加時(shí)進(jìn)行的紅黑樹(shù)性質(zhì)匹配操作
     *
     * @param node
     */
    private void doAddBalance(TreeNode<T> node) {
        TreeNode<T> currentNode = node;
        TreeNode<T> grandP;
        TreeNode<T> uncle;
        while (currentNode.parent != null && currentNode.parent.color == Color.RED) {//當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)為紅色或當(dāng)前節(jié)點(diǎn)為根節(jié)點(diǎn)
            grandP = currentNode.parent.parent;
            if (grandP.left == currentNode.parent) {//當(dāng)前節(jié)點(diǎn)的祖父節(jié)點(diǎn)的左孩子是當(dāng)前節(jié)點(diǎn)的父親節(jié)點(diǎn)
                uncle = currentNode.parent.parent.right;//叔叔節(jié)點(diǎn)
                if (uncle == null || uncle.color == Color.BLACK) {//叔叔節(jié)點(diǎn)是黑色
                    if (currentNode.parent.right == currentNode) {//當(dāng)前節(jié)點(diǎn)是右孩子
                        currentNode = currentNode.parent;//以當(dāng)前節(jié)點(diǎn)父親節(jié)點(diǎn)為新的當(dāng)前節(jié)點(diǎn)
                        leftRotate(currentNode);//對(duì)新的當(dāng)前節(jié)點(diǎn)進(jìn)行左旋
                    } else if (currentNode.parent.left == currentNode) {//當(dāng)前節(jié)點(diǎn)是左孩子
                        currentNode.parent.color = Color.BLACK;//將當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)設(shè)置為黑色
                        grandP.color = Color.RED;//將當(dāng)前節(jié)點(diǎn)的祖父節(jié)點(diǎn)設(shè)置為紅色
                        rightRotate(grandP);//對(duì)當(dāng)前節(jié)點(diǎn)的祖父節(jié)點(diǎn)進(jìn)行右旋
                    }
                } else {//叔叔節(jié)點(diǎn)是紅色
//                    (01) 將“父節(jié)點(diǎn)”設(shè)為黑色。
                    currentNode.parent.color = Color.BLACK;
//                    (02) 將“叔叔節(jié)點(diǎn)”設(shè)為黑色。
                    uncle.color = Color.BLACK;
//                    (03) 如果祖父節(jié)點(diǎn)不是根節(jié)點(diǎn)，將“祖父節(jié)點(diǎn)”設(shè)為“紅色”。
                    if (grandP.parent != null) {
                        grandP.color = Color.RED;
                    }
//                    (04) 將“祖父節(jié)點(diǎn)”設(shè)為“當(dāng)前節(jié)點(diǎn)”(紅色節(jié)點(diǎn))；
                    currentNode = grandP;
                }
            } else if (grandP.right == currentNode.parent) {//當(dāng)前節(jié)點(diǎn)的祖父節(jié)點(diǎn)的右孩子是當(dāng)前節(jié)點(diǎn)的父親節(jié)點(diǎn)
                uncle = currentNode.parent.parent.left;//叔叔節(jié)點(diǎn)
                if (uncle == null || uncle.color == Color.BLACK) {//叔叔節(jié)點(diǎn)是黑色
                    if (grandP.right == currentNode.parent) {//當(dāng)前節(jié)點(diǎn)的祖父節(jié)點(diǎn)的右孩子是當(dāng)前節(jié)點(diǎn)的父親節(jié)點(diǎn)
                        if (currentNode.parent.left == currentNode) {//當(dāng)前節(jié)點(diǎn)是左孩子
                            currentNode = currentNode.parent;//以當(dāng)前節(jié)點(diǎn)父親節(jié)點(diǎn)為新的當(dāng)前節(jié)點(diǎn)
                            rightRotate(currentNode);//對(duì)新的當(dāng)前節(jié)點(diǎn)進(jìn)行右旋
                        } else if (currentNode.parent.right == currentNode) {//當(dāng)前節(jié)點(diǎn)是右孩子
                            currentNode.parent.color = Color.BLACK;//將當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)設(shè)置為黑色
                            grandP.color = Color.RED;//將當(dāng)前節(jié)點(diǎn)的祖父節(jié)點(diǎn)設(shè)置為紅色
                            leftRotate(grandP);//對(duì)當(dāng)前節(jié)點(diǎn)的祖父節(jié)點(diǎn)進(jìn)行左旋
                        }
                    }
                } else {//叔叔節(jié)點(diǎn)是紅色
                    //同上邊處理方式相同
                    currentNode.parent.color = Color.BLACK;
                    uncle.color = Color.BLACK;
                    if (grandP.parent != null) {
                        grandP.color = Color.RED;
                    }
                    currentNode = grandP;
                }
            }
        }
    }

    /**
     * 刪除時(shí)進(jìn)行的紅黑樹(shù)性質(zhì)匹配操作
     *
     * @param node
     */
    public void doDeleteBalance(TreeNode<T> node) {
        TreeNode<T> currentNode = node;
        while (currentNode != null) {
            if (currentNode.color == Color.RED) {//當(dāng)前節(jié)點(diǎn)為紅色，直接涂黑處理
                currentNode.color = Color.BLACK;
                return;
            } else {//當(dāng)前節(jié)點(diǎn)為黑色，需要分情況處理
                if (currentNode.parent == null) return;//根節(jié)點(diǎn)，不做處理
                TreeNode<T> brother;//當(dāng)前節(jié)點(diǎn)的兄弟節(jié)點(diǎn)
                brother = getBrother(currentNode);//獲取當(dāng)前節(jié)點(diǎn)的兄弟節(jié)點(diǎn)
                if (node.parent.left == node) {//被刪節(jié)點(diǎn)是其父節(jié)點(diǎn)的左孩子
                    if (brother.color == Color.RED) {//若當(dāng)前節(jié)點(diǎn)的兄弟節(jié)點(diǎn)為紅色
                        currentNode.parent.color = Color.RED;//將當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)變?yōu)榧t色
                        brother.color = Color.BLACK;//將當(dāng)前節(jié)點(diǎn)的兄弟節(jié)點(diǎn)置黑
                        leftRotate(currentNode.parent);//將當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)左旋
                    } else if (brother.color == Color.BLACK) {//若當(dāng)前節(jié)點(diǎn)的兄弟節(jié)點(diǎn)為黑色
                        if ((brother.left == null || brother.left.color == Color.BLACK) && (brother.right == null || brother.right.color == Color.BLACK)) {//兄弟節(jié)點(diǎn)的左右孩子都是黑色
                            brother.color = Color.RED;//當(dāng)前節(jié)點(diǎn)的兄弟節(jié)點(diǎn)顏色變?yōu)榧t色
                            currentNode = currentNode.parent;//將父節(jié)點(diǎn)設(shè)置為當(dāng)前節(jié)點(diǎn)
                        } else if (brother.right != null && brother.right.color == Color.RED) {//兄弟節(jié)點(diǎn)的右孩子是紅色
                            brother.color = currentNode.parent.color;//將兄弟節(jié)點(diǎn)顏色置為當(dāng)前節(jié)點(diǎn)父節(jié)點(diǎn)顏色
                            currentNode.parent.color = Color.BLACK;//當(dāng)前節(jié)點(diǎn)父節(jié)點(diǎn)置黑
                            brother.right.color = Color.BLACK;//兄弟節(jié)點(diǎn)右孩子置黑
                            leftRotate(currentNode.parent);//以當(dāng)前節(jié)點(diǎn)父節(jié)點(diǎn)為支點(diǎn)左旋
                            return;
                        } else if ((brother.left != null && brother.left.color == Color.RED) && (brother.right == null || brother.right.color == Color.BLACK)) {//兄弟節(jié)點(diǎn)的左孩子是紅色，右孩子是黑色
                            brother.left.color = Color.BLACK;//將兄弟節(jié)點(diǎn)的左孩子變?yōu)楹谏?                            brother.color = Color.RED;//兄弟節(jié)點(diǎn)變?yōu)榧t色
                            rightRotate(brother);//將兄弟節(jié)點(diǎn)右旋
                        }
                    }
                } else if (node.parent.right == node) {//被刪節(jié)點(diǎn)是其父節(jié)點(diǎn)的右孩子
                    if (brother.color == Color.RED) {//若當(dāng)前節(jié)點(diǎn)的兄弟節(jié)點(diǎn)為紅色
                        currentNode.parent.color = Color.RED;//將當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)變?yōu)榧t色
                        brother.color = Color.BLACK;//將當(dāng)前節(jié)點(diǎn)的兄弟節(jié)點(diǎn)置黑
                        rightRotate(currentNode.parent);//將當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)右旋
                    } else if (brother.color == Color.BLACK) {//若當(dāng)前節(jié)點(diǎn)的兄弟節(jié)點(diǎn)為黑色
                        if ((brother.left == null || brother.left.color == Color.BLACK) && (brother.right == null || brother.right.color == Color.BLACK)) {//兄弟節(jié)點(diǎn)的左右孩子都是黑色
                            brother.color = Color.RED;//當(dāng)前節(jié)點(diǎn)的兄弟節(jié)點(diǎn)顏色變?yōu)榧t色
                            currentNode = currentNode.parent;//將父節(jié)點(diǎn)設(shè)置為當(dāng)前節(jié)點(diǎn)
                        } else if (brother.left != null && brother.left.color == Color.RED) {//兄弟節(jié)點(diǎn)的左孩子是紅色
                            brother.color = currentNode.parent.color;//將兄弟節(jié)點(diǎn)顏色置為當(dāng)前節(jié)點(diǎn)父節(jié)點(diǎn)顏色
                            currentNode.parent.color = Color.BLACK;//當(dāng)前節(jié)點(diǎn)父節(jié)點(diǎn)置黑
                            brother.left.color = Color.BLACK;//兄弟節(jié)點(diǎn)左孩子置黑
                            rightRotate(currentNode.parent);//以當(dāng)前節(jié)點(diǎn)父節(jié)點(diǎn)為支點(diǎn)右旋
                            return;
                        } else if ((brother.right != null && brother.right.color == Color.RED) && (brother.left == null || brother.left.color == Color.BLACK)) {//兄弟節(jié)點(diǎn)的右孩子是紅色，左孩子是黑色
                            brother.right.color = Color.BLACK;//將兄弟節(jié)點(diǎn)的右孩子變?yōu)楹谏?                            brother.color = Color.RED;//兄弟節(jié)點(diǎn)變?yōu)榧t色
                            leftRotate(brother);//將兄弟節(jié)點(diǎn)右旋
                        }
                    }
                }
            }
        }
    }

    public TreeNode<T> getBrother(TreeNode<T> node) {//獲取當(dāng)前節(jié)點(diǎn)的兄弟節(jié)點(diǎn)
        if (node.parent.left != node) {//重新設(shè)置X的兄弟節(jié)點(diǎn)
            return node.parent.left;
        } else {
            return node.parent.right;
        }
    }


    private void doDelete(TreeNode<T> node) {
        TreeNode<T> currentNode;//要替換的節(jié)點(diǎn)
        TreeNode<T> needDelete = node;//要?jiǎng)h除的節(jié)點(diǎn)
        //先進(jìn)行二叉排序樹(shù)的刪除操作，找到要進(jìn)行替換的節(jié)點(diǎn)
        if (node.left != null && node.right != null) {//待刪除節(jié)點(diǎn)左右子樹(shù)均在
            TreeNode<T> succed = node.left;//尋找該節(jié)點(diǎn)的后繼節(jié)點(diǎn)（找左兒子的最右子樹(shù)）
            while (succed.right != null) {
                succed = succed.right;
            }
            node.value = succed.value;//將原刪除節(jié)點(diǎn)的值替換為其后繼節(jié)點(diǎn)的值，將后繼節(jié)點(diǎn)作為待刪除節(jié)點(diǎn)
            node.data = succed.data;
            needDelete = succed;
        }
        currentNode = needDelete.left != null ? needDelete.left : needDelete.right;
        if (currentNode != null) {
            currentNode.parent = needDelete.parent;//刪除待刪除節(jié)點(diǎn)，并用其子節(jié)點(diǎn)代替
            if (needDelete.left == currentNode) {
                currentNode.parent.left = currentNode;
            } else {
                currentNode.parent.right = currentNode;
            }
            needDelete.left = needDelete.right = needDelete.parent = null;
            if (needDelete.color == Color.BLACK) {
                doDeleteBalance(node);
            }
        } else if (needDelete.parent == null) {//說(shuō)明當(dāng)前是根節(jié)點(diǎn)
            root = null;
        } else {//說(shuō)明待刪除節(jié)點(diǎn)是個(gè)葉子節(jié)點(diǎn)
            currentNode = needDelete;//將自己作為替換節(jié)點(diǎn)，同時(shí)自己也是待刪除節(jié)點(diǎn)
            if (needDelete.color == Color.BLACK) {
                doDeleteBalance(currentNode);
            }
            //平衡之后，將其刪除
            if (currentNode.parent != null) {
                if (currentNode.parent.left == currentNode) {
                    currentNode.parent.left = null;
                } else if (currentNode.parent.right == currentNode) {
                    currentNode.parent.right = null;
                }
                currentNode.parent = null;
            }
        }
    }

    public boolean isLeaf(TreeNode<T> node) {
        return node.left == null && node.right == null;
    }

    /**
     * 左旋操作，傳入的參數(shù)為要左旋的節(jié)點(diǎn)
     */
    private void leftRotate(TreeNode<T> des) {
        TreeNode<T> x = des;
        TreeNode<T> y = des.right;
        TreeNode<T> b = y.left;
        x.right = b;//將y的左孩子變?yōu)閤的右孩子
        if (b != null) {
            b.parent = x;
        }
        y.parent = x.parent;//將x的父親設(shè)置為y的父親
        if (x.parent == null) {//根節(jié)點(diǎn)
            root = y;
        } else {//非根節(jié)點(diǎn)
            if (x.parent.left == x) {//x是其父節(jié)點(diǎn)的左孩子
                x.parent.left = y;
            } else if (x.parent.right == x) {//x是其父節(jié)點(diǎn)的右孩子
                x.parent.right = y;
            }
        }
        x.parent = y;//將y設(shè)置成x的父親
        y.left = x;//將x設(shè)置為y的左孩子
    }

    /**
     * 右旋操作，傳入的參數(shù)為要右旋的節(jié)點(diǎn)
     */
    private void rightRotate(TreeNode<T> des) {
        TreeNode<T> y = des;
        TreeNode<T> x = des.left;
        TreeNode<T> b = x.right;
        y.left = b;//將x的右孩子變?yōu)閥的左孩子
        if (b != null) {
            b.parent = y;
        }
        //將y的父親設(shè)置為x的父親
        x.parent = y.parent;
        if (y.parent == null) {//根節(jié)點(diǎn)
            root = x;
        } else {//非根節(jié)點(diǎn)
            if (y.parent.left == y) {//y是其父節(jié)點(diǎn)的左孩子
                y.parent.left = x;
            } else if (y.parent.right == y) {//y是其父節(jié)點(diǎn)的右孩子
                y.parent.right = x;
            }
        }
        y.parent = x;//將x設(shè)置成y的父親
        x.right = y;//將y設(shè)置為x的右孩子
    }
}

參考資料：
1.https://www.cnblogs.com/skywang12345/p/3245399.html
2.java TreeMap的源碼

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請(qǐng)結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡(jiǎn)書(shū)系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

  • 紅黑樹(shù)是平衡二叉查找樹(shù)的一種。為了深入理解紅黑樹(shù)，我們需要從二叉查找樹(shù)開(kāi)始講起。 BST 二叉查找樹(shù)（Binary...
    kanehe閱讀 1,454評(píng)論 0贊 8
  • 樹(shù)的概述 樹(shù)是一種非常常用的數(shù)據(jù)結(jié)構(gòu)，樹(shù)與前面介紹的線(xiàn)性表，棧，隊(duì)列等線(xiàn)性結(jié)構(gòu)不同，樹(shù)是一種非線(xiàn)性結(jié)構(gòu) 1.樹(shù)的定...
    Jack921閱讀 4,753評(píng)論 1贊 31
  • 周三買(mǎi)的百合開(kāi)來(lái)了一朵其他的都還是花骨朵。周六加班的那天開(kāi)了四朵了。過(guò)了周天只有一天的周末。大概是講好每周一買(mǎi)花，...
    梵谷臉譜閱讀 569評(píng)論 0贊 50
  • 俗話(huà)說(shuō)的好，男怕入錯(cuò)行，女怕嫁錯(cuò)郎。對(duì)于后者的理解顯而易見(jiàn)，但是對(duì)于前者，就在我踏入職場(chǎng)的那一瞬，我恍然間領(lǐng)悟了。...
    everfight閱讀 559評(píng)論 3贊 6
  • 今天看見(jiàn)小伙伴們開(kāi)始發(fā)總結(jié)復(fù)盤(pán)，才驚覺(jué)五月有這樣悄悄溜走了！今天我也來(lái)對(duì)自己的五月做一下復(fù)盤(pán)吧！ 一、關(guān)于微商 五...
    萵是秀秀閱讀 561評(píng)論 0贊 0

友情鏈接更多精彩內(nèi)容