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

题目

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

A.LL

B.LR

C.RL

D.RR

解答

正确答案是 B

空树也是一棵平衡二叉树，且平衡因子为0。
所以结点A没有右孩子结点（右孩子的平衡因子为0），而A的左孩子节点的左子树为空，有一个右孩子节点（A的左孩子的平衡因子为-1），所以做左-右（LR）双旋转

C 2条回复评论

墨色槐

真棒！茅塞顿开的感觉。

发表于 2021-09-08 23:15:00

伸手揪云

可以假设为根节点没有右子树，左节点的左子树为空，而有一个右子树节点。所以做左-右双旋转

发表于 2018-10-12 11:58:10