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: 6,128 | Comments: 45,548

filter by tags archive

Find the bugA broken tree

time to read 3 min | 573 words

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. (29 Feb 2016) When you can't rely on your own identity
  2. (05 Jan 2016) The case of the degrading system–Answer
  3. (04 Jan 2016) The case of the degrading system
  4. (11 Sep 2015) The concurrent memory buster
  5. (20 Apr 2011) Why do I get a Null Reference Exception?
  6. (25 Nov 2010) A broken tree
  7. (13 Aug 2010) RavenDB HiLo implementation
  8. (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. The low level interview question - 3 hours from now
  2. The worker pattern - 3 days from now

There are posts all the way to May 30, 2016

RECENT SERIES

  1. The design of RavenDB 4.0 (14):
    26 May 2016 - The client side
  2. RavenDB 3.5 whirl wind tour (14):
    25 May 2016 - Got anything to declare, ya smuggler?
  3. Tasks for the new comer (2):
    15 Apr 2016 - Quartz.NET with RavenDB
  4. Code through the looking glass (5):
    18 Mar 2016 - And a linear search to rule them
  5. Find the bug (8):
    29 Feb 2016 - When you can't rely on your own identity
View all series

RECENT COMMENTS

Syndication

Main feed Feed Stats
Comments feed   Comments Feed Stats