Ayende @ Rahien

Hi!
My name is Oren Eini
Founder of Hibernating Rhinos LTD and RavenDB.
You can reach me by phone or email:

ayende@ayende.com

+972 52-548-6969

, @ Q c

Posts: 5,972 | Comments: 44,517

filter by tags archive

Find the bugA 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);
}

More posts in "Find the bug" series:

  1. (20 Apr 2011) Why do I get a Null Reference Exception?
  2. (25 Nov 2010) A broken tree
  3. (13 Aug 2010) RavenDB HiLo implementation
  4. (25 Jul 2010) Accidental code reviews

Comments

configurator

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

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

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

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

Ayende Rahien

Chaviv,

How come?

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

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

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

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

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

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

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

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.

Comment preview

Comments have been closed on this topic.

FUTURE POSTS

  1. Reducing parsing costs in RavenDB - 18 hours from now

There are posts all the way to Aug 04, 2015

RECENT SERIES

  1. Production postmortem (5):
    29 Jul 2015 - The evil licensing code
  2. Career planning (6):
    24 Jul 2015 - The immortal choices aren't
  3. API Design (7):
    20 Jul 2015 - We’ll let the users sort it out
  4. What is new in RavenDB 3.5 (3):
    15 Jul 2015 - Exploring data in the dark
  5. The RavenDB Comic Strip (3):
    28 May 2015 - Part III – High availability & sleeping soundly
View all series

Syndication

Main feed Feed Stats
Comments feed   Comments Feed Stats