day062：平衡二叉树——左旋、右旋

二叉树、平衡二叉树的介绍：day061：二叉树、二叉查找树、平衡二叉树_ZQyyds：）的博客-CSDN博客

目录

一、平衡二叉树的左旋

1.为什么要左旋、右旋？

2.什么是左旋？

3.图解

 二、平衡二叉树的右旋

1.什么是右旋？

2.图解

 三、总结

1.往哪旋：

2.关于多余的节点（子树上的节点）

---

一、平衡二叉树的左旋

1.为什么要左旋、右旋？

防止二叉树出现“长短腿”的情况；便于二叉树查找

2.什么是左旋？

左旋：指将根节点的右侧往左拉，原先的右子节点变成新的父节点，并把多余的左子节点出让，给已经降级的根节点当右子节点

3.图解

（1）原先的根节点为7，右子节点10 有个左子节点9

（2）暂且不看10的左子节点，先将二叉树左旋

 （3）左旋后如下图

（4）左旋后，将原来10的左子节点9，给已经降级的原根节点 7 做右子节点即可

 二、平衡二叉树的右旋

1.什么是右旋？

右旋：指将根节点的左侧往右拉，原先的左子节点变成新的父节点，并把多余的右子节点出让，给已经降级的根节点当左子节点

2.图解

（1）原先的根节点为7，左子节点4有个右子节点5

（2）暂且不看右子节点5，先将二叉树右旋，新的父节点为4

（3）再将原右子节点5，作为已降级的7的左子节点即可

 三、总结

1.往哪旋：

大致：

左子树高：右旋；右子树高：左旋；

平衡二叉树有左左、右右、左右、右左四种旋转情况，具体怎么旋视情况而定

2.关于多余的节点（子树上的节点）

左旋后当已降级的右节点；右旋后当已降级的左节点