数据结构与算法(九)：AVL树详细讲解
1 /** 2 * 左旋操作 3 * @param t 4 */ 5 private void left_rotate(AVL<E>.Node<E> t) { 6 if (t != null) { 7 Node tr = t.right; 8 //将t结点的右孩子的左结点设置为t结点的右孩子 9 t.right = tr.left; 10 if (tr.left != null) { 11 //重置其父节点12 tr.left.parent = t; 13 } 14 //t结点旋转下来，其右孩子相当于替换t结点的位置15 //所以这里同样需要调整其右孩子的父节点为t结点的父节点16 tr.parent = t.parent; 17 //整棵树只有根结点没有父节点，这里检测我们旋转的是否为根结点18 //如果是则需要重置root结点19 if (t.parent == null) { 20 root = tr; 21 } else { 22 //如果t结点位于其父节点的左子树，则旋转上去的右结点则23 //位于父节点的左子树，反之一样24 if (t.parent.left == t) { 25 t.parent.left = tr; 26 } else if (t.parent.right == t) { 27 t.parent.right = tr; 28 } 29 } 30 //将t结点设置为其右子树的左结点31 tr.left = t; 32 //重置t结点的父节点33 t.parent = tr; 34 } 35 }
代码基本上都加上了备注，对比左旋流程仔细分析一下，这里需要注意一下，旋转完后结点的父节点都需要重置。
好了，对于左旋操作，相信你已经有一定了解了，如果还有不明白的地方可以自己仔细想一下，实在想不明白可以关注我公众号联系本人单独交流。
接下来我们看看右旋是怎么回事。
右旋操作
上图就是对Y结点进行右旋操作的流程，有了左旋操作的基础这里应该很好理解了。
第一步同样仅仅将Y结点右旋，成为X的一个结点，同样这里会出现问题X有了三个结点。
第二步，如果一开始Y左子树存在右结点，上图中也就是B结点，则将其设置为Y的右孩子。
到这里一个标准的右旋流程就完成了。
右旋操作具体应用
我们看一个右旋的例子，如图：
在我们插入结点1的时候就会出现不平衡现象，结点5的平衡因子变为2，这里我们将结点5进行右旋，变为右图就又变为一颗AVL树了。
右旋操作代码实现
1
