The delete operation would fail if the key was located outside of a leaf node (i.e. it was being used as a median.) This was the broken code:
if pos > 0 && node.Values[pos-1].Key == index {
// Found the delete value
if node.Nodes != nil {
// Lost median, will balance
tree.balance(node, pos)
}else{
The problem is that when I lost a median I just rebalanced two subtrees, resulting in no change. What was I thinking?
if pos > 0 && node.Values[pos-1].Key == index {
// Found the delete value
tree.Stats.Size--
if node.Nodes != nil {
// Lost median, must borrow
var remaining int
node.Values[pos-1], remaining = tree.borrow(node.Nodes[pos-1])
if remaining < (tree.N/2) {
tree.balance(node, pos-1)
}
The new code implements the borrow() routine. That operates similar to the del() routine except that it always descends down the right-most tree or value, returning the largest value in the subtree.
No comments:
Post a Comment