平衡二叉树四种旋转情况

迷南。 2023-10-11 18:27 32阅读 0赞

*  说明

平衡二叉树首先要满足二叉排序树，其次还要满足树中每个节点的平衡因子的绝对值不能超过1，节点的平衡因子 = 左子树高度-右子树高度。若插入后导致二叉排序树失去平衡，此时需要找到对平衡二叉树进行选择操作。

*  LL 类型

插入新节点之后，若导致了树不平衡，此时首先需要找到最小不平衡树的根节点，记作A，A的左右子节点记作B，B的左右子节点记作C，此时A和C就是祖孙关系。

![在这里插入图片描述][b4691377b1b4489090d684feed1d7583.png]  
新插入节点X位于最小不平衡子树的左节点的左节点上，至于x是c的左节点还是右节点无所谓，只关心最上面三个节点的关系，当然，x也可以是c节点。LL型调整的是B这个中间节点，让B右旋一次。

*  RR类型

![在这里插入图片描述][4f112f48518d4d8680076015101b0cab.png]  
RR类型为新插入的节点x位于最小不平衡子树的右节点的右节点上，同理，此时还是只需要让B左旋即可。

*  LR类型

![在这里插入图片描述][dc738c7040b04d3fb3b562af342f978e.png]

LR型为新插入的节点位于最小不平衡子树的左节点的右节点上（x也有可能就是c节点），此时需要先将C节点先左旋再右旋，要旋转两次最终的目的是要将C节点代替A的位置。

*  RL型  
    ![在这里插入图片描述][9b20f8de645941a6b423aac1f39e72a1.png]

RL型为新插入的节点位置最小不平衡子树的右节点的左节点上（x也有可能就是c节点），此时需要先将C节点右旋再左旋，同理，也是要将C代替到A的位置。

*  两个注意点

1.  B和C只和A的位置有关系至于新节点插入到C的左侧还是右侧没有关系。
2.  LLRR是旋转B，LR和RL是旋转C

[b4691377b1b4489090d684feed1d7583.png]: https://img-blog.csdnimg.cn/b4691377b1b4489090d684feed1d7583.png
[4f112f48518d4d8680076015101b0cab.png]: https://img-blog.csdnimg.cn/4f112f48518d4d8680076015101b0cab.png
[dc738c7040b04d3fb3b562af342f978e.png]: https://img-blog.csdnimg.cn/dc738c7040b04d3fb3b562af342f978e.png
[9b20f8de645941a6b423aac1f39e72a1.png]: https://img-blog.csdnimg.cn/9b20f8de645941a6b423aac1f39e72a1.png