Treap Add 功能的实现

Question

你好，所以我正在研究我的 treap 方法，该方法需要一个 Stack 来跟踪它所经过的节点列表，并通过在最后执行旋转列表来维护堆属性。但是，当我运行此代码时，它为我的旋转方法提供了 nullPointerException() 。不确定我做错了什么。这是我的节点和 Treap 类的链接。 我的节点和 Treap 类代码

Answer 1

这是一个有效的异常，因为您无法对左子节点为空的节点执行右旋转，反之亦然。

这就是我要做的：

public Node<E> rotateRight() {
    if (this.left == null) {
        throw new IllegalStateException("Cannot perform a right rotation with a null left node")
    } 

    Node<E> newRoot = this.left; // this will be new rooth after rotation, which is why it cannot be null
    this.left = newRoot.right;
    newRoot.right = this;

    return newRoot;

}

// 那么对于rotateLeft() 方法反之亦然