二叉搜索树与AVLTree问题

Question

我正在为分配制作二叉搜索树和AVL树。

尝试向二叉搜索树添加1,000,000个元素时遇到问题，但我可以向AVL树添加键->值对。（AVLTree没有问题）

如果我平衡二叉搜索树，与AVL树没有区别？？（如果我平衡二叉搜索树，它变成AVLTREE有什么意义？）

插入15,000个元素后，我从二叉搜索树中得到错误：线程“main”java.lang.StackOverflowError中出现异常

项目定义:
使用这些测试和为朴素二叉搜索树创建的代码，比较AVL树和朴素二叉搜索树在搜索、插入和删除时间以及长序列上的树平衡方面的性能。您应该在树中运行多达1000000个元素的测试。

public class BinaryTreeExample {

    public static void main(String[] args) {
        new BinaryTreeExample().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);

        insert3(rootnode, 50_000);

        for (int i = 0; i < 150_000; i++)
            insert3(rootnode, i);
        System.out.println("Bittaaa");
        // System.out.println(getNodesCount(rootnode));

    }

    protected int getNodesCount(Node root) {

        if (root != null) {
            int counter = 1;
            counter += getNodesCount(root.left);
            counter += getNodesCount(root.right);
            return counter;
        } else
            return 0;

    }

    void insert3(Node node, int value) {
        if (value < node.value) {
            if (node.left == null)
                node.left = new Node(value);
            else
                insert3(node.left, value);
        } else {
            if (node.right == null)
                node.right = new Node(value);
            else
                insert3(node.right, value);
        }
    }


    public void printInOrder(Node node) {
        if (node != null) {
            printInOrder(node.left);
            System.out.println("  Traversed " + node.value);
            printInOrder(node.right);
        }
    }
}

Answer 1

StackOverflowError是因为您递归实现了insert。在这种情况下，如果您添加元素1，2，3，...，15000，那么您的树将具有15000级别，并且您的递归将溢出您的堆栈。必须执行它，您将不会得到StackOverflowError。应该是像

void insert (Node node, int value) {
    while (true) {
        if (value < node.value) {
            if (node.left == null){
                node.left = new Node(value);
                break;
            }
            else
                node = node.left;
        }
        else {
            if (node.right == null){
                node.right = new Node(value);
                break;
            }
            else
                node = node.right;
        }
    }
}

但整个方法并不是最优的。上面的行为不是您期望的BST的行为。您希望级别为日志(15000)而不是15000。您将通过使用平衡的结构来实现这一点。它仍将是BST树，但附加的约束是级别为O（log n）。因此，一旦您完成了BST，一定要尝试AVL：）