Почему этот рекурсивный метод дает мне StackOverFlowError в дереве AVL?

Question

В настоящее время я реализую пользовательское дерево AVL в Java, которое поддерживает дубликаты элементов. Внизу я предоставил класс AvlTreeNode, который показывает, как дубликаты поддерживаются переменными «next» и «prev».

Я реализовал метод removeAll (), который лениво удаляет каждое вхождение переданного ему параметра, и он прекрасно работает.

Я попытался сделать то же самое с методом findAll (), который находит каждое вхождение переданного ему параметра и добавляет каждое вхождение в ArrayList (т. Е. Если дерево AVL содержит пять значений 7, все 5 значения будут добавлены в ArrayList, давая: [7, 7, 7, 7, 7]). Это бросает StackOverFlowError, хотя, и я не могу понять, почему.

Оба метода используют закрытый метод firstMatch (), который находит первое вхождение элемента, а затем использует приватную версию метода внутри методов publi c для рекурсии. Код выглядит следующим образом:

private AvlTreeNode<AnyType> firstMatch(AnyType x) {

        AvlTreeNode<AnyType> test = root;

        while (test != null) {
            int compareResult = x.compareTo(test.element);

            if (compareResult < 0)
                test = test.left;
            else if (compareResult > 0)
                test = test.right;
            else if (test.isActive)
                return test;    // Match
        }
        return null;
    }

    public Collection<AnyType> findAll(AnyType x) {
        ArrayList <AnyType> theColl = new ArrayList<>();
        AvlTreeNode<AnyType> p = firstMatch(x);

        findAll(theColl, x, p);

        return theColl;

    }

    private void findAll(ArrayList<AnyType> arrList, AnyType x, AvlTreeNode<AnyType> n )
    {
        if(n != null)
        {
            int compare = n.element.compareTo(x);

            if (compare == 0){
                arrList.add(n.element);

                if(n.next != null){
                    n = n.next;
                    findAll(arrList, x, n;
                }
                else if(n.prev != null){
                    n = n.prev;
                    findAll(arrList, x, n);
                }
            }
            else if (compare > 0){
                n = n.right;
                findAll(arrList, x, n);

            }
            else{
                n = n.left;
                findAll(arrList, x , n);
            }

        }
    }

А мой AvlTreeNode выглядит следующим образом:

 private static class AvlTreeNode<AnyType> {

        AvlTreeNode(AnyType theElement) {
            this(theElement, null, null, 1);
        }

        AvlTreeNode(AnyType theElement, AvlTreeNode<AnyType> lt, AvlTreeNode<AnyType> rt, int counter) {
            element = theElement;
            left = lt;
            right = rt;
            height = 0;
            isActive = true;
            count = counter;
        }

        AvlTreeNode<AnyType> insertDuplicate(AnyType x) {
            if (this.next == null) {
                AvlTreeNode n = new AvlTreeNode<>(x, null, null, count++);
                prev = next = n;
                n.prev = n.next = this;
                header = this;
                return this;
            }
            else if (!header.prev.isActive) {
                AvlTreeNode n = new AvlTreeNode<>(x, null, null, count++);
                prev = next = n;
                n.prev = n.next = this;
                n.header = header;
                return n;
            }
            else {
                AvlTreeNode n = new AvlTreeNode<>(x, null, null, count++);
                n.prev = header.prev;
                n.next = header;
                header.prev = header.prev.next = n;
                n.header = header;
                return this;
            }
        }


        AvlTreeNode<AnyType> removeDuplicate() {
            if (isActive) {
                isActive = false;
                next.right = right;
                next.left = left;
                next.header = header;
                right = left = header = null;
                return next;
            }
            return this;
        }

        AnyType element;
        AvlTreeNode<AnyType> left;
        AvlTreeNode<AnyType> right;
        AvlTreeNode<AnyType> next, prev;
        AvlTreeNode<AnyType> header;
        int height;
        boolean isActive;
        int count;
    }


    private AvlTreeNode<AnyType> root;

Любая помощь по этому вопросу была бы НЕМЕДЛЕННО признательна!

Answer 1

У меня была эта проблема несколько раз. Проблема слишком велика, чтобы использовать рекурсию. Попробуйте использовать другой алгоритм. (Я разместил это в комментариях, но мне не разрешено, потому что я новичок здесь)