我已经尝试使用 Java 来实现教科书 Introduction to Algorithms, 3rd edition 中的算法,但没有取得很大成功。几乎每次我尝试实现它们时都会遇到大量错误,以至于我不确定作者自己是否尝试过实现自己的伪代码。但具体来说,在这种情况下,我遇到了 Btree 算法的问题。我认为问题出在 B-Tree-Insert-Nonfull 方法的某个地方。当我尝试运行程序时,此行会导致空指针异常:
int i = x.totalKeys - 1;
然而,这没有任何意义。所有节点,比如本例中的 x,在它们的构造函数中都被初始化为 0,那么他的错误是怎么发生的呢?我将附上下面的函数:
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);
}
}