设平衡的二叉排序树(AVL树)的结点个数为n，则其平均查找长度的数量级为 ______。

admin2010-05-13 70

问题设平衡的二叉排序树(AVL树)的结点个数为n，则其平均查找长度的数量级为 ______。

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

答案2

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

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

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

三级数据库技术

NCRE全国计算机三级

相关试题推荐

随机试题

最新回复(0)

设平衡的二叉排序树(AVL树)的结点个数为n，则其平均查找长度的数量级为 ______。

三级数据库技术

NCRE全国计算机三级

下面关于S3C2410中断控制器的叙述中，错误的是()。

以下不属于转移(分支)类指令的是()。

ARM处理器当前运算操所产生的标志位记录在以下()寄存器中?

手机最基本的功能是打电话和接听电话，在此过程中手机必须对话音信号进行处理，下面有关叙述中错误的是()。

以下不属于ARM处理器的特点是()。

下列不是实时操作系统的是()。

JTAG是指满足IEEE1149规范的边界扫描测试方法及TAP接口，是一种用于片上【77】技术的统称。JTAG接口标准中规定了TAP接口所使用的5个信号，它们分别是【78】、TMS、TDI、TDO和TRST。

IP协议在计算机网络的互连中起着重要的作用。下面有关IP地址的叙述中，错误的是()。

政策不仅要告诉人们什么是该做的，什么是不该做的，而且还要使人们明白，为什么要这样做而不那样做，怎样才能做得更好。这表明政策具有()

下列五输穴中，属于本经子穴的是

硝苯地平治疗高血压过程中，患者出现踝部水肿，发生原因是

关于法和道德之间关系的正确表述是()。

关于运用假设开发法评估某酒店在建工程的投资价值(其中开发完成后的房地产价值采用收益法测算)的说法，正确的有()。

“申报日期”栏应填()。

出卖人出卖交由承运人运输的在途标的物，除另有约定外，毁损、灭失的风险自合同成立时起由()承担。

溢出效应是指一个组织在进行某项活动时．不仅会产生活动所预期的效果，而且会对组织之外的人或社会产生影响。根据上述定义，下列属于溢出效应的是：

A、Ontheirownelectronicmonitors.B、Onthepassword-protectedwebsite.C、Onthesportschairman’scomputer.D、Onthecolorscr