B树中查找≤指定键的最大键：操作命名与代码修改问询

操作的标准名称 #

这个操作在有序集合中的标准名称是floor操作，对应数学上的“下取整”概念，即找到集合中小于等于给定值key的最大元素。

基于lower_bound的修改方案 #

已知lower_bound的作用是找到有序B树中第一个大于等于给定key的元素，我们可以基于这个结果做如下调整来实现floor操作：

• 调用现有lower_bound函数，得到目标节点指针p
• 如果p不为空且p->key == key：直接返回p->key，这就是我们要找的元素
• 如果p是树的根节点的第一个子节点（即没有前驱元素）：说明所有元素都大于key，返回默认值0
• 否则：返回p的前驱节点的键值，这个前驱节点就是小于等于key的最大元素

代码逻辑示例（C语言风格） #

int btree_floor(BTreeNode *root, int key) {
    BTreeNode *p = btree_lower_bound(root, key);
    if (p != NULL && p->key == key) {
        return p->key;
    }
    // 判断是否无前驱元素
    if (p == root->children[0]) {
        return 0;
    }
    // 获取前驱节点，需根据B树结构实现
    BTreeNode *prev = get_predecessor(p);
    return prev != NULL ? prev->key : 0;
}

注：get_predecessor函数需要适配你的B树节点结构实现：如果当前节点是父节点的第k个孩子，前驱就是父节点第k-1个孩子的最右侧叶子节点；如果是叶子节点，直接取同一节点中的前一个键（若节点存储多个键）。

关键思路说明 #

因为B树是严格递增的，lower_bound的结果将树分为两部分：左侧是所有小于key的元素，右侧是大于等于key的元素。我们要找的是左侧部分的最后一个元素，或是刚好等于key的元素，通过对lower_bound结果的判断和前驱查找，就能在O(log n)时间内完成操作，符合B树的时间复杂度要求。

内容的提问来源于stack exchange，提问作者Neil