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

admin2010-05-13 58

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

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

三级数据库技术

NCRE全国计算机三级

相关试题推荐

随机试题

最新回复(0)

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

三级数据库技术

NCRE全国计算机三级

下面关于Linux内核的叙述中，错误的是()。

下面关于嵌入式系统使用的存储器的叙述中，错误的是()。

在ARM汇编语言程序设计中，经常用到子程序设计及调用，与子程序设计与调用无关的指令或伪指令是()。

下面有关RVDS开发工具套件的描述语句中，不正确的描述是()。

下面有关RVDS开发工具套件的描述语句中，不正确的描述是()。

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

数据模型可分为概念数据模型和结构数据模型，层次模型是()数据模型。

至(14)题基于以下的5阶B树结构，该B树现在的层数是2。(13)往该B树中插入关键码72后，该B树的第2层的结点数为

为了保证事务的正确执行，数据库系统维护以下事务特性：Ⅰ．原子性Ⅱ．一致性Ⅲ．隔离性Ⅳ．持久性

()是指公司必须依照法律规定或证券监管机构和证券交易所的指令将有关信息予以公开，不得有重大遗漏。

党提出把工作重点由乡村转移到城市的会议是()

某一酶促反应的速度为最大反应速度的80％时，底物浓度等于

患者，女，65岁。全口义齿初戴时，感觉就位时疼痛，戴入后缓解。原因是

婴儿，3个月，体重5kg，母亲经常出差到外地工作，无法母乳喂养，改为牛乳喂养。该婴儿每日需8％糖牛乳量应为

安装在工作区地面上的接线盒应()。

下列选项中，对股东会该项决议投反对票的股东能够请求公司按照合理的价格收购其股权的有()。

AncientOlympicGamesAmateurathletesfromallovertheworldtakepartinthemodemOlympicGames.Anynationmayentera

A、Alan’sshowingup.B、Alan’sillustration.C、Alan’sjoke.D、Alan’sgift.C