data structure · 2021-10-30 0

平衡二叉树的失衡与调整

在所有的不平衡情况中,都是按照先寻找 最小不平衡树,然后 寻找所属的不平衡类别,再 根据 4 种类别进行固定化程序的操作。

AVL树插入时的失衡与调整

左旋

(1)节点的右孩子替代此节点位置
(2)右孩子的左子树变为该节点的右子树
(3)节点本身变为右孩子的左子树

右旋

(1)节点的左孩子代表此节点
(2)节点的左孩子的右子树变为节点的左子树
(3)将此节点作为左孩子节点的右子树

1.A的左孩子的左子树插入节点(LL)

只需要执行一次右旋即可

2.A的右孩子的右子树插入节点(RR)

只需要执行一次左旋即可

3.A的左孩子的右子树插入节点(LR)

需要执行两步操作,使得旋转之后为 原来根结点的左孩子的右孩子作为新的根节点

(1)对失衡节点 A 的左孩子 B 进行左旋操作,即上述 RR 情形操作
(2)对失衡节点 A 做右旋操作,即上述 LL 情形操作

4.A的右孩子的左子树插入节点(RL)

需要执行两步操作,使得旋转之后为 原来根结点的右孩子的左孩子作为新的根节点

(1)对失衡节点 A 的右孩子 C 进行右旋操作,即上述 LL 情形操作
(2)对失衡节点 A 做左旋操作,即上述 RR 情形操作

LL , LR ,RR ,RL其实已经为我们提供了最后哪个结点作为新的根指明了方向。如 LR 型最后的根结点为原来的根的左孩子的右孩子,RL 型最后的根结点为原来的根的右孩子的左孩子。只要记住这四种情况,可以很快地推导出所有的情况。