为什么这种递归方法在AVL树上给我一个StackOverFlowError？

Question

我目前正在Java中实现一个支持重复元素的自定义AVL树。我在底部提供了AvlTreeNode类，该类显示了“ next”和“ prev”变量如何支持重复项。

我已经实现了removeAll（）方法，该方法懒惰地删除传递给它的参数的每次出现，并且工作得很好。

我试图用findAll（）方法做同样的事情，该方法查找传递给它的参数的每个匹配项，并将每个匹配项添加到ArrayList中（即，如果AVL树包含5个值为7的值，则将添加所有5个值到ArrayList，给出：[7，7，7，7，7]）。这虽然引发了StackOverFlowError，但我不知道为什么。

两种方法都使用私有的firstMatch（）方法，该方法查找该项目的第一个匹配项，然后在公共方法中使用该方法的私有版本进行递归。代码如下：

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