用Btree算法挣扎

我已经尝试过使用Java来实现从教科书算法入门算法第3版算法，没有很多的成功。几乎每次我尝试实现它们时，都会遇到很多错误，以至于我不确定作者本身是否尝试过实现自己的伪代码。但具体而言，在这种情况下，我遇到了Btree算法的问题。我认为问题出在B-Tree-Insert-Nonfull方法的某处。当我尝试运行该程序，这条线将导致一个空指针异常：用Btree算法挣扎

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); 
    } 
}

来源

2012-10-19 Richard Waher

是'x' null还是'x.totalkeys' null？代码发布到空引用发生在第一行的功能并不能帮助我们（编辑：这是一个递归函数，所以也许错误实际上是在此功能） - 的错误造成的，因为无论是x'传递到节点'该函数为null或变量'x.totalkeys'未初始化。 –

检查在书中数组索引从1，因为他们经常在算法伪代码，并确保你适应你的Java代码（从0哪些索引阵列）。要么让1个做大Java数组，并留下指数0未使用，或适应算法使用索引一个比伪小。 – hyde

在阐述亚历克斯的想法：如果你看一下算法的最后部分，有这样一行：

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

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

来源

2012-10-19 09:07:42 Eduardo

好的，伙计们，给了我一些很好的提示来解决这个混乱。谢谢。 –

请接受这个答案。 – alexraasch

用Btree算法挣扎

回答

相关问题