Java 数据结构篇-实现红黑树的核心方法

public class RedBlackTree<Key extends Comparable<Key>, Value> {
 
    private Node root;
 
    private class Node {
        Key key;
        Value value;
        int N; // 以该节点为根的子树中的节点数
        boolean color; // 节点的颜色
        Node left, right;
 
        public Node(Key key, Value value, int N, boolean color) {
            this.key = key;
            this.value = value;
            this.N = N;
            this.color = color;
            this.left = this.right = null;
        }
    }
 
    // 其他需要实现的方法...
 
    // 以下是实现红黑树插入方法的核心函数
    private Node rotateLeft(Node h) {
        if (h != null) {
            Node x = h.right;
            h.right = x.left;
            x.left = h;
            x.N = h.N;
            h.N = 1 + size(h.left) + size(h.right);
            return x;
        }
        return h;
    }
 
    private Node rotateRight(Node h) {
        if (h != null) {
            Node x = h.left;
            h.left = x.right;
            x.right = h;
            x.N = h.N;
            h.N = 1 + size(h.left) + size(h.right);
            return x;
        }
        return h;
    }
 
    private void flipColors(Node h) {
        h.color = !h.color;
        h.left.color = !h.left.color;
        h.right.color = !h.right.color;
    }
 
    public void put(Key key, Value value) {
        root = put(root, key, value);
        root.color = BLACK;
    }
 
    // 插入方法的辅助函数
    private Node put(Node h, Key key, Value value) {
        if (h == null) return new Node(key, value, 1, RED);
 
        int cmp = key.compareTo(h.key);
        if (cmp < 0) h.left = put(h.left, key, value);
        else if (cmp > 0) h.right = put(h.right, key, value);
        else h.value = value;
 
        if (isRed(h.right) && !isRed(h.left)) h = rotateLeft(h);
        if (isRed(h.left) && isRed(h.left.left)) h = rotateRight(h);
        if (isRed(h.left) && isRed(h.right)) flipColors(h);
 
        h.N = size(h.left) + size(h.right) + 1;
        return h;
    }
 
    // 辅助函数，判断节点是否为红色
    private boolean isRed(Node x) {
        if (x == null) return false;
        return