java - 与 Btree 算法作斗争

Question

我尝试使用 Java 来实现教科书《算法简介》第三版中的算法，但没有取得很大成功。几乎每次我尝试实现它们时，我都会遇到大量错误，以至于我不确定作者自己是否尝试过实现他们自己的伪代码。但具体来说，在这种情况下，我在使用 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);
    }
}

Answer 1

详细阐述 Alex 的想法:如果您查看算法的最后一部分，就会发现有一行内容:

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

这暗示 x.children[i] == null 是一种可能性。该算法的最后一行调用 bTreeInsertNonfull(x.children[i], k); 而不检查第一个参数是否为 null。