数据结构（关于AVL树）
设有一个关键码的输入序列{55,31,11,37,46,73,63},(1)从空树开始构造平衡二叉搜索树,画出每加入一个新结点时二叉树的形态。若发生不平衡,指明需做的平衡...
设有一个关键码的输入序列 { 55, 31, 11, 37, 46, 73, 63 },
(1) 从空树开始构造平衡二叉搜索树, 画出每加入一个新结点时二叉树的形态。若发生不平衡, 指明需做的平衡旋转的类型及平衡旋转的结果。
(2) 计算该平衡二叉搜索树在等概率下的查找成功的平均查找长度。 展开
(1) 从空树开始构造平衡二叉搜索树, 画出每加入一个新结点时二叉树的形态。若发生不平衡, 指明需做的平衡旋转的类型及平衡旋转的结果。
(2) 计算该平衡二叉搜索树在等概率下的查找成功的平均查找长度。 展开
1个回答
展开全部
插入11时，发生向右的单旋转
插入46时发生先左后右的双旋转
插入73时发生向左的单旋转
插入63时发生先右后左的双旋转
最后结果如下：
根 46
第二层 31 63
第三层 11 37 55 73
其形态就是一颗完全二叉树
于是查找成功时的平均查找长度为(1 * 1 + 2 * 2 + 4 * 3) / 7 = 17 /7
插入46时发生先左后右的双旋转
插入73时发生向左的单旋转
插入63时发生先右后左的双旋转
最后结果如下：
根 46
第二层 31 63
第三层 11 37 55 73
其形态就是一颗完全二叉树
于是查找成功时的平均查找长度为(1 * 1 + 2 * 2 + 4 * 3) / 7 = 17 /7
本回答由提问者推荐
已赞过
已踩过<
评论
收起
你对这个回答的评价是？
美林数据技术股份有限公司
2023-07-25 广告
常用的大数据工具有以下这些：* Apache Cassandra：一种分布式的开源数据库。* Apache Drill：一种开源分布式系统，用于大规模数据集的交互分析。* Apache Elasticsearch：是Apache Lucen...
点击进入详情页
本回答由美林数据技术股份有限公司提供
推荐律师服务：
若未解决您的问题，请您详细描述您的问题，通过百度律临进行免费专业咨询
