CODEWITHSUNDEEP
javanullpointerexceptionb-tree
Richard Waher
Richard Waher

Reputation: 21

Struggling With Btree Algorithm

I've tried using Java to implement algorithms from the textbook Introduction to Algorithms, 3rd edition, without a lot of success. Almost every time I try to implement them I encounter a multitude of errors, to the point where I'm not sure if the authors themselves have tried implementing their own pseudocode. But specifically, in this case, I'm having problems with the Btree algorithm. I think the problem lies somewhere in the B-Tree-Insert-Nonfull method. When I try to run the program, this line causes a Null Pointer Exception:

int i = x.totalKeys - 1;

However, that doesn't make any sense. All Nodes, like x in this case, are initialized with a value of 0 in their constructors, so how is his error even occurring? I'm going to enclose the function below:

public void bTreeInsertNonfull(Node x, Integer k)
{
    int i = x.totalKeys - 1;
    if (x.leaf || (x.children[i] == null))
    {
        while( (i >= 0) && (k < x.keys[i]) )
        {
            x.keys[i+1] = x.keys[i];
            i = i - 1;
        }
        x.keys[i+1] = k;
        x.totalKeys = x.totalKeys + 1;
    }
    else
    {
        while ( (i >= 0) && x.keys[i] != null)
        {
            if (k < x.keys[i])
            {
                i = i - 1;
            }
        }

        i = i + 1;

        if ((x.children[i] != null) && (x.children[i].totalKeys == tUpper))
        {
            bTreeSplitChild( x, i, x.children[i] );
            if (k > x.keys[i])
            {
                i = i + 1;
            }
        }
        bTreeInsertNonfull(x.children[i], k);
    }
}

Upvotes: 1

Views: 541

Answers (1)

Eduardo
Eduardo

Reputation: 8392

Elaborating on the idea from Alex: if you look at the last part of the algorithm, there is a line that says:

if ((x.children[i] != null) && (x.children[i].totalKeys == tUpper))

That hints that x.children[i] == null is a possibility. The last line of the algorithm calls bTreeInsertNonfull(x.children[i], k); without checking if the first parameter is null.

Upvotes: 1

Related Questions