Thread: Need soem suggestions on my Binary Search Tree Implementation

  1. #1
    Ethernal Noob
    Join Date
    Nov 2001
    Posts
    1,901

    Need some suggestions on my Binary Search Tree Implementation

    I am implementing a binary search tree, and using non-recursive techniques in most of the algorithms. I think I finally have my deletion down, and considered several forms of a tree when a node is deleted that may cause problems for the non-recursive solutions. The one thing I'm having trouble with is non-recursive traversals (in-order, post-order, pre-order). Is it practical to devise a non-recursive algorithm for such functions. Also, is my delete function missing anything? I'm trying to get this down pat before I move on to R/B trees or AVL trees.
    Last edited by indigo0086; 10-08-2007 at 02:23 PM.

  2. #2
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,895
    I'd say a non-recursive traversal algorithm is the most important of all, because you need it to implement iterator-style access.
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

  3. #3
    Ethernal Noob
    Join Date
    Nov 2001
    Posts
    1,901
    The only problem I'm having in planning it out is would I have to make "doubly linked" nodes because the tree traversals eventually have to backtrack

  4. #4
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,897
    >would I have to make "doubly linked" nodes because the tree traversals eventually have to backtrack
    No, but you do need to store the backtracking data somehow. Another option is to save the nodes in a stack.
    My best code is written with the delete key.

  5. #5
    Ethernal Noob
    Join Date
    Nov 2001
    Posts
    1,901
    yeah, i thought of that soon before I saw your post. The iterator class would have a stack of addresses, starting from the root and pushing on each iterator dependign on the operation executed (child 0 for --, child 1 for ++), and pop it to go back up the chain. Makes more sense than what I was doing. I'm wondering if I could use this method to do a more generalized deletion algorithm, because now it seems like I'm just looking at all these possibilities rather than have the general rules (if a node has a child, then do this to the right subtree). But either way I got what I should do. Thanks for the info.

    and your sig is so right.

  6. #6
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,897
    >Makes more sense than what I was doing.
    There are downsides to a stack too, but it's a fantastic way to iteratively walk a tree without having to add extra storage and maintenance logic to the tree itself. If you want to see something that already exists, my tutorials cover non-recursive iteration, and the tree libraries implement it using a stack.

    >I'm wondering if I could use this method to do a more generalized deletion algorithm
    If you're not doing any balancing, the deletion algorithm should be pretty simple. Even the most complex case is straightforward, so I'm guessing that you're over complicating things.
    My best code is written with the delete key.

  7. #7
    Ethernal Noob
    Join Date
    Nov 2001
    Posts
    1,901
    Eventually I'm going to do balancing when I implement other trees, and just want to know how I can improve what I have for later use.

  8. #8
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,897
    >Eventually I'm going to do balancing when I implement other trees
    All the more reason to keep the basic algorithms as simple as possible.
    My best code is written with the delete key.

  9. #9
    Ethernal Noob
    Join Date
    Nov 2001
    Posts
    1,901
    What I'm really getting at is, is the one I posted "BSTree.h" simple ;b

  10. #10
    The superhaterodyne twomers's Avatar
    Join Date
    Dec 2005
    Location
    Ireland
    Posts
    2,273
    I think you're (potentially), missing a lot of nodes in your clear method. Shouldn't you have to traverse through the branches and delete all nodes rather than just delete-ing the root?

  11. #11
    Ethernal Noob
    Join Date
    Nov 2001
    Posts
    1,901
    Quote Originally Posted by twomers View Post
    I think you're (potentially), missing a lot of nodes in your clear method. Shouldn't you have to traverse through the branches and delete all nodes rather than just delete-ing the root?
    The desturctor for the Node class iterates through it's children array and deletes them, so if I delete the root, it will call the destructor for it's children, which delete it's children.

    Code:
        virtual ~Node()
        {
            for(size_t i = 0; i < size; ++i)
                delete child[i];
        }

  12. #12
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,897
    >is the one I posted "BSTree.h" simple ;b
    Gah, you're going to make me look at it, aren't you?

    I like that you're using the link array instead of symmetric cases, but you do know that a relational operation is required to return 0 or 1, right? You don't have to use the conditional operator for setting dir.

    For Delete, you can merge the zero and one child cases into a single case:
    Code:
    // The two child case goes here
    }
    else {
      // One or both children are null
      int replace = ( next->child[0] == NULL );
    
      if (next == root)   //delete if data is at root
        root = next->child[replace];
      else
        prev->child[dir] = next->child[replace];
    
      delete next;
    }
    Even if next->child[replace] is NULL, you still get the correct behavior. Also, you don't need to set next->child[replace] to NULL in any of the three cases because next is going to be immediately deleted. It doesn't matter what the value of any of its members is.
    My best code is written with the delete key.

  13. #13
    Ethernal Noob
    Join Date
    Nov 2001
    Posts
    1,901
    Thanks for that tip. Though I do have to replace the child to null because of the node's destructors. They traverse the child array and delete any children it's linked to. So if I have to link a node a child of the node to be deleted, then delete the node without disconnecting it from it's child, I will have inadvertently deleted two or more nodes, since the destructor will delete the nodes below it, if it's the case they aren't null. I don't know if it was wise but it made destroying the entire tree easier.

    And a lot of my code is verbose for the sake of me being explicit. I don't like having to go back and pen-n-paper my code to understand the logic (regarding using relational operators return values). In simple cases it's easy enough to udnerstand, but once I start using them a lot I miss my own logic sometimes.
    Last edited by indigo0086; 10-09-2007 at 07:38 AM.

  14. #14
    Ethernal Noob
    Join Date
    Nov 2001
    Posts
    1,901
    ok my delete function has been washed and waxed as follows
    Code:
    template <typename T>
    void BSTree<T>::Delete(T x)
    {
        if (root == NULL)
        {
            std::cout << "-- Tree is empty --" << std::endl;
            return;
        }
    
        BinaryTreeNode<T>* next = root;    //points ahead
        BinaryTreeNode<T>* prev = next;    //points to previous node
        size_t dir = 0;                 //stores pointer direction
    
        //search for the data to be replaced
        while(next->data != x)
        {
            prev = next;
            dir = next->data < x;
            next = next->child[dir];
        }
    
        //if there are two child nodes
        if(next->child[0] != NULL && next->child[1] != NULL)
        {
            //point to the root of right subtree
            BinaryTreeNode<T>* right = next->child[1];
            BinaryTreeNode<T>* rNext = right->child[0];
    
            //right is the leastmost node in subtree
            if(rNext == NULL)
            {
                next->data = right->data;
                next->child[1] = right->child[1];
                right->child[1] = NULL;
                delete right;
            }
            else    //otherwise find leastmost node
            {
                while(rNext->child[0] != NULL)
                {
                    right = rNext;
                    rNext = rNext->child[0];
                }
    
                //move subtrees upward to right's left tree
                next->data = rNext->data;
                right->child[0] = rNext->child[1];
                rNext->child[1] = NULL;
                delete rNext;
            }
        }
        else    //there is either none or one child node
        {
            //child to be moved to
            size_t replace = (next->child[0] == NULL);
    
            if(next == root)
            {
                root->data = root->child[replace];
                root->child[replace] = NULL;
            }
            else
            {
                prev->child[dir] = next->child[replace];
                next->child[replace] = NULL;
            }
        }
        std::cout << "-- " << x << " has been Deleted -- " << std::endl;
    }

  15. #15
    Ethernal Noob
    Join Date
    Nov 2001
    Posts
    1,901
    blech, didn't work.
    Last edited by indigo0086; 10-10-2007 at 10:25 AM.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Binary Search Tree
    By penance in forum C Programming
    Replies: 4
    Last Post: 08-05-2005, 05:35 PM
  2. Binary Tree, couple questions
    By scoobasean in forum C Programming
    Replies: 3
    Last Post: 03-12-2005, 09:09 PM
  3. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 10:33 AM
  4. Binary Search Tree, Inserting node
    By cheryl_li in forum C Programming
    Replies: 1
    Last Post: 09-13-2003, 03:53 AM
  5. BST/Red and Black Tree
    By ghettoman in forum C++ Programming
    Replies: 0
    Last Post: 10-24-2001, 10:45 PM