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

admin2010-05-13 76

问题设平衡的二叉排序树(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全国计算机三级

某ARM处理器仅工作于Thumb–2状态，该处理器的指令宽度是()。①8位②16位③32位④64位

Linux内核主要由5个子系统组成，下面选项中不属于这5个子系统的是()。

下列选项中用于完成创建任务的自用栈空间的μC／OS–Ⅱ程序源代码的是()。

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

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

实时操作系统(RTOS)有3个主要的实时指标，除响应时间和生存时间之外，另一个指标是在给定时间内可以处理的事件总数，它称为【67】，其英文名称是【68】。

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

设关系R和S的元组个数分别为100和300，关系T是R与S的笛卡尔积，则T的元组个数是

电刷磨出与滑环吻合的弧面，其接触面积应达到()％以上，才能保证电刷与滑环贴合良好。

同时传递电子和质子的辅酶有()(1996年)

男性，26岁。主动脉瓣关闭不全。该患者可有以下临床表现，除了

关于Χ线强度的叙述，错误的是

石决明、草决明的共同作用是

施工中，容易造成瓦斯积聚的做法是()。

物流中心与境外之间进出的货物，除实行出口被动配额管理和中华人民共和国参加或者缔结的国际条约及国家另有明确规定的以外，______。

由于投资的特定经济主体中包括国家，从特定企业的角度看，投资不一定要考虑收益。()

早く子供______寝させた方がいいですよ。