Использование стека для хранения узлов трепа при добавлении новых узлов.Почему я получаю исключение EmptyStackException?

Question

Я строю класс Treap в Java.Ниже моя функция для добавления новых узлов в трепе.Процесс таков: переход вниз к основанию трепа (при добавлении каждого узла в пути к локальному стеку), вначале меня беспокоит только структура 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 - относитсяна вызов reheap в нижней части функции add 137 - относится к циклу while частной функции reheap 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))).<- это будет после переучивания конечно. </p>

Answer 1

Вам необходимо выполнить проверку пустого стека перед просмотром стека!

while(!stack.isEmpty() && added.priority > stack.peek().priority) {...}