早教吧考试题库频道 --> 计算机类考试 -->计算机三级 -->
设平衡的二叉排序树(AVL树)的结点个数为n,则其平均检索长度为A.O(1)B.O(log2n)C.O(n)D.O(n log2n
题目
设平衡的二叉排序树(AVL树)的结点个数为n,则其平均检索长度为
A.O(1)
B.O(log2n)
C.O(n)
D.O(n log2n)
参考答案
正确答案:B
解析:平衡二叉树又称AVL树,它或者是一棵空树,或者是具有下列性质的二叉树:它的左子树和右子树都是平衡二叉树,且左子树和右子树的深度之差的绝对值不超过1,若将二叉树上结点的平衡因子BF定义为该结点的左子树的深度减去它的右子树的深度,则平衡二叉树上所有结点的平衡因子只可能是-1、0和1。只要二叉树上有一个结点的平衡因子的绝对值大于1,则该二叉树就是不平衡的。因为AVL树上任何结点韵左右子树的深度之差都不超过1,则可以证明它的深度和log2n是同数量级的(N为结点个数)。因此,它的平均查找长度也和log2n同数量级。
解析:平衡二叉树又称AVL树,它或者是一棵空树,或者是具有下列性质的二叉树:它的左子树和右子树都是平衡二叉树,且左子树和右子树的深度之差的绝对值不超过1,若将二叉树上结点的平衡因子BF定义为该结点的左子树的深度减去它的右子树的深度,则平衡二叉树上所有结点的平衡因子只可能是-1、0和1。只要二叉树上有一个结点的平衡因子的绝对值大于1,则该二叉树就是不平衡的。因为AVL树上任何结点韵左右子树的深度之差都不超过1,则可以证明它的深度和log2n是同数量级的(N为结点个数)。因此,它的平均查找长度也和log2n同数量级。
看了设平衡的二叉排序树(AVL树)...的网友还看了以下:
设a、b、c、d是四个整数,且使得m=(ab+cd)的平方-1/4(a的平方+b的平方-c的平方-d 数学 2020-03-31 …
某次考试A、B、C、D、E五人的成绩统计如下:A、B、C、D的平均分是75分;A、C、D、E的平均分 数学 2020-03-31 …
如图1所示,真空中有竖直放置的平行金属板A、B和水平放置相距为d的平行金属板C、D,C、D板长为L 物理 2020-04-06 …
■在线等!高一数学,数列证明■已知a,b,c,d成等比数列(公比为q),求怔:(1)如果q≠-1, 数学 2020-05-14 …
A的平方+B的平方=C的平方+D的平方+E的平方=365其中A和B是连续的自然数,C,D,E也是连 数学 2020-05-19 …
在一次考试中,A、B、C、D四人的得分是不小于90且互不相同的整数,四人的平均分也是整数,A、B、 数学 2020-05-20 …
在一次考试中,A、B、C、D四人的得分是不小于90且互不相同的整数,四人的平均分也是整数,A、B、 数学 2020-05-21 …
21点之前回答呀.有分A.B.C.D四个数中,A>B>C>D,且B是奇数.A.B.C的平均数是15 数学 2020-05-23 …
如果A+B>C+D(A,B,C,D都大于0),那么A的平方加上B的平方的和也大于C的平方加上D的平 其他 2020-06-03 …
A、B、C、D四人,A的体重比B重7千克,A、B的平均体重比A、B、D的平均体重多1千克,B、C、 数学 2020-06-15 …