Btree 알고리즘으로 어려움을 겪고 있습니다.

Question

Java를 사용하여 알고리즘 소개, 제 3 판, 알고리즘 소개를 많은 시도없이 구현하려고했습니다. 거의 언제나 구현하려고 할 때마다 많은 오류가 발생합니다. 저자 자신이 자신의 의사 코드를 구현 하려는지 확실하지 않습니다. 그러나 구체적으로이 경우 Btree 알고리즘에 문제가 있습니다. 나는이 문제가 B-Tree-Insert-Nonfull 방법의 어딘가에 있다고 생각한다. 프로그램을 실행하려고하면이 줄에서 Null 포인터 예외가 발생합니다.

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

알렉스의 생각을 부연 : 나는 아래의 기능을 묶으려고 당신이 알고리즘의 마지막 부분에 보면를 말한다 라인이 :

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

은 그 힌트는 x.children[i] == null 가능성이 있습니다. 알고리즘의 마지막 행은 첫 번째 매개 변수가 null인지 확인하지 않고 bTreeInsertNonfull(x.children[i], k);을 호출합니다.