Assymetric delete() vs. symmetric delete() functions - binary tree

This is a discussion on Assymetric delete() vs. symmetric delete() functions - binary tree within the C++ Programming forums, part of the General Programming Boards category; Hello all, I would once again like to ask for advice. I've created a binary tree that adds and deletes ...

  1. #1
    Registered User
    Join Date
    Jun 2006
    Posts
    121

    Assymetric delete() vs. symmetric delete() functions - binary tree

    Hello all, I would once again like to ask for advice. I've created a binary tree that adds and deletes random elements. I read in my Data Structures text, regarding the below deleteByCopying() function, which can lead to an unbalanced tree, that:

    'a simple improvement can make the algorightm symmetrical. The algorithm can alternately delete the predecessor of the key in node from the left subtree and delete its successor form the right subtree.'

    What does this mean in regards to:

    Code:
    template<class T>
    void deleteByCopying(BinSearchNode<T>*& node)
    {
    	BinSearchNode<T> *previous, *tmp = node;
    	if(node->right == 0)
    		node = node->left;
    	else if(node->left == 0)
    		node = node->right;
    	else
    	{
    		tmp = node->left;
    		previous = node;
    		while(tmp->right != 0)
    		{
    			previous = tmp;
    		    tmp = tmp->right;
    	    }
    	node->key = tmp->key;
    	if(previous == node)
    		previous->left = tmp->left;
    	else
    		previous->right = tmp->left;
    	}
    delete tmp;
    }
    I can't figure out why it's talking about deleting predecessors and successors. The sucessor from the right subtree sounds like node->right, the right subchild, but: successor from the left subtree? Successor sounds like it's parent, prev, and not like node->left. Can anyone help?

    Thanks,

    -Patrick

  2. #2
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,305

    Smile

    No, predecessor and successor don't have anything to do with their parent-child relationships. It is only to do with the key values.

    The leftmost child in the items right sub-tree is the successor and the rightmost child in the left sub-tree is the predecessor. Draw a correctly ordered binary tree and you will see what I mean.

  3. #3
    Registered User
    Join Date
    Jun 2006
    Posts
    121
    OK, thanks, iMalc, the book never told us that! I'm not sure if I'm on the right track, but that gives me an idea with this tree.

    -Patrick

  4. #4
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,796
    >'a simple improvement can make the algorightm symmetrical.
    A simple improvement, yes, but it still adds complexity to the algorithm and solves a problem that borders between extremely rare and impossible in practice. You can safely ignore that advice.

    >I can't figure out why it's talking about deleting predecessors and successors.
    The successor is one to the right and as far as you can go to the left. The predecessor is one to the left and as far as you can go to the right. By predecessor and successor, we mean the values in the tree when viewed from the perspective of an inorder traversal.
    My best code is written with the delete key.

  5. #5
    Registered User
    Join Date
    Jun 2006
    Posts
    121
    Thanks, Prelude, I understand what you're saying, but there is an end-of-chapter problem that asks for this (I did implement it, BTW, and it seems to work). Do you (or does anyone, for that matter) know of a function/algorithm to calculate IPL (internal path length) for a tree when it is called? I've been thinking about a few different ways, but I'm not sure they would work: how would I be sure I am on the highest level when I traverse the tree? Thanks,

    -Patrick

  6. #6
    Registered User
    Join Date
    Jun 2006
    Posts
    121
    Am I on the right track here?

    Code:
    int BreadthOrderTraversal(BinaryTree binaryTree)
    {
            Queue queue;
            queue.Enqueue(binaryTree.Root);
            while(Queue.Size > 0)
            {
                    level++;
                    Node n = GetFirstNodeInQueue();
                    queue.Enqueue(n.LeftChild); //Enqueue if exists
                    queue.Enqueue(n.RightChild); //Enqueue if exists
                    queue.Dequeue(); //Visit
             }
             return level+1;
    }

  7. #7
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,796
    >I did implement it, BTW, and it seems to work
    Since it's an exercise, by all means work through a few solutions, but in my experience it's an unnecessary change. Keep that in mind for your production code.

    >Do you (or does anyone, for that matter) know of a function/algorithm to
    >calculate IPL (internal path length) for a tree when it is called?
    Yes. As with most problems, there are a bunch of ways to solve it. I think you've got a nice elegant solution in the works. Just do a level order traversal and add together the levels for each visited node. A depth first traversal would also work, and you would also get level numbers right out of the recursion tree. That's another solution.

    >how would I be sure I am on the highest level when I traverse the tree?
    You shouldn't worry about it because a caller might want the internal path length of a subtree. Just take the given tree and work from it on the assumption that there's nothing above. This gives you more flexibility.

    >Am I on the right track here?
    Yes.
    My best code is written with the delete key.

  8. #8
    Registered User
    Join Date
    Jun 2006
    Posts
    121
    I forgot that IPL is sigma(path length for each node), I was thinking the longest path in the tree. Thanks!

    -Patrick

  9. #9
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,796
    >I was thinking the longest path in the tree.
    The longest path is even easier. Just do a depth first traversal and return the height of the tallest subtree + 1.
    My best code is written with the delete key.

  10. #10
    Registered User
    Join Date
    Jun 2006
    Posts
    121
    'add together the levels for each visited node'... I'm having trouble implementing. How do I ascertain the level of the node being visited?

    -Patrick

  11. #11
    Registered User
    Join Date
    Jun 2006
    Posts
    121
    This doesn't work, just gives me the total # of nodes I have in the tree:

    Code:
    template<class T>
    void BinSearchTree<T>::getIPL()
    {
            int level = 0;
            static int count = 0;
            Queue<BinSearchNode<T>*> anotherQueue;
            BinSearchNode<T> * n = root;
            if(n != 0)
            {
                    anotherQueue.enqueue(n);
                    while(!anotherQueue.empty())
                    {   
                        level++;
                        n = anotherQueue.dequeue();
                        if(n->left != 0)
                        {
                            count += level;
                            anotherQueue.enqueue(n->left);
                        }
                        if(n->right != 0)
                        {
                            count += level;
                            anotherQueue.enqueue(n->right);
                        }
                        
                    }
             }
             cout << "This tree has an IPL of " <<  level << endl;
    }

  12. #12
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,796
    >How do I ascertain the level of the node being visited?
    You calculate it. Off the top of my head, I'd say that pulling the level from the last dequeue should give you the results you want. If you start with a guaranteed level of 0, you have a base to work with. Like so:
    Code:
    Node it := root
    
    If it <> null Then
      length := 0
      level := 0
    
      # Guaranteed first level of 0
      q.enqueue ( make_pair ( it, level ) )
    
      While not q.empty() Do
        save := q.dequeue()
    
        it := save.first
        length := length + save.second
    
        If it.left <> null Then
          q.enqueue ( make_pair ( it->left, save.second + 1 ) )
        EndIf
    
        If it.right <> null Then
          q.enqueue ( make_pair ( it->right, save.second + 1 ) )
        EndIf
      Loop
    EndIf
    My best code is written with the delete key.

  13. #13
    Registered User
    Join Date
    Jun 2006
    Posts
    121
    Is this what you were hinting at? I doubt it, because it gives me an IPL of over 200 million for a complete tree of level = 8. I was a little confused in particular by save.first and save.second.

    Code:
    template<class T>
    void BinSearchTree<T>::getIPL()
    {
            int level = 0;
            static int count = 0;
            Queue<BinSearchNode<T>*> anotherQueue;
            BinSearchNode<T> * n = root;
            if(n != 0)
            {
                    anotherQueue.enqueue(n);
                    while(!anotherQueue.empty())
                    {   
                        level += count;
                        n = anotherQueue.dequeue();
                        if(n->left != 0)
                        {
                            anotherQueue.enqueue(n->left);
                            count += 1;
                        }
                        if(n->right != 0)
                        {
                            count += level;
                            anotherQueue.enqueue(n->right);
                            count += 1;
                        }
                        
                    }
             }
             else if(n == 0)
             {
                  level = 0;
                  count = 0;
             }
             cout << "This tree has an IPL of " <<  level << endl;
    }

  14. #14
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,796
    >Is this what you were hinting at?
    No. Note how carefully I treated the level in that pseudocode. You can't just blindly increment it or you'll be counting far too high.

    >I was a little confused in particular by save.first and save.second.
    The queue stores two values in my suggestion: the link (as before), and also the level. save.first is the link and save.second is the level. For C++, look at the pair<> template and make_pair template function in <utility>. The pseudocode was modelled with those in mind.
    My best code is written with the delete key.

  15. #15
    Registered User
    Join Date
    Jun 2006
    Posts
    121
    You know, Prelude, I'm thinking that software engineering is not a field I should be looking into; I can't do a lot of the projects in the book without asking for help. This data structs class is distance learning, so real-time help doesn't exist for me :-( I read up on std:air, modified my function and included the <utility> header, and included pair class def., but the compiler does not like my use of enqueue() for pair (do I have to overload it?), and doesn't accept my declaration of pair in the getIPL function. As usual, thanks for any help, and what you've done so far!

    -Patrick

    pair class declaration:
    Code:
    template <class T>
    class pair {
        T values [2];
      public:
        pair (T first, T second)
        {
          values[0]=first; values[1]=second;
        }
    };
    New getIPL() function
    Code:
    template<class T>
    void BinSearchTree<T>::getIPL()
    {
            int level = 0;
            static int count = 0;
            Queue<BinSearchNode<T>*> anotherQueue;
            BinSearchNode<T> * n = root;
            if(n != 0)
            {
                    anotherQueue.enqueue(make_pair(n, level)); //no-go.  Must I overload?
                    while(!anotherQueue.empty())
                    {   
                        pair<BinSearchNode<int>*, int> save = n.dequeue(); //error
                        n = save.first; //doesn't recognize save
                        count += save.second;
                        if(n->left != 0)
                        {
                            anotherQueue.enqueue(make_pair(n->left, save.second+1));
            
                        }
                        if(n->right != 0)
                        {
                            anotherQueue.enqueue(make_pair(n->right, save.second+1));
                        }
                        
                    }
             }
             else if(n == 0)
             {
                  level = 0;
                  count = 0;
             }
             cout << "This tree has an IPL of " <<  level << endl;
    }

Page 1 of 2 12 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Tutorial review
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 11
    Last Post: 03-22-2004, 08:40 PM
  2. binary tree start
    By curlious in forum C++ Programming
    Replies: 6
    Last Post: 01-01-2004, 02:47 PM
  3. read records fron file into a binary tree
    By Kirsten in forum C Programming
    Replies: 1
    Last Post: 04-23-2002, 02:48 PM
  4. Array, Linked List, or Binary Tree?
    By Unregistered in forum C Programming
    Replies: 6
    Last Post: 01-05-2002, 09:07 PM
  5. BST/Red and Black Tree
    By ghettoman in forum C++ Programming
    Replies: 0
    Last Post: 10-24-2001, 10:45 PM

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