Re: Another bug in TreeMap

[Brian Jones]

Xuan Baldauf <address@hidden> writes:

>     else
>       {
>         // Node has 2 children. Splice is node's
> predecessor, and we swap
>         // its contents into node.
>         splice = node.left;
>         while (splice.right != nil)
>           splice = splice.right;
>         child = splice.left;
>         node.key = splice.key;
>         node.value = splice.value;
>       }
> 
>     // Unlink splice from the tree.
>     Node parent = splice.parent;
>     if (child != nil)
>       child.parent = parent;
>     if (parent == nil)
>       {
>         // Special case for 0 or 1 node remaining.
>         root = child;
>         return;
>       }
>     if (splice == parent.left)
>       parent.left = child;
>     else
>       parent.right = child;
> 
>     if (splice.color == BLACK)
>       deleteFixup(child, parent);
>   }
> 
> 
> In case the node to be removed has two children, within
> removeNode(), new keys and values will be swapped into the
> node the which is about to be removed. After removeNode()
> finished, remove() returns the value variable of that node.
> Because it was changed previously within removeNode(), the
> wrong value (from the swapped in node rather than from the
> original node) is returned. This is a bug.

I'm pretty sure that without dusting off my data structures book I
couldn't patch this properly.  I'm unsure what the point is of setting
the key/value of node in the else statement with that "node" being
deleted from the tree.

Brian
-- 
Brian Jones <address@hidden>