+972 52-548-6969
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:
- (29 Feb 2016) When you can't rely on your own identity
- (05 Jan 2016) The case of the degrading system–Answer
- (04 Jan 2016) The case of the degrading system
- (11 Sep 2015) The concurrent memory buster
- (20 Apr 2011) Why do I get a Null Reference Exception?
- (25 Nov 2010) A broken tree
- (13 Aug 2010) RavenDB HiLo implementation
- (25 Jul 2010) Accidental code reviews
Comments
There's a picture of a tree all over it... Is that it?
The else case is never hit.
else
<tkey,> successor = Right;
<tkey,> (comparer, deepCopyKey, deepCopyValue, successor.Key,
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: Which if would match the case of having two children, then?
Chaviv,
How come?
If both Right & Left are not empty, it is hit.
Omer,
BINGO!
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)
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.
int compare = comparer.Compare(key, theKey);
I cannot see a declaration of the variable "theKey".
In the complex case the value out parameter is set to the child replacing the node. Like I just noticed Patrick said,
Remember vaguely that out and ref can give you some nastiness especially passing it around forward and sideways...
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