无法在Java中向二进制搜索树添加1,000,000个元素

Question

我正在将二进制搜索树作为一项任务.
当我尝试添加1,000,000个元素时,我遇到了问题.
插入15,000个元素后我收到错误:

线程"main"中的异常java.lang.StackOverflowError

我的代码有问题我无法找到我做错的地方.

public class BinarytreeInsert {

    public static void main(String[] args) {
        new BinarytreeInsert().run();
    }

    static class Node {

        Node left;
        Node right;
        int value;

        public Node(int value) {
            this.value = value;
        }
    }

    public void run() {
        Node rootnode = new Node(25);
        System.out.println("Building tree with root value " + rootnode.value);
        System.out.println("=================================");
        for(int i = 0 ; i<1_000_000;i++)
            insert(rootnode, i);

    }


    public void insert(Node node, int value) {
        if (value < node.value) {
            if (node.left != null) {
                insert(node.left, value);
            } else {
                System.out.println("  Inserted " + value + " to left of Node " + node.value);
                node.left = new Node(value);
            }
        } else if (value > node.value) {
            if (node.right != null) {
                insert(node.right, value);
            } else {
                System.out.println("  Inserted " + value + " to right of Node " + node.value);
                node.right = new Node(value);
            }
        }
    }
}

Answer 1

正如@ ajp15243所提到的,问题的直接原因是你有一个递归insert方法过于递归.这将填充线程的方法调用堆栈,并触发异常.

根本问题是算法中的设计缺陷,并结合"病理"测试数据.

问题是您的insert方法不会尝试创建平衡的二叉树.也就是说,它不会尝试创建一个树,其中节点的左子树具有(大致)与右子树相同数量的节点.

病理学是您的算法与测试数据相结合产生一个树,其中每个节点的左子节点null.(或类似的东西 ...).最终结果是你的树非常不平衡,你必须非常深入地找到插入点.

有几种方法可以解决这个问题:

• 理想的方法是使用保持树平衡的算法重新实现树,而不依赖于插入元素的顺序.

• "作弊"的方法是找出一个插入顺序,它将导致一个平衡的树...用当前的算法.

• 最后,您可以创建一个元素数组,对数组进行洗牌,然后以随机顺序插入元素.这可能会导致树木不完全平衡,但病态行为的可能性将会非常小.