0

Something that came up in an assignment, and could be due to my potato laptop, but I was interested in when a StackOverflow happens for an unbalanced BST (on purpose).

So I'm comparing the worst performance searching an AVL tree vs unbalanced BST, and the same method that searches for an element works for the AVL, but I get StackOverflow error for the BST. The BST ends up just being a linked list with the "bad data" being fed into it (alphabetical names; around 10000), so at what number of calls to entryExists would it produce that error?

I know the unbalanced BST obviously performs much worse than an AVL at worst case, but I want to limit the search queries to acquire some kind of time number.

[I don't think posting the actual code is necessary, but if anyone needs it, I'll upload it - as far as I can tell, it's not just me doing infinite recursion (same method used for both).]

Paul12596
  • 300
  • 3
  • 13
  • It gets thrown when your code keeps calling itself, like when a method simply calls itself again. Most likely you messed up the return condition on some recursion your code is doing. – GhostCat Apr 22 '17 at 12:46
  • Here, on this site, a stackoverflow exception manifests in downvotes, because people think you have not done any prior research, for example by entering the exception name into a search engine – GhostCat Apr 22 '17 at 12:47
  • That's right @StephenC, my bad! But unfortunately I cannot edit it now. So I delete and re-post the comment again. Thanks for correcting me. – STaefi Apr 22 '17 at 13:08
  • StackOverflowError is a situation due to infinite number of method calls happens in your program. By infinite I mean more than the permitted size of the stack of the method calls. This situation mostly happens when you implement an algorithm in a recursive way and the initial condition is not properly implemented to stop the self calls. If you implemented your algorithm correctly you can increase the stack size to support the needed number of recursive calls. Here you can find out How: http://stackoverflow.com/questions/3700459/how-to-increase-the-java-stack-size – STaefi Apr 22 '17 at 13:09

1 Answers1

2

A stack overflow happens in a situation where there are too many method calls active (i.e. in progress) on a single thread.

Each method call requires a stack frame to hold the local variables for the call, and some call house-keeping information. (Typically a return address, and a saved top-of-stack pointer.) The stack frames for a thread are held on the thread's stack. This has a fixed size (determined when the thread is created). The default depends on the JVM and the command line switches, but it is typically 1Mbytes.

There are four scenarios which can lead to a stack overflow:

  1. Infinite recursion is guaranteed to lead to stack overflow (unless something else terminates the code first).
  2. Finite recursion that is too deep. For instance, if your code traverse a list recursively, it will most likely overflow the stack is the list is long enough. (The recursion is not infinite.)
  3. Non-recursive code that is complicated and involves a very deep call stack.
  4. Non-recursive code with a call-chain involving methods with a large number of local variables.

Scenarios 3 and 4 are unlikely, but they can be more likely if your threads are created with unusually small thread stacks. (For example, if you are trying to economize on thread stack memory.)

In your case, scenario 2 is your worry. This should not happen if your tree is properly balanced. However if an tree is extremely unbalanced, it can be extremely deep. Combine that with an algorithm which recurses to (say) search the tree, and a deep enough tree can lead to stack overflow.

Note: this is NOT infinite recursion. Rather it is the combination of a recursive algorithm and a data structure that has an unfortunate "shape".

Stephen C
  • 698,415
  • 94
  • 811
  • 1,216