首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
设平衡的二叉排序树(AVL树)的结点个数为n,则其平均查找长度的数量级为 ______。
设平衡的二叉排序树(AVL树)的结点个数为n,则其平均查找长度的数量级为 ______。
admin
2010-05-13
39
问题
设平衡的二叉排序树(AVL树)的结点个数为n,则其平均查找长度的数量级为 ______。
选项
A、O(1)
B、0(log
2
n)
C、O(n)
D、0(nlog
2
n)
答案
2
解析
平衡二叉树又称AVL树。它或者是一棵空树,或者是具有下列性质的二叉树:它的左子树和右子树都是平衡二叉树,且左子树和右子树的深度之差的绝对值不超过1。若将二叉树上结点的平衡因子BF定义为该结点的左子树的深度减去它的右子树的深度,则平衡二叉树上所有结点的平衡因子只可能是-1、0和1。只要二叉树上有一个结点的平衡因子的绝对值大于1,则该二叉树就是不平衡的。因为AVL树上任何结点的左右子树的深度之差都不超过1,则可以证明它的深度和logN是同数量级的(N为结点个数)。由此,它的平均查找长度也和logN同数量级。
转载请注明原文地址:https://jikaoti.com/ti/J1C7FFFM
本试题收录于:
三级数据库技术题库NCRE全国计算机三级分类
0
三级数据库技术
NCRE全国计算机三级
相关试题推荐
下面关于Linux内核的叙述中,错误的是()。
以下各项不属于开源嵌入式操作系统的是()。
下面哪一种接口不是无线通信接口?()。
以下不属于ARM处理器的特点是()。
酒店客房的门锁系统是由总台服务器和若干客房指纹锁组成,其基本功能具体描述如下:a、客房的指纹锁与总台服务器之间通过通信网络连接。b、旅客在总台登记住宿时,录入其指纹信息,并提取其特征值存储在总台服务器中。同时录入一个密码(若干位数字组成),以备指纹无法
在数字音频信息数字化过程中,正确的处理顺序是()。
在μC/OS–II操作系统下,由中断服务子程序代码完成的操作一定包括()。
实时系统对时间约束要求的严格性,使【73】性成为实时系统的一项重要性能要求,它是指RTOS能够对外部事件的【74】时间和实时任务的执行时间进行判断,以确定被事件触发的实时任务能否在规定的时间内完成。
UART传送一个字符时有固定的格式,如下图所示。图中①和②分别是【61】位和【62】位。
Linux操作系统内核的网络模块可分为两部分:一部分提供对各种网络资源访问的控制,称为网络【75】;另一部分提供对各种网络硬件的支持,称为网络【76】。
随机试题
修改权
泰勒在科学管理理论中提出了例外原则,其目的是解决【】
天王补心丹中的三参是
会计电算化环境下,属于审核记账员的责任是()。
某企业编制“直接材料预算”,预计第四季度期初存量400千克,预计生产需用量2000千克,预计期末存量350千克,材料单价为10元,若材料采购货款有80%在本季度内付清,另外20%在下季度付清,则该企业预计资产负债表年末“应付账款”项目为(
请选择最适合的一项填入问号处,使之符合整个图形的变化规律()。
在我国,关于犯罪和刑罚的法律规范可以由()制定。
ThesuccessofAugustusowedmuchtothecharacterofRomantheorizingaboutthestate.TheRomansdidnotproduceambitiousblu
When______difficultproblems,weshouldoftentakeanoptimisticattitude.
Tallmenaremorelikelytohavechildrenthantheirverticallychallengedfriendsbecausewomenfindheightattractive,anews
最新回复
(
0
)