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

admin2010-05-13 53

问题设平衡的二叉排序树(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://www.kaotiyun.com/show/AjSZ777K

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

三级数据库技术

NCRE全国计算机三级

相关试题推荐

随机试题

最新回复(0)

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

三级数据库技术

NCRE全国计算机三级

AMBA是ARM公司公布的总线协议，是用于连接和管理片上系统中功能模块的开放标准和片上互连规范。下面列出的ARM处理芯片中的4个组件，哪一个组件是挂在AMBA的系统总线上的?()

以下ARM指令中源操作数属于寄存器寻址的指令是()。

以下是有关TCP／IP协议中IP地址格式(IPv4)的叙述，其中错误的是()。

关于ARM处理器的工作模式，以下说法正确的是()。

数字图像的文件格式有多种，不同的文件格式采用不同的编码方法，具有不同的特点，适合不同的应用。通常，数码相机中大多使用【43】图像文件格式，www网页中具有动画效果的插图或剪贴画其文件格式是【44】。

路由器用于2个或多个计算机网络的互连，有关路由器IP地址的下列说法中，正确的是()。

与个人计算机(PC)相比，嵌入式系统具有许多不同的特点。下面不属于嵌入式系统特点的是()。

ARM处理器中存储器保护单元英文简写为【53】，它允许ARM处理器【54】GB的地址空间定义为8对域，分别控制8个指令和8个数据内存区域。

下面关于互联网(Internet)的叙述中错误的是()。

室性心动过速的正确描述是

软胶囊囊壁由明胶、增塑剂、水三者构成，其重量比例通常是()

工业企业对外销售生产用材料时，下列会计处理中，正确的处理方法是()。

下列有关家用电器工作原理的说法，不正确的是（）。

与2007年相比，2008年北京市60－69岁的老年人多了()。

下面属于发展心理学范畴的学科有

Whatattractscustomers?Obviouslythequalityofaproductdoes,butvisualimages【C1】______agreatdeal.Itisnotonlytheim

强身健体