How to empty a Binary Serach Tree???

This is a discussion on How to empty a Binary Serach Tree??? within the C++ Programming forums, part of the General Programming Boards category; Well Iīve been working with this Binary Search Tree and it is almost completed. Itīs actually only missing a "cleaning" ...

  1. #1
    Veni Vidi Vice
    Join Date
    Aug 2001
    Posts
    343

    How to empty a Binary Serach Tree???

    Well Iīve been working with this Binary Search Tree and it is almost completed. Itīs actually only missing a "cleaning" operation. I am trying to implement a member-fuction for cleanup that actually deletes all nodes in the tree for avoiding a serius memory leak. The problem is that I donīt know how to do it.

    I have one solution that deletes the root until the tree is empty but this seems quite un-efficient because the tree must be rebuild every time it deletes the root. I was also thinking to implement a recusive deleteAllNodes member-func but isnīt this also quite un-efficient if the tree contains MANY nodes (invokes many functions)???. Iīm looking for an iterative solution (if there is any) but I havenīt come up with some.

  2. #2
    ggs
    ggs is offline
    C > C++ duders ggs's Avatar
    Join Date
    Aug 2001
    Posts
    435
    If you're that worried about stack depth, you can treat the binary tree as a list that _may_ have other lists sprout off the side. Iterate through all the right nodes, and recurse for left nodes. I think this will reduce the stack depth.
    .sect signature

  3. #3
    Registered User Cela's Avatar
    Join Date
    Jan 2003
    Posts
    362
    >>I have one solution that deletes the root until the tree is empty
    Eew, yucky! Why not just use an in-order traversal and instead of doing something fun with the node, delete it. :-)
    Code:
    void destroy(tree *t)
    {
      if (t == 0)
      {
        return;
      }
    
      destroy(t->left);
      destroy(t->right);
      delete t;
    }
    >>but isnīt this also quite un-efficient if the tree contains MANY nodes (invokes many functions)???.
    Not enough to worry about unless you've fallen into the worst case of ordered insertion where the tree depth is equal to the number of nodes. If this is even close to possible you need to use a balanced insertion algorithm to begin with. Otherwise, a recursive routine only has a depth equal to the height of the tree. Even for **HUGE** trees this won't be noticeable.
    *Cela*

  4. #4
    Veni Vidi Vice
    Join Date
    Aug 2001
    Posts
    343
    Yeeh I guess that a recursive deletenode-func would be the best solution for empting the tree. But this araises a new question for me. Iīve always tried to avoid recursive functions because I found it very un-efficient e.i. Fibonacci problem can be solved much better with an iterative (for loop) solution.

    Because of mine dislike for recursion Iīve replaced it with a iteratiove solution when possible. For example in my insert and remove methods Iīve iterated "down" to the node that should be preformed an action where I easily could use recursion insteed. Is my "dislike" for recusion unjustyfied???

  5. #5
    Registered User Cela's Avatar
    Join Date
    Jan 2003
    Posts
    362
    >>Is my "dislike" for recusion unjustyfied???
    Not a bit :-) For the most part recursive functions are better implemented iteratively, but recursion does have it's place for some recursively defined data structures or algorithms. Most of the time a binary tree is made recursively because it's much simpler, more natural, and the efficiency hit isn't that bad. quicksort and mergesort are defined recursively and most easily written that way as well. If you need blazing speed and a small stack depth the you can write them iteratively, but if you've ever done that you'll find it's a lot of extra work and complexity for not a whole lot of performance improvement.

    Recursion should be the last choice except in a few well defined application areas where recursion has been proven to be a very small handicap in performance and a huge timesaver in creation and maintenance.
    *Cela*

  6. #6
    Veni Vidi Vice
    Join Date
    Aug 2001
    Posts
    343
    ...
    but if you've ever done that you'll find it's a lot of extra work and complexity for not a whole lot of performance improvement.
    I know exactly what you mean. Well I thought that it would be big performence bootleneek because of my earlier experience with recursion. Well maybe next time a should make it easier for me insteed of looking at the perfomace issue. After all you can always modify (or rebuild the whole structure ) it later.

    Also I was a little confused by your earlier statement
    ...
    Otherwise, a recursive routine only has a depth equal to the height of the tree.
    Shouldnīt it be "Otherwise, a recursive routine only has a depth equal to the height times 2 of the tree" because you actually compare the links(leftchild and rightchild) ??? I presume you mean the number of times the actual function is invoked?!?! Need confirmation on this subject.

  7. #7
    Registered User Cela's Avatar
    Join Date
    Jan 2003
    Posts
    362
    >>Need confirmation on this subject.
    Consider a tree with height 4
    Code:
               6
              / \
         4           9
       /   \       /   \
      2     5     7     10
     / \   / \   / \   / \
    0   1                 11
    The most recursive calls you'll make for a search/deletion is 4, including the first call. To begin an in-order search you start by going to a depth of 4, (6 4 2 0), then return to a stack depth of 3 and recurse to 4 again. The whole order is (6 4 2 0 2 1 2 4 5 4 6 9 7 9 10 11)
    *Cela*

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 0
    Last Post: 11-04-2006, 11:07 AM
  2. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 04:00 PM
  3. Tutorial review
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 11
    Last Post: 03-22-2004, 09:40 PM
  4. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 10:33 AM
  5. BST/Red and Black Tree
    By ghettoman in forum C++ Programming
    Replies: 0
    Last Post: 10-24-2001, 11:45 PM

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