| Subject: | delete can delete wrong key |
| Date: | Thu, 27 Aug 2009 18:26:42 -0400 |
| To: | <bug-tree-rb [...] rt.cpan.org> |
| From: | "Christopher Gurnee" <gurnec [...] gis.net> |
When deleting a node 'z' which has two children from a binary search tree, the
typical algorithm is to delete the successor node 'y' instead (which is
guaranteed to have at most one child), and then to overwrite the key/values of
node 'z' (which is still in the tree) with the key/values (which we don't want
to lose) from the now-deleted successor node 'y'.
It looks like the delete sub is implementing the first half of this (deleting
the successor node 'y'), but not the second half (moving over the key/values we
want to keep). Currently, a call to delete will sometimes delete the successor
node instead (whenever the node to delete has two children). E.g.:
$t = new Tree::RB;
$t->put("b", 1);
$t->put("a", 1);
$t->put("c", 1);
print $t->delete("b")->key;
This should delete and print "b", but instead it deletes and prints "c". I think
this patch should fix it:
--- lib/Tree/RB.pm 2009-07-15 18:16:48.000000000 -0400
+++ ../fixed/RB.pm 2009-08-27 18:00:57.000000000 -0400
@@ -395,6 +395,14 @@
delete $y->[_PARENT];
}
}
+ if($y ne $z) {
+ my $swap = $y->[_KEY];
+ $y->[_KEY] = $z->[_KEY];
+ $z->[_KEY] = $swap;
+ $swap = $y->[_VAL];
+ $y->[_VAL] = $z->[_VAL];
+ $z->[_VAL] = $swap;
+ }
$self->[SIZE]--;
return $y;
}
Since you need to return the deleted item, it's not good enough to overwrite the
key/values of node 'z' with those of node 'y'. Instead I swap them so we can
return the deleted values.
-Chris