Ayende @ Rahien

It's a girl

Find the bug: A broken tree

Originally posted at 11/22/2010

This method has a bug, a very subtle one. Can you figure it out?

public IBinarySearchTree<TKey, TValue> TryRemove(TKey key, out bool removed, out TValue value)
{
    IBinarySearchTree<TKey, TValue> result;
    int compare = comparer.Compare(key, theKey);
    if (compare == 0)
    {
        removed = true;
        value = theValue;
        // We have a match. If this is a leaf, just remove it 
        // by returning Empty.  If we have only one child,
        // replace the node with the child.
        if (Right.IsEmpty && Left.IsEmpty)
            result = new EmptyAVLTree<TKey, TValue>(comparer, deepCopyKey, deepCopyValue);
        else if (Right.IsEmpty && !Left.IsEmpty)
            result = Left;
        else if (!Right.IsEmpty && Left.IsEmpty)
            result = Right;
        else
        {
            // We have two children. Remove the next-highest node and replace
            // this node with it.
            IBinarySearchTree<TKey, TValue> successor = Right;
            while (!successor.Left.IsEmpty)
                successor = successor.Left;
            result = new AVLTree<TKey, TValue>(comparer, deepCopyKey, deepCopyValue, successor.Key, 
                successor.Value, Left, Right.TryRemove(successor.Key, out removed, out value));
        }
    }
    else if (compare < 0)
        result = new AVLTree<TKey, TValue>(comparer, deepCopyKey, deepCopyValue, 
            theKey, theValue, Left.TryRemove(key, out removed, out value), Right);
    else
        result = new AVLTree<TKey, TValue>(comparer, deepCopyKey, deepCopyValue,
            theKey, theValue, Left, Right.TryRemove(key, out removed, out value));
    return MakeBalanced(result);
}

Posted By: Ayende Rahien

Published at

Originally posted at

Comments

configurator
11/25/2010 10:16 AM by
configurator

There's a picture of a tree all over it... Is that it?

Chaviv
11/25/2010 10:27 AM by
Chaviv

The else case is never hit.

else

    {

        // We have two children. Remove the next-highest node and replace

        // this node with it.

        IBinarySearchTree

<tkey,> successor = Right;

        while (!successor.Left.IsEmpty)

            successor = successor.Left;

        result = new AVLTree

<tkey,> (comparer, deepCopyKey, deepCopyValue, successor.Key,

            successor.Value, Left, Right.TryRemove(successor.Key, out removed, out value));

    }
Omer Mor
11/25/2010 10:28 AM by
Omer Mor

If we have a match (compare == 0) we set removed to be true (which is right), but later, if both right & left are not empty, we overwrite this value with the result of removing from the right side.

So you can't trust the "removed" result in this scenario.

configurator
11/25/2010 10:29 AM by
configurator

Chaviv: Which if would match the case of having two children, then?

Ayende Rahien
11/25/2010 10:29 AM by
Ayende Rahien

Chaviv,

How come?

If both Right & Left are not empty, it is hit.

Chaviv
11/25/2010 10:45 AM by
Chaviv

Not wearing my code glasses. My bad. I read the code wrong. It would have been easier to read it as:

Check if both are not empty

Left not empty

Right not empty

else (both empty)

Patrick Huizinga
11/25/2010 02:29 PM by
Patrick Huizinga

When the matching node has two children, you can trust __result (to be true). However __value will in this case have the value of replacing node.

Nick
11/25/2010 02:58 PM by
Nick

int compare = comparer.Compare(key, theKey);

I cannot see a declaration of the variable "theKey".

nickd
11/25/2010 03:34 PM by
nickd

In the complex case the value out parameter is set to the child replacing the node. Like I just noticed Patrick said,

Frank Quednau
11/25/2010 05:08 PM by
Frank Quednau

Remember vaguely that out and ref can give you some nastiness especially passing it around forward and sideways...

Wesner Moise
12/01/2010 10:01 AM by
Wesner Moise

Code Review:

You should really design the function to return the same object if no node has been deleted.... rather than offering an out removed parameter.

Comments have been closed on this topic.