数据结构（关于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
本回答由提问者推荐
已赞过
已踩过<
评论
收起
你对这个回答的评价是？
景联文科技
2024-06-11 广告
杭州景联文科技有限公司专注于大模型数据集的研发与应用。我们深知，在人工智能飞速发展的时代，数据是驱动模型优化的核心动力。因此，我们致力于构建丰富、多元的大模型数据集，涵盖各行各业，为AI模型提供充足的“养分”。通过不断积累与优化，我们的数据...
点击进入详情页
本回答由景联文科技提供
推荐律师服务：
若未解决您的问题，请您详细描述您的问题，通过百度律临进行免费专业咨询
