无法在Java中向二进制搜索树添加1,000,000个元素
我正在将二进制搜索树作为一项任务。
当我尝试添加1,000,000个元素时，我遇到了问题。
插入15,000个元素后，我收到错误：
线程“main”java.lang.StackOverflowError中的exception
我的代码有问题我无法找到我做错的地方。
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.right != null) { insert(node.right, value); } else { System.out.println(" Inserted " + value + " to right of Node " + node.value); node.right = new Node(value); } } } } 正如@ ajp15243所提到的，问题的直接原因是你有一个递归insert方法，它递归过深。 这将填充线程的方法调用堆栈，并触发exception。
根本问题是算法中的设计缺陷，并结合“病理”测试数据。
问题是您的insert方法不会尝试创建平衡的二叉树。 也就是说，它不会尝试创建一个树，其中节点的左子树具有（大致）与右子树相同数量的节点。
病理学是您的算法与测试数据结合产生树，其中每个节点的左子节点为null 。 （或类似的东西 …）。 最终结果是你的树非常不平衡，你必须非常深入地找到插入点。
有几种方法可以解决这个问题：
-
理想的方法是使用保持树平衡的算法重新实现树，而不依赖于插入元素的顺序。
-
“作弊”的方式是找出一个插入顺序，它将导致一个平衡的树…用当前的算法。
-
最后，您可以创建一个元素数组，对数组进行洗牌，然后以随机顺序插入元素。 这可能会导致树木不完美平衡，但病态行为的可能性将会非常小。
问题是你的insertfunction – 因为你的树很深，你的insert太深了。 没有编译器选项的Java不支持特别深的递归调用。
最好的解决方案是将递归insert函数转换为迭代。 简而言之 – 只需将函数中的代码放在循环中，在每次迭代时更改node 。
另外，我建议自平衡树 ，例如红黑树 。
请注意，您的树目前看起来像这样：
25 / \ 0 26 \ \ 1 27 \ \ 2 28 \ ... 3 ...
这将比它需要的深得多（实际上它将是O(n)高度，这反过来将导致对树的O(n)操作）。
使用自平衡树，高度永远不会超过O(log n) 。