因此，我使用节点为红黑树编写了以下代码。我在第一次插入时遇到了问题，因为为了旋转或重新着色，以便红色项目始终有黑色的父项，我无法检查它们的“叔叔”，因为它们没有任何父项。错误为：
线程“main”java.lang.nullpointerexception中出现异常：无法读取字段“right”，因为“x”为null
错误在rotateright（x.parent==y.parent）和fix方法中，我想，如果有人能帮上忙，我会很感激的。其他方法似乎都很有效。
导入java.io.*；导入java.util.random；
公共类二进制搜索树<key，item>{

BSTreeNode root;        // root of binary search tree
int numItems;

class BSTreeNode {

    Key key;            // key associated with the item stored at node
    Item item;          // item stored at node
    BSTreeNode left;    // left child
    BSTreeNode right;   // right child
    BSTreeNode parent;  // node's parent
    int height;         // node's height
    int N;              // number of descendants
    boolean isRed;      // red or black

    // create new node
    BSTreeNode(Key key, Item item, BSTreeNode parent) {
        this.key = key;
        this.item = item;
        this.parent = parent;
        this.height = 1;
        this.N = 1;
        this.isRed = true;
    }
}

// search for item with key; returns the last node on the search path 
BSTreeNode searchNode(Key key) {
    BSTreeNode v = root;
    BSTreeNode pv = null; // parent of v
    while (v != null) {
        int c = key.compareTo(v.key);  // compare with the key of node v
        pv = v;
        if (c < 0) {
            v = v.left;
        } else if (c > 0) {
            v = v.right;
        } else {
            return v; // item found; return node that contains it
        }
    }
    return pv; // item not found; return last node on the search path
}

// search for item with key
public Item search(Key key) {
    if (root == null) {
        return null; // tree is empty
    }
    BSTreeNode v = searchNode(key);
    int c = key.compareTo(v.key);
    if (c == 0) {
        return v.item;    // item found
    } else {
        return null;      // item not found
    }
}

// return the height of a node x; if x is null return 0
private int getHeight(BSTreeNode x) {
    if (x == null) {
        return 0;
    } else {
        return x.height;
    }
}

// return the number of descendants of a node x; if x is null return 0
private int getN(BSTreeNode x) {
    if (x == null) {
        return 0;
    } else {
        return x.N;
    }
}

// update the height and the number of descendants of a node
private void updateNode(BSTreeNode x) {
    int leftHeight = getHeight(x.left);
    int rightHeight = getHeight(x.right);
    int bf = leftHeight - rightHeight; // balance factor
    if (bf < 0) {
        x.height = rightHeight + 1;
    } else {
        x.height = leftHeight + 1;
    }

    int leftN = getN(x.left);
    int rightN = getN(x.right);
    x.N = leftN + rightN + 1;
}

// update the height v's ancestors
private void updatePath(BSTreeNode v) {
    BSTreeNode u = v;
    while (u != null) {
        updateNode(u);
        u = u.parent;
    }
}

// return the height of the binary search tree
int getTreeHeight() {
    return getHeight(root);
}

boolean isRed(BSTreeNode x) {
    while (x != null && x.isRed) {
        return true;
    }
    return false;
}

// insert item with key and return inserted node
BSTreeNode insertNode(Key key, Item item) {
    if (root == null) { // tree is empty
        root = new BSTreeNode(key, item, null);
        return root;
    }

    BSTreeNode v = searchNode(key); // v is the last node on the search path
    int c = key.compareTo(v.key);
    if (c == 0) { // key already exists in v; overwrite node's item with new item
        v.item = item;
        return v;
    }

    BSTreeNode u = new BSTreeNode(key, item, v); // new node becomes child of v
    if (c < 0) {
        v.left = u;
    } else {
        v.right = u;
    }

    return u;
}

//mporei na vgali nullPointer
public BSTreeNode sibling (BSTreeNode x) {
    BSTreeNode y = x.parent;
    //y = x.parent;
    while (y != null) {
        if (y.left == x) {
            return y.right;
        } else {
            return y.left;
        }
    }
    return null;
}

public void recolor(BSTreeNode x) {
    x.isRed = !x.isRed;
}

// insert item with key
public void insert(Key key, Item item) {
    BSTreeNode v = insertNode(key, item);
    updatePath(v);
    numItems++;
    fix(v);
}

private void fix(BSTreeNode x) {
    if (x == root) return;

    BSTreeNode y, z, w, uncle;
    y = x.parent;
    if (!isRed(y)) {
        updatePath(y);
        return;
    }
    z = w = y.parent;
    uncle = sibling(y);

    while (true && z != null) {
        if (!isRed(uncle)) { // uncle black p1
            if (uncle == y.parent.right) {
                if (x == y.right) {
                    rotateRight(x);
                    updateNode(x);
                }
                rotateRight(y);
                updateNode(y);
                updateNode(w);  
                recolor(y);
                recolor(w);
            }
            else {
                if (x == y.left) {
                    rotateLeft(x);
                    updateNode(x);
                }
                rotateLeft(x);
                updateNode(y); 
                updateNode(w);
                recolor(y);
                recolor(w);
            }
        }
        if (x.parent == null) {
            recolor(x);
        }
        recolor(z);
        recolor(y);
        recolor(uncle);
    }
}

private BSTreeNode rotateLeft (BSTreeNode x) {
    BSTreeNode y = x.right;
    x.right = y.left;
    if (x.right != null) {
        x.right.parent = x;
    }
    y.left = x;
    y.parent = x.parent;
    if (x.parent != null) {
        if (x.parent.left == x) {
            x.parent.left = y;
        } else {
            x.parent.right = y;        
        }
    }
    x.parent = y;
    updateNode(x);
    updateNode(y);
    return y;
}

private BSTreeNode rotateRight(BSTreeNode y) {
    BSTreeNode x = y.left;
    y.left = x.right;
    if (y.left != null) {
        y.left.parent = y;
    }
    x.right = y;
    x.parent = y.parent;
    if (y.parent != null) {
        if (y.parent.left == y) {
        y.parent.left = x;
        } else {
        y.parent.right = x;
        }
    }
    y.parent = x;
    updateNode(y);
    updateNode(x);
    return x;
}

// inorder traversal: prints the key of each node
void printNode(BSTreeNode v, int level) {
    if (v == null) {
        return;
    }
    printNode(v.right, level + 1);
    for (int i = 0; i < level; i++) {
        System.out.print("\t");
    }
    String s = "";
    if (isRed(v)) s = " (red) "; else s = " (black)";
    System.out.println("" + v.key + "[" + v.height + "," + v.N + "]" + s);
    printNode(v.left, level + 1);
}

// print binary tree
public void print() {
    System.out.println("Printing binary search tree");
    System.out.println("");
    printNode(root, 0);
    System.out.println("");
}