设平衡的二叉排序树(AVL树)的结点个数为n，则其平均拉索长度为

admin2010-05-13 54

问题设平衡的二叉排序树(AVL树)的结点个数为n，则其平均拉索长度为

选项 A、O(1)
B、O(log₂n)
C、O(n)
D、O(nlog₂n)

答案2

解析平衡二叉树又称AVL树，它或者是一棵空树，或者是具有下列性质的二叉树：它的左子树和右子树都是平衡二叉树，且左子树和右子树的深度之差的绝对值不超过1，若将二叉树上结点的平衡因子BF定义为该结点的左子树的深度减去它的右子树的深度，则平衡二叉树上所有结点的平衡因子只可能是-1、0和1。只要二叉树上有一个结点的平衡因子的绝对值大于1，则该二叉树就是不平衡的。因为AVL树上任何结点的左右子树的深度之差都不超过1，则可以证明它的深度和log₂n是同数量级的(N为结点个数)。因此，它的平均查找长度也和log₂n同数量级。

转载请注明原文地址:https://kaotiyun.com/show/AjSZ777K

本试题收录于：三级数据库技术题库NCRE全国计算机三级分类

三级数据库技术

NCRE全国计算机三级

相关试题推荐

随机试题

最新回复(0)

设平衡的二叉排序树(AVL树)的结点个数为n，则其平均拉索长度为

三级数据库技术

NCRE全国计算机三级

已知R1=0x81000000，R0=0x00112233，在小端模式下执行ARM指令STRR0，[R1]之后，内存0x81000002中的值为()。

ARM处理器采用指令流水线技术，并采用加载／存储指令访问内存，此外，ARM处理器还具有的特点是()。①功能强②功耗大③RISC架构④单周期操作⑤低功耗设计⑥指令长度固定⑦哈佛结构⑧成本高

在基于ARM微处理器为核心的硬件平台上，开发其Linux环境下的应用程序exp1．c。若需要编译后生成expl．c对应的汇编程序，应使用的命令是()。

下面关于Unix与Linux的叙述中，错误的是()。

下面的各嵌入式操作系统中，只有一个与Linux密切相关，它是()。

关于μC／OS—II中处于就绪状态的任务，下面叙述中正确的是()。

Linux内核主要是由5个子系统组成的，如下图所示，其中的A是【73】子系统，B是【74】子系统。

I2C总线被启动后，多个主机在每发送一个数据位时都要对SDA信号线电平进行检测，只要检测的电平与自己发出的电平【63】就会继续占用总线。总线控制遵循的原则是谁先发送【64】电平谁就会掌握对总线的控制权。

Oracle数据库管理系统的Internet解决方案的产品是OracleWebServer，下面列出的条目中，哪一个不属于该产品？

油、气在立式分离器内要经过四次分离，才能脱出比较纯净的天然气。()

领导活动的出发点和归宿是______。

疾病的三间分布是指()。

假定基金在未来5年内将取得平均每年10%的收益率,无风险收益率保持3%不变。那么,为了取得8%的平均收益率,投资于基金的比例y为()

下列关于基金的销售协议的说法中，错误的是()。

下列关于个人经营贷款的表述，错误的是()。

新购进设备的下列企业中，可以享受企业所得税加速折旧优惠的有()。

孔子说“三军可夺帅也，匹夫不可夺志也”；墨子说“志不强者智不达”；诸葛亮说“志当存高远”。这里的“志”指的是()

Sheseldomgoestothetheatre,______?

YouAreWhatYouThinkDoyouseetheglassashalf-fullratherthanhalf-empty?Doyoukeepyoureyeuponthedough-nut(油炸圈