B-Tree实现

Question

我在Rober Sedgewik的文章中读到了关于实现B树的文章，我在search方法的else部分找到了这个代码片段，链接如下：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和children的j+1th元素进行比较，而不是jth。有人可以通过一些光来说明这一点吗？

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的密钥。