首页 > 试题广场 >

以下为平衡二叉排序树的查找算法, 假设表长为N,则算法的时间

[单选题]
以下为平衡二叉排序树的查找算法, 假设表长为N,则算法的时间复杂度为(
bitree *search_fsortree(bitree *t, keytype key) {
    while(nullptr != t) {
        if (t->data == key) return t;
        else if (t->data > key) t = t->lchild;
        else  t = t->rchild;
    }
    return nullptr;
}
  • O(1)
  • O(n)
  • O(n^2)
  • O(log(n))
如果只是二叉排序树,则树高最差是O(n)
如果是平衡二叉树,则树高最差是O(logn)
发表于 2022-10-02 09:17:51 回复(0)

二叉排序树的查找长度不超过其树高,即O(log2N)

发表于 2019-12-05 01:48:54 回复(0)
二叉排序树的查找,最差情况下搜索的次数为树高,即为log2n,则时间复杂度为log2n。
发表于 2017-06-19 15:45:54 回复(0)