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

admin2010-07-20 42

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

选项 A、O(1)
B、O(log2n)
C、O(n)
D、O(nlog2n)

答案B

解析平衡二叉树又称AVL树，它或者是一棵空树，或者是具有下列性质的二叉树：它的左子树和右子树都是平衡二叉树，且左子树和右子树的深度之差的绝对值不超过1，若将二叉树上节点的平衡因子BF定义为该节点的左子树的深度减去它的右子树的深度，则平衡二叉树上所有节点的平衡因子只可能是-1、0和1。只要二叉树上有一个节点的平衡因子的绝对值大于1，则该二叉树就是不平衡的。因为AVL树上任何节点的左右子树的深度之差都不超过1，则可以证明它的深度和log2n是同数量级的(n为节点个数)。因此，它的平均查找长度也和log2n同数量级。

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

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

三级数据库技术

NCRE全国计算机三级

相关试题推荐

随机试题

最新回复(0)

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

三级数据库技术

NCRE全国计算机三级

下述哪一条是由于关系模式设计不当所引起的问题？

在关系数据库系统中，当合并两个关系时，用户程序可以不变。这是

下列关于中断的叙述中，错误的是

SQL语言中对权限回收的命令是【】。

在数据库并发控制中，两个或更多的进度同时处于等待其他进程所占用资源的状态，称为【】。

对于给出的一组权w={10，12，16，21，30}，通过霍夫曼算法求出的扩充二叉树的带权外部路径长度为

关系模式分解的等价性标准主要有两个，它们是分解具有无损连接性和分解【】。

汇编语言是一种符号语言，通常用指令功能的英文词缩写代替操作码。助记符MOV表示的指令是_________。

对于关键码序列18，30，35，10，46，38，5，40，进行堆排序(假定堆的根结点是最小关键码)，在初始建堆过程中需进行的关键码交换次数为【】。

下面不属于使用视图的优点的是

男性，30岁，有2年吸烟史。主诉：牙龈自动出血伴牙龈疼痛、口臭3天，无发热。检查：牙石(+++)，龈缘呈虫蚀状，表面覆盖坏死假膜，易于擦去。最可能的诊断是

作用于酪氨酸激酶受体通路的抗肿瘤药物是作用于芳香化酶的抗肿瘤药物是

下列关于施工总承包管理模式的说明，正确的是（）。

从所给的四个选项中，选择最合适的一个填入问号处，使之呈现一定的规律性：()

(1989年)若3a2－5b＜0，则方程χ5＋2aχ3＋3bχ＋4c＝0【】

Mankind’sfascinationwithgoldisasoldascivilizationitself.TheancientEgyptianses-teemedgold,whichhadreligioussign

WhatdowemeanbyaperfectEnglishpronunciation?Inone【C1】______therearemanydifferentkindsofEnglishastherearespeak

Forgetfit,tannedandsporty—thenewgenerationofAustraliansisfastbecomingfat,paleandlazy.Aloveofjunkfood,tele