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

admin2010-05-13 27

问题设平衡的二叉排序树(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，则可以证明它的深度和logN是同数量级的(N为结点个数)。由此，它的平均查找长度也和logN同数量级。

转载请注明原文地址:https://kaotiyun.com/show/CYSZ777K

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

三级数据库技术

NCRE全国计算机三级

相关试题推荐

随机试题

最新回复(0)

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

三级数据库技术

NCRE全国计算机三级

下面是与ARM处理器存储器相关的叙述，其中错误的是()。

在ARM汇编语言程序设计中常有分支和循环程序的设计，下面指令中应用于分支和循环的指令操作码是()。①B②ADD③AND④LDR⑤STR⑥MOV⑦EOR⑧CMP⑨BX⑩TEQ

按照嵌入式系统的技术复杂程度进行分类，可以把嵌入式系统分为低端系统、中端系统和高端系统三大类。下面属于高端嵌入式系统的是()。

与个人计算机(PC)相比，嵌入式系统具有许多不同的特点。下面不属于嵌入式系统特点的是()。

嵌入式Linux操作系统由用户进程、OS服务组件和Linux内核3个部分组成(如图)，下面选项中正确的是()。

在μC／OS－II中，OSSched()函数是任务调度的前导函数，用于判断进行任务调度的条件是否满足。下列满足条件的变量值为()。

ARM处理器中存储器保护单元英文简写为【53】，它允许ARM处理器【54】GB的地址空间定义为8对域，分别控制8个指令和8个数据内存区域。

从静态的观点看，操作系统的进程由程序段、数据和【】3部分组成。

血液透析过程中，患者出现寒战，继而发热，首要的处理是

发现骨折4周，X线片上骨折周围有较多骨痂，但骨折线仍清晰可见，且有逐日硬化趋向，这种骨折是

乳腺癌出现"酒窝征"的机制是

手少阳三焦经的走向为

对刘某离岗二年以上的行为，医院应当报告准予注册的卫生行政部门的期限是医院未按规定履行报告职责，若导致严重后果，由卫生行政部门给予警告，并对该机构的行政负责人给予

施工企业即从事建筑安装又从事货物销售，如果企业不分别核算或不能准确核算营业税和增值税的，则()。

在()以突出广告主题为主给人以丰富的联想空间,在人气积聚的配合下会产生很好的效果。

存货模式和随机模式是确定最佳现金持有量的两种方法，对这两种方法的以下表述中，正确的有()。(2005年)

《四民月令》（华东师范大学2005年中国通史真题）