Thread: 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

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 forgot that IPL is sigma(path length for each node), I was thinking the longest path in the tree. Thanks!

-Patrick

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

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

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