Thread: How to destroy a splay tree?

  1. #1
    Registered User
    Join Date
    Mar 2010

    Question 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?

  2. #2
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    The edge of the known universe
    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.

  3. #3
    Registered User
    Join Date
    Nov 2010
    Long Beach, CA
    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.

  4. #4
    Registered User
    Join Date
    Mar 2010
    I use my own stack instead of the system's and now it works, thank you!

  5. #5
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    New Zealand
    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"

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. object destroy
    By George2 in forum C# Programming
    Replies: 0
    Last Post: 04-19-2008, 05:13 AM
  2. Object destroy itself?
    By cminusminus in forum C++ Programming
    Replies: 28
    Last Post: 03-27-2008, 01:08 AM
  3. allocator::destroy
    By dra in forum C++ Programming
    Replies: 8
    Last Post: 03-03-2008, 11:33 AM
  4. best way to destroy object?
    By Shadow12345 in forum C++ Programming
    Replies: 11
    Last Post: 11-03-2002, 06:54 PM
  5. destroy DOS disks
    By itld in forum Linux Programming
    Replies: 29
    Last Post: 07-07-2002, 11:45 PM