设二叉排序树上有n个结点，则在二叉排序树上查找结点的平均时间

[单选题]

设二叉搜索树上有n个结点，则在二叉搜索树上查找结点的平均时间复杂度为（）。

查看正确选项

Madgee

二叉排序树，也是二叉查找树，最坏情况下退化为单链表，时间复杂度为O(N),
平均情况下，时间复杂度为O(logN)

编辑于 2019-01-02 21:18:20 回复(0)

日子苦啊

最坏情况是深度为N的单支树为（N+1）/2
最好的是形态均匀和折半查找一样大约为 log2 N

发表于 2017-08-17 11:31:59 回复(2)

小易正在学习中

二叉排序树，也是二叉查找树，最坏情况下退化为单链表，时间复杂度为O(N), 平均情况下，时间复杂度为O(logN)

发表于 2022-05-02 23:51:26 回复(0)

提交观点

问题信息

复杂度

上传者：阿奻_

难度：

3条回答 140收藏 6766浏览

扫一扫，把题目装进口袋