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

Question

我在将 Treapnode 插入 treap 时遇到问题。它接受 3 个参数。 add(E key, P priority, 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但是Integerclass可以是

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
  ....
}

要深入了解，请阅读此页 https://www.geeksforgeeks.org/binary-search-tree-set-1-search-and-insertion/

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

How to insert a node onto a Treap with three arguments

java

binary

binary-tree

treap

binary-search-tree