[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: Another bug in TreeMap
From: |
Brian Jones |
Subject: |
Re: Another bug in TreeMap |
Date: |
02 May 2002 18:56:11 -0400 |
User-agent: |
Gnus/5.09 (Gnus v5.9.0) Emacs/21.1 |
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>