首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
设平衡的二叉排序树(AVL树)的结点个数为n,则其平均拉索长度为
设平衡的二叉排序树(AVL树)的结点个数为n,则其平均拉索长度为
admin
2010-05-13
28
问题
设平衡的二叉排序树(AVL树)的结点个数为n,则其平均拉索长度为
选项
A、O(1)
B、O(log
2
n)
C、O(n)
D、O(nlog
2
n)
答案
2
解析
平衡二叉树又称AVL树,它或者是一棵空树,或者是具有下列性质的二叉树:它的左子树和右子树都是平衡二叉树,且左子树和右子树的深度之差的绝对值不超过1,若将二叉树上结点的平衡因子BF定义为该结点的左子树的深度减去它的右子树的深度,则平衡二叉树上所有结点的平衡因子只可能是-1、0和1。只要二叉树上有一个结点的平衡因子的绝对值大于1,则该二叉树就是不平衡的。因为AVL树上任何结点的左右子树的深度之差都不超过1,则可以证明它的深度和log
2
n是同数量级的(N为结点个数)。因此,它的平均查找长度也和log
2
n同数量级。
转载请注明原文地址:https://jikaoti.com/ti/tWC7FFFM
本试题收录于:
三级数据库技术题库NCRE全国计算机三级分类
0
三级数据库技术
NCRE全国计算机三级
相关试题推荐
嵌入式系统使用的存储器有多种类型,按照所处物理位置可分为片内存储器和【57】_______存储器以及外部存储设备,按照存储信息的不同又可分为【58】_______存储器和数据存储器。
数字视频信息的数据量相当大,通常需要进行压缩处理之后才进行传输和存储。目前数字有线电视所传输的数字视频采用的压缩编码标准是()。
AMBA是ARM公司公布的总线协议,是用于连接和管理片上系统中功能模块的开放标准和片上互连规范。下面列出的ARM处理芯片中的4个组件,哪一个组件是挂在AMBA的系统总线上的?()
下面关于Linux操作系统的论述中,错误的是()。
【63】Flash和NANDFlash是现在市场上两种主要的闪存技术,前者以【64】为单位随机存取,后者以页(行)为单位随机存取。
下面有关片上调试技术的描述语句中,不恰当的是()。
μC/OS–Ⅱ中调用中断退出函数OSIntExit()标志着中断服务子程序的【75】,OSIntExit()将中断嵌套层数计数器的值【76】。
数字音频的比特率(码率)指的是每秒钟的数据量,它与取样频率、量化位数、声道数目、使用的压缩编码方法等密切相关。假设数字音频的比特率为16kb/s,其取样频率是8kHz,单声道,量化位数为8位,采用压缩编码,那么压缩比是()。
以下关于ARM状态寄存器CPSR的说法错误的是()。
随机试题
Thegarden______astrongfragrance.
A.手足抽搐B.发热C.声音嘶哑D.饮水呛咳E.窒息喉上神经损伤
不属于拔罐法中的火吸法的有
住房公积金个人住房贷款和商业性个人住房贷款的区别包括()。
鲁迅曾说:“人有人性,狼有狼性。我希望中国人多一点狼性,少一点人性。”用现代教育改革新理念的眼光来看,鲁迅实际上是在提倡()
数字推理:0.001,0.002,0.006,0.024,()。
斯大林格勒保卫战:希特勒
求∫0πdχ.
设A=,则A与B
给定程序MODI1.C中函数fun的功能是:为一个偶数寻找两个素数,这两个素数之和等于该偶数,并将这两个素数通过形参指针传回主函数。和等于该偶数,并将这两个素数通过形参指针传回主函数。请改正函数fun中指定部位的错误,使它能得出正确的结果。
最新回复
(
0
)