Like Tree2Likes
  • 1 Post By anduril462
  • 1 Post By iMalc

How to destroy a splay tree?

This is a discussion on How to destroy a splay tree? within the C Programming forums, part of the General Programming Boards category; I create a top-down splay tree but don't know how to destroy it? Since the tree can be very deep, ...

  1. #1
    Registered User
    Join Date
    Mar 2010
    Location
    China
    Posts
    74

    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 wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,687
    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.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  3. #3
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,579
    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.
    Salem likes this.

  4. #4
    Registered User
    Join Date
    Mar 2010
    Location
    China
    Posts
    74
    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
    Location
    New Zealand
    Posts
    6,308
    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).
    anduril462 likes this.
    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, 10:33 AM
  4. best way to destroy object?
    By Shadow12345 in forum C++ Programming
    Replies: 11
    Last Post: 11-03-2002, 05:54 PM
  5. destroy DOS disks
    By itld in forum Linux Programming
    Replies: 29
    Last Post: 07-07-2002, 11:45 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21