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

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.

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

>'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.

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

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;
}

>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.

I forgot that IPL is sigma(path length for each node), I was thinking the longest path in the tree. Thanks!

-Patrick

>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.

'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

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;
}

>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

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;
}

>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.

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;
}