平衡BST查找指定数floor值的最坏时间复杂度是多少

平衡二叉搜索树中查找指定key的floor值，最坏时间复杂度仍然为O(logn)，和精确匹配查找节点的最坏复杂度一致。

复杂度推导依据 #

floor操作的目标是找到等于key、或是最接近key且不大于key的节点，整个查找过程不会出现多子树遍历的情况：

• 你实现的递归逻辑中，每一层递归只会选择左子树、右子树其中一个方向向下深入，从来不会同时遍历两个子树
• 平衡BST的树高被严格维持在O(logn)级别，递归的最大深度不会超过树的高度
• 每一层递归的判断、返回操作都是O(1)的常数时间操作，整体总耗时和树高线性相关

代码执行逻辑拆解 #

struct Node {
    int data;
    Node *left, *right;
};

int floor(Node* root, int key)
{
    if (!root)
        return INT_MAX;
 
    // 找到精确匹配节点，直接返回，当前查找路径终止
    if (root->data == key)
        return root->data;
 
    // 当前节点值大于key，floor不可能出现在右子树（右子树所有节点值都比当前节点大），仅向左子树查找
    if (root->data > key)
        return floor(root->left, key);
 
    // 当前节点值小于key，优先去右子树找更接近key的合法值，找不到则当前节点就是当前子树范围内的最优解
    int floorValue = floor(root->right, key);
    return (floorValue <= key) ? floorValue : root->data;
}

这段代码不存在重复遍历、回溯遍历多分支的问题，最坏场景就是从根节点一路走到叶子节点才找到floor值，总遍历节点数等于树高，对应时间复杂度就是O(logn)。

补充说明：这段代码的边界返回值存在设计缺陷：当整棵树所有节点值都大于key时不存在合法floor，返回INT_MAX会和key恰好为INT_MAX的合法场景冲突，实际使用可通过空指针、布尔标记位区分无合法结果的情况，该缺陷不影响时间复杂度判断。

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