添加新节点时使用栈存储treap节点。为什么我会收到 EmptyStackException?
Using a stack to store treap nodes when adding new nodes. Why am I getting an EmptyStackException?
我正在 Java 建造一个 treap class。下面是我将新节点添加到 treap 的函数。这个过程是:向下遍历到 treap 的底部(同时将路径中的每个节点添加到本地堆栈)首先只担心 BST 结构,然后,一旦到达底部,我将通过旋转重新建立堆不变性通过利用我建立的堆栈。
听起来应该可以,但我一直收到 EmptyStackException。一旦调用私有 "reheap" 函数,就会发生此异常。
add 函数适用于添加到 treap 的第一个节点,例如我这样做:
testTree.add (4 ,19);
但是在第二次添加节点时失败,就像我调用:
testTree.add (2 ,31);
这是完整的错误:
Exception in thread "main" java.util.EmptyStackException
at java.util.Stack.peek(Unknown Source)
at classes.Treap.reheap(Treap.java:137)
at classes.Treap.add(Treap.java:130)
at classes.Treap.main(Treap.java:220)
130 -- 指add函数底部调用reheap
137 -- 指的是私有reheap函数的while循环
220 -- 指的是我尝试在 main 中添加新节点。
我试过改变 reheap 函数中的条件,但无济于事。
boolean add(E key, int priority) {
Stack<Node<E>> stack = new Stack<Node<E>>();
if(root == null) {
Node<E> newroot = new Node<E>(key, priority);
root = newroot;
stack.push(root);
return true;
}else {
Node<E> current = new Node<E>(root.data, root.priority); //placeholder, used for traversing
Node<E> added = new Node<E>(key, priority); //node to be added to the treap
if(this.find(key) == true){
return false;
}else {
if(current.right == null && current.left == null) {
stack.push(current);
if(key.compareTo(current.data) < 0)
current = current.left;
else
current = current.right;
}
else {
while(current.right != null || current.left != null) {
if(key.compareTo(current.data) < 0) {
stack.push(current);
current = current.left;
}
if(key.compareTo(current.data) > 0) {
stack.push(current);
current = current.right;
}
}
}
if(key.compareTo(stack.peek().data) < 0)
stack.peek().left = added;
else if(key.compareTo(stack.peek().data) > 0)
stack.peek().right = added;
if(!stack.isEmpty())
this.reheap(added, stack);
return true;
}
}
}
private boolean reheap(Node<E> added, Stack<Node<E>> stack) {
while(added.priority > stack.peek().priority && !stack.isEmpty()) {
if(stack.peek().right == added)
stack.peek().rotateLeft();
else
stack.peek().rotateRight();
stack.pop();
}
return true;
}
在第二次调用 ( testTree.add (2 ,31)
; ) 之后,我应该得到一个具有结构 ( Node(2, null, Node(4)) ) 的 treap。 <-- 这当然是在重新堆积之后。
您需要在查看堆栈之前进行空堆栈检查!
while(!stack.isEmpty() && added.priority > stack.peek().priority) {...}
我正在 Java 建造一个 treap class。下面是我将新节点添加到 treap 的函数。这个过程是:向下遍历到 treap 的底部(同时将路径中的每个节点添加到本地堆栈)首先只担心 BST 结构,然后,一旦到达底部,我将通过旋转重新建立堆不变性通过利用我建立的堆栈。
听起来应该可以,但我一直收到 EmptyStackException。一旦调用私有 "reheap" 函数,就会发生此异常。
add 函数适用于添加到 treap 的第一个节点,例如我这样做: testTree.add (4 ,19); 但是在第二次添加节点时失败,就像我调用: testTree.add (2 ,31);
这是完整的错误:
Exception in thread "main" java.util.EmptyStackException
at java.util.Stack.peek(Unknown Source)
at classes.Treap.reheap(Treap.java:137)
at classes.Treap.add(Treap.java:130)
at classes.Treap.main(Treap.java:220)
130 -- 指add函数底部调用reheap 137 -- 指的是私有reheap函数的while循环 220 -- 指的是我尝试在 main 中添加新节点。
我试过改变 reheap 函数中的条件,但无济于事。
boolean add(E key, int priority) {
Stack<Node<E>> stack = new Stack<Node<E>>();
if(root == null) {
Node<E> newroot = new Node<E>(key, priority);
root = newroot;
stack.push(root);
return true;
}else {
Node<E> current = new Node<E>(root.data, root.priority); //placeholder, used for traversing
Node<E> added = new Node<E>(key, priority); //node to be added to the treap
if(this.find(key) == true){
return false;
}else {
if(current.right == null && current.left == null) {
stack.push(current);
if(key.compareTo(current.data) < 0)
current = current.left;
else
current = current.right;
}
else {
while(current.right != null || current.left != null) {
if(key.compareTo(current.data) < 0) {
stack.push(current);
current = current.left;
}
if(key.compareTo(current.data) > 0) {
stack.push(current);
current = current.right;
}
}
}
if(key.compareTo(stack.peek().data) < 0)
stack.peek().left = added;
else if(key.compareTo(stack.peek().data) > 0)
stack.peek().right = added;
if(!stack.isEmpty())
this.reheap(added, stack);
return true;
}
}
}
private boolean reheap(Node<E> added, Stack<Node<E>> stack) {
while(added.priority > stack.peek().priority && !stack.isEmpty()) {
if(stack.peek().right == added)
stack.peek().rotateLeft();
else
stack.peek().rotateRight();
stack.pop();
}
return true;
}
在第二次调用 ( testTree.add (2 ,31)
; ) 之后,我应该得到一个具有结构 ( Node(2, null, Node(4)) ) 的 treap。 <-- 这当然是在重新堆积之后。
您需要在查看堆栈之前进行空堆栈检查!
while(!stack.isEmpty() && added.priority > stack.peek().priority) {...}