本文共 558 字，大约阅读时间需要 1 分钟。

LL

LL，由于在结点A的左孩子（L）的左子树（L）上插入了新结点，50的平衡因子由1增加到了2，导致以50为根的子树失去平衡，需要一次顺时针的旋转，使得50的左孩子40右旋代替50成为根节点，50右旋成为40的右子树的根节点，50原来的60继续作为50的右子树，因为50占据了45的位置，又因为45比40大且比50小，45只能放在50的左子树，30继续作为40的左子树。

 RR

由于在结点40的右孩子（R）的右子树（R）上插入了新结点，A的平衡因子由-1减至-2，导致以40为根的子树失去平衡，需要一次逆时针（向右）的旋转操作，将40的右孩子向左旋转代替40成为根节点，将40结点向左下旋转成为50的左子树的根节点，而50的原左子树45因为40占据了50左子树的位置，45又比50小比40大，因此作为40的右子树，60、30继续分别作为B的右子树和A的左子树

 LR

由于节点50的左子树的右孩子添加节点，使得50处不平衡，因此要进行旋转，先让左子树的右孩子45左旋，45作为50的左子树的根节点，40作为45的左孩子，42的位置被占，又比40大，作为40的右孩子，变成红色的情况

接着，45右旋，成为根节点，50作为45的右孩子。变成黄色。

 RL

和LR类似，先右孩子旋转，变成红色，此时的右孩子再左旋，成为黄色。 

转载地址：https://blog.csdn.net/weixin_58104242/article/details/122570598 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！