I create a top-down splay tree but don't know how to destroy it? Since the tree can be very deep, the recursive destruction sometimes cause stack overflow. How can I get it work without changing the system stack?
How to destroy a splay tree?
I create a top-down splay tree but don't know how to destroy it? Since the tree can be very deep, the recursive destruction sometimes cause stack overflow. How can I get it work without changing the system stack?
Splay tree - Wikipedia, the free encyclopedia
Is your tree linear perhaps?
Just how complicated is your delete function?
How large is the stack frame for your function (parameters and local variables). You should be able to manage a few hundred thousand recursive steps.
Or you use your own stack to keep track of where you are, and use a simple loop in the code.
If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
If at first you don't succeed, try writing your phone number on the exam paper.
If you have a working deleteNode function, you can continually delete the root node until there's nothing left in your tree. It's not very quick, but if your delete is iterative, this will require almost no stack space.
I use my own stack instead of the system's and now it works, thank you!
A safe way to delete any binary tree, that doesn't require recursion, or large amounts of stack space, or an explicit stack is:
While root is not NULL:
If the root has a left child, perform a right rotation.
Else, delete the root, promoting its right child the new root.
This is much better than repeatedly calling a function to delete the root node (and finding a replacement from the botom of the tree), since it is O(n).
My homepage
Advice: Take only as directed - If symptoms persist, please see your debugger
Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"
