Xuan Baldauf <[EMAIL PROTECTED]> 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 <[EMAIL PROTECTED]> _______________________________________________ Classpath mailing list [EMAIL PROTECTED] http://mail.gnu.org/mailman/listinfo/classpath