2025年左旋转、右旋转、双旋

编程基础 • 2025-09-22 15:11 • 阅读 59

左旋转、右旋转、双旋https://www.cnblogs.com/shan333/p/15468699.html

1，LL ：– 右旋转（单旋）：为啥LL ，要用右旋转：LL 的意思是：左左，说明左边高度多了一个？

--------------------左边过重失衡，右旋转，把重量匀称一点到右边。 （图片来源小码哥教育）

2，RR： – 左旋转（单旋）：为啥RR ，要用左旋转：RR 的意思是：右右，说明右边高度多了一个？

--------------------右边过重失衡，左旋转，把重量匀称一点到左边。（图片来源小码哥教育）

3，LR – RR：左旋转，然后得到 LL，再右旋转（双旋）：首先看LR-RR结构的最后一对是RR，

■ 为啥RR，要用左旋转：RR 的意思是：右右，说明右边高度多了一个？

--------------------右边过重失衡，左旋转，把重量匀称一点到左边。

■ 然后得到LL，要用右旋转，LL的意思是：左左，说明左边高度多了一个？

--------------------左边过重失衡，右旋转，把重量匀称一点到右边。 （图片来源小码哥教育）

　（图片来源小码哥教育）　　　　　

4，RL – LL：右旋转，然后得到 RR，再左旋转（双旋）：首先看RL-LL 结构最后一对是LL，

■ 为啥LL，要用右旋转：LL 的意思是：左左，说明左边高度多了一个？

--------------------左边过重失衡，右旋转，把重量匀称一点到右边。

■ 然后得到RR，要用左旋转，RR的意思是：右右，说明右边高度多了一个？

--------------------右边过重失衡，左旋转，把重量匀称一点到左边。（图片来源小码哥教育）

　　　（图片来源小码哥教育）　　　

✿ 最后一个字母就是提示失衡的情况：

● LL: 是左边失衡~ 右旋转

● RR:是右边失衡~ 左旋转

● LR-RR: （可以看到该结构最后一对是 RR，是右边失衡）左旋转，处理后得到~LL（是左边失衡），右旋转。

● RL-LL：（可以看到该结构最后一对是 LL，是左边失衡）右旋转，处理后得到~RR（是右边失衡），左旋转。

1，LL型【右旋转】的代码：

g.left = p.right;
p.right = g;

理解：右旋g：将p的right 赋值给了g.left 。【原先模型中，g.left = p】

然后 p.right 指向了g。

【形态理解上：】【g的左边太重了】处理：

g.left = p.right; ● 代码意思：p 要丢给了g 最近的孩子（右孩子），然后 p 爬升了，

p.right = g; ● 代码意思：g 拿了 p 的右孩子后下沉了，p 的右孩子变成了下层的 g。

形象生动地使用现实中天平平衡的理解角度即可啦~

2，如何用代码判断是LL、RR、LR、RL 型的呢？

1，先看父节点是左，则 L：

● 然后再看当前结点是左，则 LL，否则是右，则LR;

2, 若父结点是右，则 R：

● 然后再看当前结点是左，则RL，否则是右，则RR；