在含有n个结点的二叉排序树中查找一个关键字，进行关键字比较次

[单选题]

在含有n个结点的二叉排序树中查找一个关键字，进行关键字比较次数最大值是（）

1.n/2

2.log₂n

3. log₂(n +1)

4.n

Derkl

平均查找长度取决于二叉排序树的高度，即树的形态。

最坏情况下，二叉排序树输入序列有序时，会形成一个倾斜的单支树，此时树的高度变成元素个数n

因此需要进行关键字比较的最大值为n

发表于 2019-11-18 16:46:51 回复(0)

提交观点

问题信息

树查找

上传者：zsw3

难度：

1条回答 5收藏 6255浏览

扫一扫，把题目装进口袋