B-Tree Реализация

Question

Я читал о реализации B-Tree из Робер Sedgewik и нашел этот фрагмент в else части search метода по этой ссылке: http://algs4.cs.princeton.edu/62btrees/BTree.java.html

// internal node 
     else { 
      for (int j = 0; j < x.m; j++) { 
       if (j+1 == x.m || less(key, children[j+1].key)) 
        return search(children[j].next, key, ht-1); 
      } 
     } 

Я ударился головой, но не мог понять, почему он непосредственно начинает сравнивать key с j+1-й элемент от children и не j th. Может ли кто-нибудь пролить свет на этот конкретный момент?

Answer 1

Если вы посмотрите на его объявление метода less(), вы заметите, что он использует compareTo.

По сути, то, что он хотел сделать key.compareTo(children[j+1].key)

Но зачем ему использовать j+1 вместо j? Чтобы понять это, посмотрите на первую часть его условного утверждения; он использует j+1 == x.m, что означает, что он хочет проверить, является ли j + 1 пределом. Если j+1 = x.m, он не хочет продолжать увеличивать j, поэтому он возвращается. Однако, если это еще не предел, проверьте сравнение текущего ключа со следующей клавишей в списке (поскольку существует следующий ключ). Если следующий ключ в списке «меньше», чем текущий ключ, выполните поиск текущего ключа.

Короче говоря: Если j+1 не существует, первая половина оператора if поймает его, и он вырвется из цикла for. В противном случае отметьте ключ j+1.