Ayende @ Rahien

Wesner Moise commented on Find the bug: A broken tree

Wed, 01 Dec 2010 10:01:32 GMT

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.

Frank Quednau commented on Find the bug: A broken tree

Thu, 25 Nov 2010 17:08:50 GMT

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

nickd commented on Find the bug: A broken tree

Thu, 25 Nov 2010 15:34:37 GMT

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

Nick commented on Find the bug: A broken tree

Thu, 25 Nov 2010 14:58:39 GMT

int compare = comparer.Compare(key, theKey); I cannot see a declaration of the variable "theKey".

Patrick Huizinga commented on Find the bug: A broken tree

Thu, 25 Nov 2010 14:29:31 GMT

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.

Chaviv commented on Find the bug: A broken tree

Thu, 25 Nov 2010 10:45:11 GMT

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)

Ayende Rahien commented on Find the bug: A broken tree

Thu, 25 Nov 2010 10:30:20 GMT

Omer, BINGO!

Ayende Rahien commented on Find the bug: A broken tree

Thu, 25 Nov 2010 10:29:41 GMT

Chaviv, How come? If both Right & Left are not empty, it is hit.

configurator commented on Find the bug: A broken tree

Thu, 25 Nov 2010 10:29:04 GMT

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

Omer Mor commented on Find the bug: A broken tree

Thu, 25 Nov 2010 10:28:59 GMT

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.

Chaviv commented on Find the bug: A broken tree

Thu, 25 Nov 2010 10:27:51 GMT

The else case is never hit. else { // We have two children. Remove the next-highest node and replace // this node with it. IBinarySearchTree successor = Right; while (!successor.Left.IsEmpty) successor = successor.Left; result = new AVLTree (comparer, deepCopyKey, deepCopyValue, successor.Key, successor.Value, Left, Right.TryRemove(successor.Key, out removed, out value)); }

configurator commented on Find the bug: A broken tree

Thu, 25 Nov 2010 10:16:31 GMT

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