首页 > 试题广场 >

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

[单选题]

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

  • 结点太多
  • 完全二叉树
  • 呈单枝树
  • 结点太复杂

二叉查找树,即二叉排序树,如果左子树不为空,左子树上的所有节点均小于根节点,如果右子树不为空,右子树上所有节点均大于根节点。
二叉排序树上查找其关键字等于给定值的结点的过程,恰是走了一条从根结点到该节点的路径的过程,和给定值比较的关键字的个数就等于,路径长度加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)
二叉树变成单支树则退化成链表
我们知道,链表增删快/查找慢,所以单支树是二叉树查找最慢情况
发表于 2018-01-02 14:43:08 回复(0)
选C

发表于 2020-07-06 12:46:19 回复(0)
C,二叉树树形结构呈单枝树时效率最低
发表于 2019-10-27 16:03:06 回复(0)