Java紅黑樹

首先創(chuàng)建樹結構

class Node {
    final boolean RED = true;
    final boolean BLACK = false;
    int key;
    boolean color;
    Node left, right, parent;

    public Node(int key) {
        this.key = key;
        this.color = RED;
    }

    @Override
    public String toString() {
        String str = "[";
        if (this.color == RED) {
            str += "紅色";
        } else {
            str += "黑色";
        }
        return str + "," + this.key + "]";
    }
}

創(chuàng)建紅黑樹類

public class RBTree {
    final boolean RED = true;
    final boolean BLACK = false;
    Node root = null;
    
}

插入方法

      public void insertNode(int key){
        Node node = new Node(key);
        if(root == null){    //判斷根節(jié)點是否為空，如果為空，當前節(jié)點即為根節(jié)點，并把顏色賦成黑色
            root = node;
            root.color = BLACK;
        }else{            //不是根節(jié)點，尋找可以當做父節(jié)點的節(jié)點
            Node cur = root;
            Node parent = null;
            do {
                parent = cur;
                if(parent.key >= key){
                    cur = cur.left;
                }else{
                    cur = cur.right;
                }
            }while (cur != null);  //找到父節(jié)點之后，判斷是在左邊還是右邊
            node.parent = parent;
            if(parent.key >= key){
                parent.left = node;
            }else{
                parent.right = node;
            }
        }
        balanceSelf(node); //每次插入要進行自平衡
    }

在插入的時候，要進行自平衡，那么就要涉及到幾個原子操作：左旋/右旋，變色


左旋

圖中的左旋，我們注意到，只有3個地方變了(不要糾結顏色，原子操作互不干擾)
①X的父親變成了Z的父親
②Z的左子樹從A變成了X
③X的右子樹變成了A
左旋方法就很簡單了

  public void rotateToLeft(Node node) {//把node看成X
        Node x = node;
        Node z = x.right;
        if (z.left != null) {
            // 如果z的左子樹不為空
            z.left.parent = x;

        }
        x.right = z.left;
        if (x.parent == null) {//如果是根節(jié)點
            root = z;
        } else if (x.parent.left == x) {//如果x是x父親的左子樹
            x.parent.left = z;
        } else {
            x.parent.right = z;
        }
        z.parent = x.parent;
        //建立z和x之間的父子關系
        x.parent = z;
        z.left = x;
    }

右旋和左旋相左就是


右旋

右旋

     public void rotateToRight(Node node) {
        Node x = node;
        Node y = node.left;
        if (y.right != null) {
            y.right.parent = x;
        }
        x.left = y.right;
        if (x.parent == null) {
            root = y;
        } else if (x.parent.left == x) {
            x.parent.left = y;
        } else {
            x.parent.right = x;
        }
        y.parent = x.parent;
        x.parent = y;
        y.right = x;
    }

能左旋右旋變色，就可以進行自平衡了

  private void balanceSelf(Node node) {
        Node parent,grandParent;
        //父存在并紅色，因為剛插入的數據是紅色，所以形成了紅 紅，要進行自平衡
        while((parent = node.parent)!= null && parent.color == RED){
            grandParent = parent.parent;
            //判斷父是祖父的左子樹還是右子樹，目的是為了找出叔叔節(jié)點
            if(parent == grandParent.left){
                Node uncle = grandParent.right;

                //case 1 : 叔叔存在并紅色
                if(null != uncle && uncle.color == RED){
                    uncle.color = BLACK;
                    parent.color = BLACK;
                    grandParent.color = RED;
                    node = grandParent;  //把祖父又當成X向上回溯
                    continue;
                }

                //case 2 : 叔叔黑，當前節(jié)點是右孩子
                if(parent.right == node){
                    rotateToLeft(parent);
                    Node temp = parent;
                    parent = node;
                    node = temp;
                }

                //case 3 : 叔叔黑，當前是左孩子
                parent.color = BLACK;
                grandParent.color = RED;
                rotateToRight(grandParent);

            }else{
                Node uncle = grandParent.left;

                //case 1 : 叔叔存在并紅色
                if(null != uncle && uncle.color == RED){
                    uncle.color = BLACK;
                    parent.color = BLACK;
                    grandParent.color = RED;
                    node = grandParent;  //把祖父又當成X向上回溯
                    continue;
                }

                //case 2 : 叔叔黑，當前節(jié)點是左孩子
                if(parent.left == node){
                    rotateToRight(parent);
                    Node temp = parent;
                    parent = node;
                    node = temp;
                }

                //case 3 : 叔叔黑，當前是右孩子
                parent.color = BLACK;
                grandParent.color = RED;
                rotateToLeft(grandParent);

            }
        }
        root.color = BLACK; // 根節(jié)點黑色
    }

刪除------
全代碼

public class RBTree {
    final boolean RED = true;
    final boolean BLACK = false;
    Node root = null;

    public void insertNode(int key) {
        Node node = new Node(key);
        if (root == null) {    //判斷根節(jié)點是否為空，如果為空，當前節(jié)點即為根節(jié)點，并把顏色賦成黑色
            root = node;
            root.color = BLACK;
        } else {            //不是根節(jié)點，尋找可以當做父節(jié)點的節(jié)點
            Node cur = root;
            Node parent = null;
            do {
                parent = cur;
                if (parent.key >= key) {
                    cur = cur.left;
                } else {
                    cur = cur.right;
                }
            } while (cur != null);  //找到父節(jié)點之后，判斷是在左邊還是右邊
            node.parent = parent;
            if (parent.key >= key) {
                parent.left = node;
            } else {
                parent.right = node;
            }
        }
        balanceSelf(node);
    }

    public void rotateToLeft(Node node) {//把node看成X
        Node x = node;
        Node z = x.right;
        if (z.left != null) {
            // 如果z的左子樹不為空
            z.left.parent = x;

        }
        x.right = z.left;
        if (x.parent == null) {//如果是根節(jié)點
            root = z;
        } else if (x.parent.left == x) {//如果x是x父親的左子樹
            x.parent.left = z;
        } else {
            x.parent.right = z;
        }
        z.parent = x.parent;
        //建立z和x之間的父子關系
        x.parent = z;
        z.left = x;
    }

    public void rotateToRight(Node node) {
        Node x = node;
        Node y = node.left;
        if (y.right != null) {
            y.right.parent = x;
        }
        x.left = y.right;
        if (x.parent == null) {
            root = y;
        } else if (x.parent.left == x) {
            x.parent.left = y;
        } else {
            x.parent.right = x;
        }
        y.parent = x.parent;
        x.parent = y;
        y.right = x;
    }


    private void balanceSelf(Node node) {
        Node parent, grandParent;
        //父存在并紅色，因為剛插入的數據是紅色，所以形成了紅 紅，要進行自平衡
        while ((parent = node.parent) != null && parent.color == RED) {
            grandParent = parent.parent;
            //判斷父是祖父的左子樹還是右子樹，目的是為了找出叔叔節(jié)點
            if (parent == grandParent.left) {
                Node uncle = grandParent.right;

                //case 1 : 叔叔存在并紅色
                if (null != uncle && uncle.color == RED) {
                    uncle.color = BLACK;
                    parent.color = BLACK;
                    grandParent.color = RED;
                    node = grandParent;  //把祖父又當成X向上回溯
                    continue;
                }

                //case 2 : 叔叔黑，當前節(jié)點是右孩子
                if (parent.right == node) {
                    rotateToLeft(parent);
                    Node temp = parent;
                    parent = node;
                    node = temp;
                }

                //case 3 : 叔叔黑，當前是左孩子
                parent.color = BLACK;
                grandParent.color = RED;
                rotateToRight(grandParent);

            } else {
                Node uncle = grandParent.left;

                //case 1 : 叔叔存在并紅色
                if (null != uncle && uncle.color == RED) {
                    uncle.color = BLACK;
                    parent.color = BLACK;
                    grandParent.color = RED;
                    node = grandParent;  //把祖父又當成X向上回溯
                    continue;
                }

                //case 2 : 叔叔黑，當前節(jié)點是左孩子
                if (parent.left == node) {
                    rotateToRight(parent);
                    Node temp = parent;
                    parent = node;
                    node = temp;
                }

                //case 3 : 叔叔黑，當前是右孩子
                parent.color = BLACK;
                grandParent.color = RED;
                rotateToLeft(grandParent);

            }
        }
        root.color = BLACK; // 根節(jié)點黑色
    }

    public void inOrder() {
        this.inOrder(root);
    }

    public void inOrder(Node node) {
        if (node == null) {
            return;
        }
        inOrder(node.left);
        System.out.println(node);
        inOrder(node.right);
    }
}


class Node {
    final boolean RED = true;
    final boolean BLACK = false;
    int key;
    boolean color;
    Node left, right, parent;

    public Node(int key) {
        this.key = key;
        this.color = RED;
    }

    @Override
    public String toString() {
        String str = "[";
        if (this.color == RED) {
            str += "紅色";
        } else {
            str += "黑色";
        }
        return str + "," + this.key + "]";
    }
}
?著作權歸作者所有,轉載或內容合作請聯(lián)系作者
【社區(qū)內容提示】社區(qū)部分內容疑似由AI輔助生成，瀏覽時請結合常識與多方信息審慎甄別。
平臺聲明：文章內容（如有圖片或視頻亦包括在內）由作者上傳并發(fā)布，文章內容僅代表作者本人觀點，簡書系信息發(fā)布平臺，僅提供信息存儲服務。

友情鏈接更多精彩內容