作业中出现的一些问题，可能是由于我的土 bean 笔记本电脑引起的，但我对不平衡 BST(故意)何时发生 StackOverflow 感兴趣。
因此，我比较了搜索 AVL 树与不平衡 BST 的最差性能，并且搜索元素的相同方法适用于 AVL，但我在 BST 中遇到 StackOverflow 错误。 BST 最终只是一个链表，其中包含“坏数据”(按字母顺序排列的名称；大约 10000 个)，那么在调用entryExists 的次数是多少时，它会产生该错误？
我知道在最坏的情况下，不平衡的 BST 显然比 AVL 的性能差得多，但我想限制搜索查询以获取某种时间数。
[我不认为发布实际代码是必要的，但如果有人需要它，我会上传它 - 据我所知，这不仅仅是我在做无限递归(两者使用相同的方法)。 ]
最佳答案
当单个线程上有太多 Activity 方法调用(即正在进行中)时，就会发生堆栈溢出。
每个方法调用都需要一个堆栈帧来保存调用的局部变量，以及一些调用内务信息。 (通常是返回地址和保存的栈顶指针。)线程的堆栈帧保存在线程的堆栈上。它具有固定大小(在创建线程时确定)。默认值取决于 JVM 和命令行开关，但通常为 1Mbytes。
有四种情况可能导致堆栈溢出:
- 无限递归肯定会导致堆栈溢出(除非其他东西首先终止代码)。
- 有限递归太深。例如，如果您的代码递归地遍历列表，那么如果列表足够长，它很可能会溢出堆栈。 (递归不是无限的。)
- 复杂且涉及非常深的调用堆栈的非递归代码。
- 非递归代码，其调用链涉及带有大量局部变量的方法。
情况 3 和 4 不太可能发生，但如果您的线程是使用异常小的线程堆栈创建的，则情况更有可能发生。 (例如，如果您试图节省线程堆栈内存。)
<小时/>就您而言，情况 2 是您担心的问题。如果您的树适当平衡，这种情况就不会发生。然而，如果一棵树极度不平衡，它可能会非常深。将其与递归搜索树的算法相结合，足够深的树可能会导致堆栈溢出。
注意:这不是无限递归。相反，它是递归算法和具有不幸“形状”的数据结构的组合。
关于java - 什么时候抛出 StackOverflowError ？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/43559359/