如何使用三个参数将节点插入到 Treap 上

Question

我在将 Treapnode 插入 Treap 时遇到问题。它接受 3 个参数。添加（E 键，P 优先级，treapnode x）。我尝试了很多方法，但总是出现空指针异常。

我尝试检查左右树中的空情况。

private TreapNode add (E key, P priority, TreapNode x)

        throws ElementFoundException {

    // For You To Complete

    int compare = key.compareTo(x.element());

    if (x == null){

        return new TreapNode(key, priority);

    }

    //root is larger than the key

    else if (compare == 0) {

        throw new ElementFoundException("Element was found, and tree was not changed.");

    } else if (compare < 0) {

        if (x.left() == null) {

         //TreapNode y = new TreapNode(key, priority);

            TreapNode y = x.left;

            x.left = y.right;

            y.right = x;

            return y;

        } else {

            x.left = add(key, priority, x.left());

        }

    }

    //root is smaller than the key

    else if (compare > 0) {

        if (x.right() == null) {

            //TreapNode y = new TreapNode(key, priority);

            TreapNode z = x.right;

            x.right = z.left;

            z.left = x;

            return z;

        }

    }

    return x;

}

Answer 1

这是你做错了x.right()。情况也是如此x.left()if (x.right() == null) {        //TreapNode y = new TreapNode(key, priority);        TreapNode z = x.right; // z = null        x.right = z.left;  // z.left will throw NPE应该if (x.right() == null) {   x.right() = new TreapNode(key, priority);   return x; // return parent node }另外，我认为这也是一个错误的比较，int不能null但是Integer类可以int compare = key.compareTo(x.element());  //comoareTo return an int if (x == null){  // does not make sense to compare and int type to Object type  ....}