// 定義一個(gè) Node 類，表示樹中的每個(gè)節(jié)點(diǎn)
class Node {
    int key; // 鍵值
    int color; // 顏色，0 表示黑色，1 表示紅色
    Node left; // 左孩子
    Node right; // 右孩子
    Node parent; // 父親

    // 構(gòu)造方法，初始化鍵值和顏色
    public Node(int key, int color) {
        this.key = key;
        this.color = color;
        this.left = null;
        this.right = null;
        this.parent = null;
    }
}

// 定義一個(gè) RBTree 類，表示一棵紅黑樹
class RBTree {
    Node root; // 根節(jié)點(diǎn)

    // 構(gòu)造方法，初始化根節(jié)點(diǎn)為 null
    public RBTree() {
        this.root = null;
    }

    // 輔助方法，對(duì)某個(gè)節(jié)點(diǎn)進(jìn)行左旋操作
    public void leftRotate(Node x) {
        // 設(shè) y 是 x 的右孩子
        Node y = x.right;
        // 將 y 的左孩子設(shè)為 x 的右孩子，并將 y 的左孩子的父親設(shè)為 x
        x.right = y.left;
        if (y.left != null) {
            y.left.parent = x;
        }
        // 將 x 的父親設(shè)為 y 的父親，并更新 y 的父親的相應(yīng)孩子指針
        y.parent = x.parent;
        if (x.parent == null) { // 如果 x 是根節(jié)點(diǎn)，那么將 y 設(shè)為新的根節(jié)點(diǎn)
            this.root = y;
        } else if (x == x.parent.left) { // 如果 x 是其父節(jié)點(diǎn)的左孩子，那么將 y 設(shè)為其父節(jié)點(diǎn)的左孩子
            x.parent.left = y;
        } else { // 如果 x 是其父節(jié)點(diǎn)的右孩子，那么將 y 設(shè)為其父節(jié)點(diǎn)的右孩子
            x.parent.right = y;
        }
        // 將 y 的左孩子設(shè)為 x，并將 x 的父親設(shè)為 y
        y.left = x;
        x.parent = y;
    }

    // 輔助方法，對(duì)某個(gè)節(jié)點(diǎn)進(jìn)行右旋操作
    public void rightRotate(Node x) {
        // 設(shè) y 是 x 的左孩子
        Node y = x.left;
        // 將 y 的右孩子設(shè)為 x 的左孩子，并將 y 的右孩子的父親設(shè)為 x
        x.left = y.right;
        if (y.right != null) {
            y.right.parent = x;
        }
        // 將 x 的父親設(shè)為 y 的父親，并更新 y 的父親的相應(yīng)孩子指針
        y.parent = x.parent;
        if (x.parent == null) { // 如果 x 是根節(jié)點(diǎn)，那么將 y 設(shè)為新的根節(jié)點(diǎn)
            this.root = y;
        } else if (x == x.parent.right) { // 如果 x 是其父節(jié)點(diǎn)的右孩子，那么將 y 設(shè)為其父節(jié)點(diǎn)的右孩子
            x.parent.right = y;
        } else { // 如果 x 是其父節(jié)點(diǎn)的左孩子，那么將 y 設(shè)為其父節(jié)點(diǎn)的左孩子
            x.parent.left = y;
        }
        // 將 y 的右孩子設(shè)為 x，并將 x 的父親設(shè)為 y
        y.right = x;
        x.parent = y;
    }

    // 輔助方法，用 v 節(jié)點(diǎn)替換 u 節(jié)點(diǎn)
    public void transplant(Node u, Node v) {
        if (u.parent == null) { // 如果 u 是根節(jié)點(diǎn)，那么將 v 設(shè)為新的根節(jié)點(diǎn)
            this.root = v;
        } else if (u == u.parent.left) { // 如果 u 是其父節(jié)點(diǎn)的左孩子，那么將 v 設(shè)為其父節(jié)點(diǎn)的左孩子
            u.parent.left = v;
        } else { // 如果 u 是其父節(jié)點(diǎn)的右孩子，那么將 v 設(shè)為其父節(jié)點(diǎn)的右孩子
            u.parent.right = v;
        }
        if (v != null) { // 如果 v 不是 null，那么將 v 的父親設(shè)為 u 的父親
            v.parent = u.parent;
        }
    }

    // 輔助方法，返回以某個(gè)節(jié)點(diǎn)為根的子樹中最小鍵值的節(jié)點(diǎn)
    public Node minimum(Node x) {
        while (x.left != null) { // 沿著左孩子指針一直向下，直到找到最左邊的節(jié)點(diǎn)
            x = x.left;
        }
        return x;
    }

    // 輔助方法，返回以某個(gè)節(jié)點(diǎn)為根的子樹中最大鍵值的節(jié)點(diǎn)
    public Node maximum(Node x) {
        while (x.right != null) { // 沿著右孩子指針一直向下，直到找到最右邊的節(jié)點(diǎn)
            x = x.right;
        }
        return x;
    }

    // 輔助方法，返回樹中鍵值等于 key 的第一個(gè)找到的節(jié)點(diǎn)
    public Node search(int key) {
        Node x = this.root; // 從根節(jié)點(diǎn)開始查找
        while (x != null && x.key != key) { // 如果 x 不是 null，并且 x 的鍵值不等于 key，那么繼續(xù)查找
            if (key < x.key) { // 如果 key 小于 x 的鍵值，那么在 x 的左子樹中查找
                x = x.left;
            } else { // 如果 key 大于 x 的鍵值，那么在 x 的右子樹中查找
                x = x.right;
            }
        }
        return x; // 返回找到的節(jié)點(diǎn)或 null
    }

    // 向樹中插入一個(gè)鍵值為 key 的節(jié)點(diǎn)
    public void insert(int key) {
        Node z = new Node(key, 1); // 創(chuàng)建一個(gè)新節(jié)點(diǎn) z，并將其顏色設(shè)為紅色
        Node y = null; // 初始化 y 為 null，用于記錄 z 的父節(jié)點(diǎn)
        Node x = this.root; // 初始化 x 為根節(jié)點(diǎn)，用于查找 z 的插入位置
        while (x != null) { // 如果 x 不是 null，那么繼續(xù)查找
            y = x; // 將 y 設(shè)為當(dāng)前的 x 節(jié)點(diǎn)
            if (z.key < x.key) { // 如果 z 的鍵值小于 x 的鍵值，那么在 x 的左子樹中查找
                x = x.left;
            } else { // 如果 z 的鍵值大于或等于 x 的鍵值，那么在 x 的右子樹中查找
                x = x.right;
            }
        }
        z.parent = y; // 將 z 的父節(jié)點(diǎn)設(shè)為 y
        if (y == null) { // 如果 y 是 null，說明樹是空的，那么將 z 設(shè)為根節(jié)點(diǎn)
            this.root = z;
        } else if (z.key < y.key) { // 如果 z 的鍵值小于 y 的鍵值，那么將 z 設(shè)為 y 的左孩子
            y.left = z;
        } else { // 如果 z 的鍵值大于或等于 y 的鍵值，那么將 z 設(shè)為 y 的右孩子
            y.right = z;
        }
        insertFixup(z); // 調(diào)用插入修復(fù)方法，恢復(fù)紅黑性質(zhì)
    }

   // 插入修復(fù)方法，用于恢復(fù)紅黑樹的性質(zhì)
public void insertFixup(Node z) {
    // 當(dāng) z 的父節(jié)點(diǎn)存在且是紅色時(shí)，需要進(jìn)行調(diào)整
    while (z.parent != null && z.parent.color == Color.RED) {
        // 判斷 z 的父節(jié)點(diǎn)是其祖父節(jié)點(diǎn)的左孩子還是右孩子
        if (z.parent == z.parent.parent.left) {
            // 如果是左孩子，那么獲取 z 的叔叔節(jié)點(diǎn)（祖父節(jié)點(diǎn)的右孩子）
            Node y = z.parent.parent.right;
            // 根據(jù)叔叔節(jié)點(diǎn)的顏色分為三種情況
            if (y != null && y.color == Color.RED) {
                // 如果叔叔節(jié)點(diǎn)是紅色，那么將父節(jié)點(diǎn)和叔叔節(jié)點(diǎn)都變?yōu)楹谏?，將祖父?jié)點(diǎn)變?yōu)榧t色，并將祖父節(jié)點(diǎn)作為新的 z 節(jié)點(diǎn)，繼續(xù)向上調(diào)整
                z.parent.color = Color.BLACK;
                y.color = Color.BLACK;
                z.parent.parent.color = Color.RED;
                z = z.parent.parent;
            } else {
                // 如果叔叔節(jié)點(diǎn)是黑色或 NIL，那么需要進(jìn)行旋轉(zhuǎn)操作
                if (z == z.parent.right) {
                    // 如果 z 是其父節(jié)點(diǎn)的右孩子，那么先對(duì)父節(jié)點(diǎn)進(jìn)行左旋，然后交換 z 和其父節(jié)點(diǎn)的角色
                    z = z.parent;
                    leftRotate(z);
                }
                // 如果 z 是其父節(jié)點(diǎn)的左孩子，那么對(duì)祖父節(jié)點(diǎn)進(jìn)行右旋，然后將父節(jié)點(diǎn)變?yōu)楹谏?，將祖父?jié)點(diǎn)變?yōu)榧t色，并結(jié)束調(diào)整
                z.parent.color = Color.BLACK;
                z.parent.parent.color = Color.RED;
                rightRotate(z.parent.parent);
            }
        } else {
            // 如果是右孩子，那么獲取 z 的叔叔節(jié)點(diǎn)（祖父節(jié)點(diǎn)的左孩子），與上面類似，只是左右對(duì)稱
            Node y = z.parent.parent.left;
            // 根據(jù)叔叔節(jié)點(diǎn)的顏色分為三種情況
            if (y != null && y.color == Color.RED) {
                // 如果叔叔節(jié)點(diǎn)是紅色，那么將父節(jié)點(diǎn)和叔叔節(jié)點(diǎn)都變?yōu)楹谏?，將祖父?jié)點(diǎn)變?yōu)榧t色，并將祖父節(jié)點(diǎn)作為新的 z 節(jié)點(diǎn)，繼續(xù)向上調(diào)整
                z.parent.color = Color.BLACK;
                y.color = Color.BLACK;
                z.parent.parent.color = Color.RED;
                z = z.parent.parent;
            } else {
                // 如果叔叔節(jié)點(diǎn)是黑色或 NIL，那么需要進(jìn)行旋轉(zhuǎn)操作
                if (z == z.parent.left) {
                    // 如果 z 是其父節(jié)點(diǎn)的左孩子，那么先對(duì)父節(jié)點(diǎn)進(jìn)行右旋，然后交換 z 和其父節(jié)點(diǎn)的角色
                    z = z.parent;
                    rightRotate(z);
                }
                // 如果 z 是其父節(jié)點(diǎn)的右孩子，那么對(duì)祖父節(jié)點(diǎn)進(jìn)行左旋，然后將父節(jié)點(diǎn)變?yōu)楹谏瑢⒆娓腹?jié)點(diǎn)變?yōu)榧t色，并結(jié)束調(diào)整
                z.parent.color = Color.BLACK;
                z.parent.parent.color = Color.RED;
                leftRotate(z.parent.parent);
            }
        }
    }
    // 最后確保根節(jié)點(diǎn)是黑色
    this.root.color = Color.BLACK;
}

// 從樹中刪除一個(gè)鍵值為 key 的節(jié)點(diǎn)
public void delete(int key) {
    Node z = search(key); // 查找要?jiǎng)h除的節(jié)點(diǎn)
    if (z == null) { // 如果沒有找到，直接返回
        return;
    }
    Node x; // 用于記錄替換后的新節(jié)點(diǎn)
    Node y = z; // 用于記錄要?jiǎng)h除或移動(dòng)的原始節(jié)點(diǎn)
    Color yOriginalColor = y.color; // 用于記錄 y 的原始顏色
    if (z.left == null) { // 如果 z 沒有左孩子，那么用其右孩子替換它
        x = z.right;
        transplant(z, z.right);
    } else if (z.right == null) { // 如果 z 沒有右孩子，那么用其左孩子替換它
        x = z.left;
        transplant(z, z.left);
    } else { // 如果 z 有兩個(gè)孩子，那么用其后繼節(jié)點(diǎn)（右子樹中最小的節(jié)點(diǎn)）替換它
        y = minimum(z.right); // 找到 z 的后繼節(jié)點(diǎn)
        yOriginalColor = y.color; // 記錄 y 的原始顏色
        x = y.right; // 記錄 y 的右孩子
        if (y.parent == z) { // 如果 y 是 z 的右孩子，那么直接將 x 的父親設(shè)為 y
            x.parent = y;
        } else { // 如果 y 不是 z 的右孩子，那么用 x 替換 y，并將 y 的右孩子設(shè)為 z 的右孩子
            transplant(y, y.right);
            y.right = z.right;
            y.right.parent = y;
        }
        transplant(z, y); // 用 y 替換 z，并將 y 的左孩子設(shè)為 z 的左孩子
        y.left = z.left;
        y.left.parent = y;
        y.color = z.color; // 將 y 的顏色設(shè)為 z 的顏色
    }
    if (yOriginalColor == Color.BLACK) { // 如果 y 的原始顏色是黑色，那么就存在過度黑問題，需要調(diào)用刪除修復(fù)方法，恢復(fù)紅黑性質(zhì)
        deleteFixup(x);
    }
}
  
  // 刪除修復(fù)方法，用于恢復(fù)紅黑性質(zhì)
public void deleteFixup(Node x) {
    // 當(dāng) x 不是根節(jié)點(diǎn)，并且是黑色時(shí)，需要進(jìn)行調(diào)整
    while (x != this.root && x.color == Color.BLACK) {
        // 判斷 x 是其父節(jié)點(diǎn)的左孩子還是右孩子
        if (x == x.parent.left) {
            // 如果是左孩子，那么獲取 x 的兄弟節(jié)點(diǎn)（父節(jié)點(diǎn)的右孩子）
            Node w = x.parent.right;
            // 根據(jù)兄弟節(jié)點(diǎn)的顏色分為四種情況
            if (w.color == Color.RED) {
                // 如果兄弟節(jié)點(diǎn)是紅色，那么將兄弟節(jié)點(diǎn)變?yōu)楹谏?，將父?jié)點(diǎn)變?yōu)榧t色，并對(duì)父節(jié)點(diǎn)進(jìn)行左旋，然后更新兄弟節(jié)點(diǎn)
                w.color = Color.BLACK;
                x.parent.color = Color.RED;
                leftRotate(x.parent);
                w = x.parent.right;
            }
            if (w.left.color == Color.BLACK && w.right.color == Color.BLACK) {
                // 如果兄弟節(jié)點(diǎn)的兩個(gè)孩子都是黑色或 NIL，那么將兄弟節(jié)點(diǎn)變?yōu)榧t色，并將父節(jié)點(diǎn)作為新的 x 節(jié)點(diǎn)，繼續(xù)向上調(diào)整
                w.color = Color.RED;
                x = x.parent;
            } else {
                // 如果兄弟節(jié)點(diǎn)的兩個(gè)孩子不都是黑色或 NIL，那么需要進(jìn)行旋轉(zhuǎn)操作
                if (w.right.color == Color.BLACK) {
                    // 如果兄弟節(jié)點(diǎn)的右孩子是黑色或 NIL，那么將兄弟節(jié)點(diǎn)變?yōu)榧t色，將兄弟節(jié)點(diǎn)的左孩子變?yōu)楹谏?，并?duì)兄弟節(jié)點(diǎn)進(jìn)行右旋，然后更新兄弟節(jié)點(diǎn)
                    w.color = Color.RED;
                    w.left.color = Color.BLACK;
                    rightRotate(w);
                    w = x.parent.right;
                }
                // 如果兄弟節(jié)點(diǎn)的右孩子是紅色，那么將父節(jié)點(diǎn)的顏色賦給兄弟節(jié)點(diǎn)，將父節(jié)點(diǎn)和兄弟節(jié)點(diǎn)的右孩子都變?yōu)楹谏?duì)父節(jié)點(diǎn)進(jìn)行左旋，然后結(jié)束調(diào)整
                w.color = x.parent.color;
                x.parent.color = Color.BLACK;
                w.right.color = Color.BLACK;
                leftRotate(x.parent);
                x = this.root; // 將 x 設(shè)為根節(jié)點(diǎn)，結(jié)束循環(huán)
            }
        } else {
            // 如果是右孩子，那么獲取 x 的兄弟節(jié)點(diǎn)（父節(jié)點(diǎn)的左孩子），與上面類似，只是左右對(duì)稱
            Node w = x.parent.left;
            // 根據(jù)兄弟節(jié)點(diǎn)的顏色分為四種情況
            if (w.color == Color.RED) {
                // 如果兄弟節(jié)點(diǎn)是紅色，那么將兄弟節(jié)點(diǎn)變?yōu)楹谏?，將父?jié)點(diǎn)變?yōu)榧t色，并對(duì)父節(jié)點(diǎn)進(jìn)行右旋，然后更新兄弟節(jié)點(diǎn)
                w.color = Color.BLACK;
                x.parent.color = Color.RED;
                rightRotate(x.parent);
                w = x.parent.left;
            }
            if (w.right.color == Color.BLACK && w.left.color == Color.BLACK) {
                // 如果兄弟節(jié)點(diǎn)的兩個(gè)孩子都是黑色或 NIL，那么將兄弟節(jié)點(diǎn)變?yōu)榧t色，并將父節(jié)點(diǎn)作為新的 x 節(jié)點(diǎn)，繼續(xù)向上調(diào)整
                w.color = Color.RED;
                x = x.parent;
            } else {
                // 如果兄弟節(jié)點(diǎn)的兩個(gè)孩子不都是黑色或 NIL，那么需要進(jìn)行旋轉(zhuǎn)操作
                if (w.left.color == Color.BLACK) {
                    // 如果兄弟節(jié)點(diǎn)的左孩子是黑色或 NIL，那么將兄弟節(jié)點(diǎn)變?yōu)榧t色，將兄弟節(jié)點(diǎn)的右孩子變?yōu)楹谏?，并?duì)兄弟節(jié)點(diǎn)進(jìn)行左旋，然后更新兄弟節(jié)點(diǎn)
                    w.color = Color.RED;
                    w.right.color = Color.BLACK;
                    leftRotate(w);
                    w = x.parent.left;
                }
                // 如果兄弟節(jié)點(diǎn)的左孩子是紅色，那么將父節(jié)點(diǎn)的顏色賦給兄弟節(jié)點(diǎn)，將父節(jié)點(diǎn)和兄弟節(jié)點(diǎn)的左孩子都變?yōu)楹谏?，并?duì)父節(jié)點(diǎn)進(jìn)行右旋，然后結(jié)束調(diào)整
                w.color = x.parent.color;
                x.parent.color = Color.BLACK;
                w.left.color = Color.BLACK;
                rightRotate(x.parent);
                x = this.root; // 將 x 設(shè)為根節(jié)點(diǎn)，結(jié)束循環(huán)
            }
        }
    }
    // 最后確保根節(jié)點(diǎn)是黑色
    this.root.color = Color.BLACK;
}