Wednesday, November 20, 2013

Delete works

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.

1 comment:

  1. As soon as you hit the minimum withdrawal, have the ability to|you possibly can} have your money sent to you utilizing the cost method of your selection. You also can choose to attend to construct up to as} your required amount, and the casino will hold your money in your account. On the opposite hand, other casinos are pretty easy and have little or no attachments thecasinosource.com to their bonuses. You get to withdraw your earnings as soon as you win them as long as|so lengthy as} you meet the withdrawal necessities. There is loads of data on how to to|tips on how to} win in blackjack round the} internet by benefit of|benefiting from|profiting from} methods from seasoned players and working towards often in demo video games.

    ReplyDelete