[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Another bug in TreeMap

From: Xuan Baldauf
Subject: Another bug in TreeMap
Date: Wed, 01 May 2002 18:51:41 +0200


there is another bug in java.util.TreeMap. The sourcecode
contains following lines:

  public Object remove(Object key)
    Node n = getNode(key);
    if (n == nil)
      return null;
    return n.value;

  final void removeNode(Node node)
    Node splice;
    Node child;


    // Find splice, the node at the position to actually
remove from the tree.
    if (node.left == nil)
        // Node to be deleted has 0 or 1 children.
        splice = node;
        child = node.right;
    else if (node.right == nil)
        // Node to be deleted has 1 child.
        splice = node;
        child = node.left;
        // 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;
    if (splice == parent.left)
      parent.left = child;
      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.



P.S.: Please include my e-Mail address in replies as I'm not

Mit freundlichen Grüßen

Xuân Baldauf Internet Server Software

reply via email to

[Prev in Thread] Current Thread [Next in Thread]