树旋转¶
树旋转是对 二叉搜索树 的一种重构操作，不改变树的性质（ 各结点值的大小关系不变，即 中序不变 ），但会改变树的形状
在 a 图中，由树的性质容易得到 \(v<f<fr<g\)
如果要将树重构成一颗以 \(f\) 为根的树，由上面的不等式容易知道，比 \(f\) 小的 \(v\) 应该在 \(f\) 的左子树，比 \(f\) 大的 \(fr\) 和 \(g\) 应该在 \(f\) 的右子树，又 \(fr<g\) ，所以 \(fr\) 应该作为 \(g\) 的左孩子
重构后的树如图 b 所示，这一重构操作即为 树右旋
我们约定 \(g\) 为旋转的 根，则上面的操作就是 对根 \(g\) 右旋
类似可以得到 树左旋（如图 c、d 所示）
下面是 Wikipedia 对树旋转的动图演示：
