文章首发于：clawhub.club

树旋转（英语：Tree rotation）是在二叉树中的一种子树调整操作, 每一次旋转并不影响对该二叉树进行中序遍历的结果. 树旋转通常应用于需要调整树的局部平衡性的场合。

当对红黑树进行插入和删除等操作时，对树做了修改，红黑树的条件可能被破坏，需要通过调整使得查找树重新满足红黑树的条件，继续保持它的性质或平衡。
调整可以分为两类：

  • 颜色调整，即改变某个节点的颜色；
  • 结构调整，集改变检索树的结构关系。结构调整过程包含两个基本操作：左旋（Rotate Left），右旋（RotateRight）。

left-rotate（左旋）

例子一：左旋的过程是将x的右子树绕x逆时针旋转，使得x的右子树成为x的父亲，同时修改相关节点的引用。
左旋.png

例子二：逆时针旋转红黑树的两个节点，使得父节点被自己的右孩子取代，而自己成为自己的左孩子。
左旋1.png

图中，身为右孩子的Y取代了X的位置，而X变成了自己的左孩子。

right-rotate（右旋）

例子一：右旋的过程是将x的左子树绕x顺时针旋转，使得x的左子树成为x的父亲，同时修改相关节点的引用。旋转之后，二叉查找树的属性仍然满足。
右旋.png

例子二：顺时针旋转红黑树的两个节点，使得父节点被自己的左孩子取代，而自己成为自己的右孩子。
右旋1.png

图中，身为左孩子的Y取代了X的位置，而X变成了自己的右孩子。

参考资料：

http://lvshen9.coding.me/2017/11/07/%E7%BA%A2%E9%BB%91%E6%A0%91%E7%9A%84%E5%8F%98%E8%89%B2%E4%B8%8E%E6%97%8B%E8%BD%AC/
https://zh.wikipedia.org/wiki/%E6%A0%91%E6%97%8B%E8%BD%AC
https://www.cnblogs.com/CarpenterLee/p/5503882.html