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