早教吧 育儿知识 作业答案 考试题库 百科 知识分享
早教吧考试题库频道 --> 计算机类考试 -->计算机三级 -->

设平衡的二叉排序树(AVL树)的结点个数为n,则其平均拉索长度为A.O(1)B.O(log2n)C.O(n)D.O(nlog2n)

题目

设平衡的二叉排序树(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同数量级。
看了设平衡的二叉排序树(AVL树)...的网友还看了以下:

树突和轴突的数量关系从生物学上看,一个神经元只有1个轴突,多个树突.但是每个轴突都可以有多个分支作 语文 2020-05-13 …

一棵t叉树中要么是叶子结点,要么是有t个分枝的非叶结点.设该t叉树叶子结点个数为s,非叶结点个数n 其他 2020-05-22 …

设树林F对应的二叉树为B,它有m个结点,B的根为P, P的右子树上的结点个数为n,树林F中第一棵树的 计算机类考试 2020-05-23 …

设二叉树根结点的层次为0,一棵高度为n的满二叉树中结点的个数是________。A.2的n次幂个B. 计算机类考试 2020-05-23 …

设二叉树根结点的层次为0,一棵高度为n的满二叉树中结点的个数是A.2的n次幂个B.2的n-1次幂个C 计算机类考试 2020-05-24 …

设二叉树根结点的层次为0,一棵高度为n的满二叉树中结点的个数是______。A.2的n次幂个B.2的 计算机类考试 2020-05-24 …

某树共有n个结点,其中所有分支结点的度为k(即每个非叶子结点的子树数目),则该树中叶子结点的个数为( 计算机类考试 2020-05-26 …

当两个磁体的N相互靠近时,它们将互相,当一个的S极靠近另一个的N极时,它们将互相. 物理 2020-11-01 …

下图是按照一定的规律画出的一列“树型”图,下表的n表示“树型”图的序号,an表示第n个“树型”图中“ 数学 2020-11-08 …

求解关于树枝的一道找规律题有个题不知道你做过没?5个图,第一个图没树枝,第2个2个树枝,第3个5个树 其他 2020-11-24 …