在平衡二叉树中,插入一个节点后引起不平衡

2025-04-07 03:59:30
推荐回答(2个)
回答1:

因为a结点右子树的平衡因子为0,因此,只能是在左子树上插入的结点,也就是说a的左子树被加高
如果你的平衡因子的定义是左子树的高度-右子树的高度,于是a的平衡因子一定是+2,则进行先左后右,也就是rl型旋转
如果你的平衡因子的定义是右子树的高度-左子树的高度,于是a的平衡因子一定是-2,需要向右旋转,也就是说rr型旋转

回答2:

你是对的,应该是A的左子树根的右子树上出现的不平衡,所以是LR