首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
设平衡的二叉排序树(AVL树)的结点个数为n,则其平均检索长度为
设平衡的二叉排序树(AVL树)的结点个数为n,则其平均检索长度为
admin
2009-01-19
57
问题
设平衡的二叉排序树(AVL树)的结点个数为n,则其平均检索长度为
选项
A、O(1)
B、O(log
2
n)
C、O(n)
D、O(nlog
2
n)
答案
2
解析
平衡二叉树又称AVL树,它或者是一棵空树,或者是具有下列性质的二叉树:它的左子树和右子树都是平衡二叉树,且左子树和右子树的深度之差的绝对值不超过1,若将二叉树上结点的平衡因子BF定义为该结点的左子树的深度减去它的右子树的深度,则平衡二叉树上所有结点的平衡因子只可能是-1、0和1。只要二义树上有一个结点的平衡因子的绝对值大于1,则该二叉树就是不平衡的。因为AVL树上任何结点的左右子树的深度之差都不超过1,则可以证明它的深度和log
2
n是同数量级的(N为结点个数)。因此、它的平均查找长度也和log
2
n同数量级。
转载请注明原文地址:https://kaotiyun.com/show/TTcZ777K
本试题收录于:
三级数据库技术题库NCRE全国计算机三级分类
0
三级数据库技术
NCRE全国计算机三级
相关试题推荐
采用电话拨号上网时,有许多因素会影响上网的速度。在下面给出的选项中,哪种不会影响上网速度?
为了减少多媒体数据所占存储空间,人们采用了
Internet使用TCP/IP协议实现了全球范围的计算机网络的互连,连接在Internet上的每一台主机都有一个IP地址,下面( )不能作为IP地址。
80286的标志寄存器增加了( )个标志位字段。
某公司在将一个产品的图片用电子邮件发送给客户前,需要先生成相应的图片文件。下列方法中,哪种是不可行的?
注册表是Windows98存储各种软硬件配置信息的“仓库”。在下列有关Windows98注册表的叙述中,错误的是
当成千上万台终端设备需要相互通信时,它们之间采用固定的连接是极不经济的。解决方法是在要进行通信的终端之间建立临时连接,通信结束后再拆除连接,实现这种功能的设备称为
Windows98是由多个模块组成的一个功能强大的操作系统,下列哪个模块负责处理键盘和鼠标的输入,井以窗口、图标、菜单和其他界面元素的形式完成输出任务?
Windows98提供了15个故障检修向导(也称为“疑难解答”),帮助用户解决一些在使用Window98过程中可能遇到的问题。下面( )项没有包含在这些故障检修向导中。
随机试题
下列几种症状中,对雏鸡维生素B2缺乏症诊断意义最大的是
患者,女,23岁。被人发现时呈昏迷状态。查体:神志不清,两侧瞳孔呈针尖样大小,呼吸有大蒜臭味,应首先考虑的是
患者,男,78岁。患病卧床日久,今日出现手足逆冷、精神疲惫、神情淡漠等症状。医师处以附子进行治疗,为加强治疗效果,可以配合应用的药物为
甲巯咪唑抗甲状腺的作用机制是
TIA是局灶性脑缺血导致突发短暂性、可逆性神经功能障碍,发作持续数分钟可完全恢复,通常不超过()。
分析表演游戏的特点及指导方法。
2005年年底,全国高速公路里程为多少万公里?( )
根据下图回答下列问题。乘用车销量占汽车产量比重最大的月份是()。
Realpolicemenhardlyrecognizeanyresemblance(类同之处)betweentheirlivesandwhattheyseeonTV—iftheyevergethomeintime.
若f(x-1)=x2(x-1),则f(x)=_______.
最新回复
(
0
)