2. 公务员类
  3. 在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A，并已知A的左孩

在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A，并已知A的左孩

练习题库2022-08-02  58
问题 在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A，并已知A的左孩子的平衡因子为0，右孩子的平衡因子为1，则应作()型调整以使其平衡。A.LLB.LRC.RLD.RR
选项 A.LL
B.LR
C.RL
D.RR
答案 C
解析 平衡二叉树是在构造=叉排序树的过程中，每当插入一个新结点时，首先检查是否因插入新结点而破坏了二叉排序树的平衡性，若是，则找出其中的最小不平衡子树，在保持二叉排序树特性的前提下，调整最小不平衡子树中各结点之间的链接关系。进行相应的旋转，使之成为新的平衡子树。具体步骤如下：(1)每当插入一个新结点，从该结点开始向上计算各结点的平衡因子，即计算该结点的祖先结点的平衡因子，若该结点的祖先结点的平衡因子的绝对值均不超过1，则平衡=叉树没有失去平衡，继续插入、结点；(2)若插入结点的某祖先结点的平衡因子的绝对值大于1，则找出其中最小不平衡子树的根结点；(3)判断新插入的结点与最小不平衡子树的根结点的关系，确定是哪种类型的调整；(4)如果是LL型或RR型，只需应用扁担原理旋转一次，在旋转过程中，如果出现冲突，应用旋转优先原则调整冲突；如果是LR型或LR型，则需应用扁担原理旋转两次，第一次最小不平衡子树的根结点先不动，调整插入结点所在子树，第二次再调整最小不平衡子树。在旋转过程中，如果出现冲突，应用旋转优先原则调整冲突；(5)计算调整后的平衡二叉树中各结点的平衡因子，检验是否因为旋转而破坏其他结点的平衡因子，以及调整后的平衡二叉树中是否存在平衡因子大于1的结点。结合上面的知识点，对于题目中的情况应该选择RL型调整。
转载请注明原文地址:https://tihaiku.com/gongwuyuan/2554128.html
本试题收录于： 计算机 电网题库国家电网招聘分类

计算机 电网

国家电网招聘

相关试题推荐
随机试题
最新回复(0)