首页 > 试题广场 >

二叉查找树的查找效率与二叉树的树型有关, 在 ( )时

[单选题]

二叉查找树的查找效率与二叉树的树型有关, 在 ( )时其查找效率最低。

查看正确选项

空空以空空

二叉查找树，即二叉排序树，如果左子树不为空，左子树上的所有节点均小于根节点，如果右子树不为空，右子树上所有节点均大于根节点。

二叉排序树上查找其关键字等于给定值的结点的过程，恰是走了一条从根结点到该节点的路径的过程，和给定值比较的关键字的个数就等于，路径长度加1（或节点所在的层数）

我们来看这两棵树

虽然他们的节点的值都是相同的，但是前者有关键字序列（45，24，53，12，37，93）构成，后者是（12，24，37，45，53，93）构成

前者深度为3，后者深度为6，假设6个记录的查找概率是相等的，是1/6，那么他们的平均查找长度分别如下

当先后插入的关键字有序时，构成的二叉排序树就会变成单支树，其平均查找长度为（n+1）/2，和顺序查找是相同的，这是最差的情况

最好的情况就是和折半查找的判定树相同，平均查找长度和log2n成正比

发表于 2017-08-29 19:58:40 回复(0)

jranzjm

二叉树变成单支树则退化成链表

我们知道，链表增删快/查找慢，所以单支树是二叉树查找最慢情况

发表于 2018-01-02 14:43:08 回复(0)

天尊墨宇

选C

发表于 2020-07-06 12:46:19 回复(0)

zkingcode

C,二叉树树形结构呈单枝树时效率最低

发表于 2019-10-27 16:03:06 回复(0)

提交观点

问题信息

树

上传者：阿奻_

难度：

4条回答 62收藏 8653浏览

扫一扫，把题目装进口袋