首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
设平衡的二叉排序树(AVL树)的结点个数为n，则其平均检索长度为
设平衡的二叉排序树(AVL树)的结点个数为n，则其平均检索长度为
admin
2010-05-13
37
问题
设平衡的二叉排序树(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://kaotiyun.com/show/j3SZ777K
本试题收录于：
三级数据库技术题库NCRE全国计算机三级分类
0
三级数据库技术
NCRE全国计算机三级
相关试题推荐
在ARM处理器中，用于存储器保护的部件用英文缩写为【47】，用来完成虚拟地址到物理地址转换的部件英文缩写为【48】。
下面有关嵌入式系统开发的说明中，错误的是()。
下面关于嵌入式系统存储器的叙述中，错误的是()。
电动汽车充电桩(示意图如下图所示)以S3C2410芯片为核心，并外加其他功能电路来进行设计，其基本功能描述如下：a、充电桩支持2种充电方式，一种是固定金额方式，如：充300元的电能。那么，所充电能的金额等于300元后自动停止充电；另一种是随机充电，即：
下面对于Linux内核的叙述，错误的是()。
Thumb-2指令集提供了专门用于开、关中断的专用指令，关外部中断使用的指令为：__________【51】，开外部中断的指令为：__________【52】。
下面关于嵌入式系统使用的存储器的叙述中，错误的是()。
嵌入式系统是一类特殊的计算机系统。下列产品中不属于嵌入式系统的是()。
若某嵌入式系统的应用程序基于μC／OS—II操作系统平台来开发，那么，应用程序的main()函数中，需要用函数【79】来创建任务。创建任务前用函数【80】来初始化μC／OS—II。
在完全二叉树的顺序存储中，若结点i有左子女，则其左子女是结点()。
随机试题
《中国药典》的组成包括()。
“________”可以显示Word2010文档的打印结果外观，主要包括页眉、页脚、图形对象、分栏设置、页面边距等元素，是最接近打印结果的页面视图。
在下列选项中，属于主物和从物关系的是()。A．甲的拖拉机和拖犁B．甲的手表和乙的表带C．房屋和天花板D．丙的钥匙和丁的锁
藏药方剂中，十味黑冰片丸的功能为()。
利率挂钩类理财产品的收益率仅取决于利率的走势。()
A房地产开发有限公司(以下简称“A公司”)建造开发销售商品房，2010年10月该公司在当地有关媒体刊登售楼广告。内称：该楼盘为绿色生态住宅，小区环境优美典雅，绿化率为48％，并建有高档会所；为此，该楼盘的房价确定为每平方米8500元(均价)。某公司职员李某
鲁迅称赞《诗经》是“史家之绝唱，无韵之离骚”。()
一只木桶能盛多少水，并不取决于最长的那块木板，而是取决于最短的那块木板。对此，你怎么看?
主张用“理解”和“解释”的立场与方法研究教育问题的教育学流派是()。
WhenIbentdowntotiemyshoelace,theseatofmytrousers____.
最新回复
(
0
)
