平衡二叉树调整

参考视频：简单粗暴的方式解决平衡二叉树的调整_哔哩哔哩_bilibili

LL型

右旋，右孩子变左孩子

RR型

左旋，左孩子变右孩子

LR型

黄色节点成根节点，其左孩子变右孩子，右孩子变左孩子

RL型

黄色节点成根节点，其左孩子变右孩子，右孩子变左孩子

确定类型

由不平衡的节点向新插入的节点遍历，取前3个结点连起来的形状

如LL、RR、LR、RL

小结

首先确定类型是LL、RR、LR、RL中的那种

如果是LL或RR，先右旋或左旋，再把变换前第2个结点（变换后的根节点）的子节点的位置

如果是LL，因为要右旋，则把其右孩子变为第1个结点（变换前的根节点）的左孩子

如果是RR，因为要左旋，则把其左孩子变为第1个结点（变换前的根节点）的右孩子

如果是LR或RL，直接将第3个结点变为根节点，即将3个结点中最下方或处于中间那个结点作为根节点

把它的左孩子变为右孩子，右孩子变为左孩子，

即左孩子去它（变换后为根节点）的左子树做右孩子。右孩子去它（变换后为根节点）的右子树做左孩子