java - B树实现

Question

我正在阅读 Rober Sedgewik 的关于实现 B-Tree 的内容，并在 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+1元素，而不是<第 j 个代码。 有人可以通过一些关于这个特定点的信息吗？

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 的 key 。