从二叉排序树中查找一个元素时，其时间复杂度大致为？

左弦 · 发表于 2012-6-14 17:09:26

本帖最后由番茄于 2012-6-15 13:59 编辑

今天看到一个题，问从二叉排序树中查找一个元素时，其时间复杂度大致为多少？有那位数据结构高手知道，给个提示吧，谢谢了。。。

wangyexin · 发表于 2012-6-14 17:09:27

log2N

Life_On_The_Go · 发表于 2012-6-14 17:28:02

O（n(n+1)/2）

Life_On_The_Go · 发表于 2012-6-14 17:28:48

O（n(n+1)/2）

故乡的风 · 发表于 2012-6-14 23:00:49

二叉树查找元素最坏情况,遍历所有的元素，等效于顺序查找数组元素，其时间复杂度为O(n).

左弦 · 发表于 2012-6-15 18:34:09

故乡的风发表于 2012-6-14 23:00

登录/注册后可看大图

二叉树查找元素最坏情况,遍历所有的元素，等效于顺序查找数组元素，其时间复杂度为O(n).

三个答案啊。。。到底那个正确啊？

左弦 · 发表于 2012-6-15 18:38:09

wangyexin 发表于 2012-6-14 23:01

登录/注册后可看大图

log2N

四个答案分别是，n 1 log2n n^2?那个正确呢？

左弦 · 发表于 2012-6-15 18:38:58

故乡的风发表于 2012-6-14 23:00

登录/注册后可看大图

二叉树查找元素最坏情况,遍历所有的元素，等效于顺序查找数组元素，其时间复杂度为O(n).

是log2n吧？

左弦 · 发表于 2012-6-15 18:45:45

Life_On_The_Go 发表于 2012-6-14 17:28

登录/注册后可看大图

O（n(n+1)/2）

应该不是把？

wangyexin · 发表于 2012-6-15 20:08:47

左弦发表于 2012-6-15 18:38

登录/注册后可看大图

四个答案分别是，n 1 log2n n^2?那个正确呢？

log2n

故乡的风 · 发表于 2012-6-15 21:43:29

左弦发表于 2012-6-15 18:38

登录/注册后可看大图

是log2n吧？

不好意思，看错题了。二叉排序树和折半查找类似，其时间复杂度为O(log2n)。如果是一般二叉树，就和线性表类似了，时间复杂度为O(n)。

回忆为微笑 · 发表于 2012-7-24 00:22:32

小甲鱼的数据结构视频是不是不更新了啊

左弦 · 发表于 2012-7-24 18:58:12

回忆为微笑发表于 2012-7-24 00:22

登录/注册后可看大图

小甲鱼的数据结构视频是不是不更新了啊

不知道啊啊啊啊啊啊啊啊

账号		自动登录	找回密码
密码			立即注册

RE: 从二叉排序树中查找一个元素时，其时间复杂度大致为？