本篇文章为红黑树的预备知识，暂且不涉及节点颜色。
左旋的过程是将x的右子树绕x逆时针旋转，使得x的右子树成为x的父节点，同时修改相关节点的引用。旋转之后，二叉查找树的属性仍然满足。
示例：
旋转前
|
/------3(null)-------\
| |
1(null) /------10(null)\
| |
6(null) 15(null)
旋转后
|
/-------------10(null)\
| |
/------3(null)\ 15(null)
| |
1(null) 6(null)
相关代码：
/**
* 左旋
* p为旋转的中心点
*/
public void rotateLeft(Node<T,E> p) {
if (p != null) {
Node<T,E> r = p.right;
p.right = r.left;
if (r.left != null)
r.left.parent = p;
r.parent = p.parent;
if (p.parent == null)
root = r;
else if (p.parent.left == p)
p.parent.left = r;
else
p.parent.right = r;
r.left = p;
p.parent = r;
}
}
右旋的过程是将x的左子树绕x顺时针旋转，使得x的左子树成为x的父节点，同时修改相关节点的引用。旋转之后，二叉查找树的属性仍然满足。
示例
旋转前
|
/-------------10(null)\
| |
/------3(null)\ 15(null)
| |
1(null) 6(null)
旋转后
|
/------3(null)-------\
| |
1(null) /------10(null)\
| |
6(null) 15(null)
相关代码：
/**
* 右旋
* 以p点为中心点旋转
*/
public void rotateRight(Node<T,E> p) {
if (p != null) {
Node<T,E> l = p.left;
p.left = l.right;
if (l.right != null) l.right.parent = p;
l.parent = p.parent;
if (p.parent == null)
root = l;
else if (p.parent.right == p)
p.parent.right = l;
else p.parent.left = l;
l.right = p;
p.parent = l;
}
}