首页 > 试题广场 >

在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点

[单选题]

在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A，并已知A的左孩子的平衡因子为0右孩子的平衡因子为1，则应作(    ) 型调整以使其平衡。 

  • LL
  • LR
  • RL
  • RR
查看正确选项
添加回答
夕一啊头像 夕一啊
搬运一下

总结：首先找到最低的不平衡节点A，LL就是在左子树的左孩子下插入，LR就是在左子树的有孩子下插入，RR就是右子树的右孩子下插入，RL就是在右子树的左孩子下插入

1. LL型调整。在B点的左子树上插入一个节点。插入后B点的左子树的平衡因子变为1，A节点的平衡因子变为了2。这样可以看出来A节点为根节点的子树是最小不平衡子树。调整时，将A的左孩子B向右旋转代替A称为原来不平衡子树的根节点，将A的节点右下旋转称为B的右子树的根节点，而B的原右子树变为A的左子树。

2. RR型调整操作

在A节点的右孩子的右子树上插入节点，使得A节点的平衡因子由-1变为-2而引起的不平衡所进行的调整操作。调整操作大致一样，看图就可以明白了。
3. LR型的调整操作。在A节点的左孩子的右子树上插入节点，使得A节点的平衡因子由1变为了2而引起的不平衡所进行的调整的操作。调整过程如图：
4. RL型的调整操作。 不多 说了，直接 上图
：
-----------------------------------------------------------------------------------------------------------------------
再 看这个题目，最低的不平衡结点为 A, 并已知 A 的左孩子的平衡因子为 0 右孩子的平衡因子为 1，这些平衡因子都是在插入造成不平衡之后的数值，所以最简单的插入后的树如下图：
    A
   /   \
左   右
      /  \
    o    o
   /
1

或者
    A
   /   \
左   右
      /  \
    o    o
     \
       1
都是可以的，从A看，都是右孩子的左孩子下插入，所以是RL型

编辑于 2017-07-11 14:42:04 回复(5)
菲尼克斯弗兰克头像 菲尼克斯弗兰克
平衡因子为1表示：左孩子 - 右孩子的高度 = 1
0：左孩子高度 = 右孩子高度
-1：右孩子高度 - 左孩子高度 = 1
题目中说的是A点右孩子的平衡因子是1 故立即推=> 右孩子的左孩子高度多一层 属于RL型
发表于 2018-11-05 10:07:35 回复(4)
菜牛1号头像 菜牛1号
为什么都是右孩子的左孩子插入节点？？？
编辑于 2017-07-31 10:26:29 回复(0)
simon_free头像 simon_free
某结点的左子树与右子树的高度(深度)差即为该结点的平衡因子
发表于 2023-11-11 15:39:50 回复(0)
張三同学头像 張三同学
平衡二叉树的性质：
    左子树和右子树的高度之差的绝对值小于等于1
    左子树和右子树也是平衡二叉树

平衡因子=结点左子树的高度-结点右子树的高度


发表于 2023-03-01 22:29:47 回复(0)
梦境迷离头像 梦境迷离
当初没有好好学习转换。。。。
发表于 2018-02-04 13:44:10 回复(0)
木易几点头像 木易几点
<
发表于 2017-08-26 09:28:25 回复(0)
提交观点

问题信息

树
上传者：Letitia
难度：
7条回答 11919浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号