平衡树旋转为什么不会破坏二叉搜索树的有序性？

简化版

旋转只改变局部父子关系，不改变中序遍历顺序。只要旋转前满足 A < x < B < y < C 这类大小关系，旋转后这些子树仍然落在同样的有序区间里，所以 BST 性质不会被破坏。

以左旋为例，原结构是 x 的右孩子为 y，y 的左子树为 B：

    x              y
   / \            / \
  A   y    =>    x   C
     / \        / \
    B   C      A   B

旋转前 BST 关系是 A < x < B < y < C。左旋后，B 变成 x 的右子树，仍满足 x < B < y；x 变成 y 的左孩子，仍满足 x < y。因此中序结果仍是 A, x, B, y, C，没有改变。

右旋完全对称。平衡树通过旋转调整高度或颜色关系，但不会打乱有序性，这是 AVL、红黑树、Treap 等结构能在局部修复后继续作为搜索树的基础。

AVL、红黑树、Treap、Splay Tree 看起来规则各不相同，但它们都绕不开旋转。旋转的任务不是重新排序所有节点，而是在局部把树形「拧一下」，让高度、颜色、优先级或访问位置重新满足约束。这个动作必须非常克制：它只能修形状，不能破坏 BST 的搜索顺序。

如果旋转会改变中序顺序，平衡树就无法边插入边修复。每次修复都要重新建树，复杂度会失控。正因为旋转保持中序顺序，平衡树才能把修复限定在 O(log n) 路径上的少数局部操作。

记忆钩子：旋转不是洗牌，而是把局部支架换个支点；中序队伍的排队顺序不能变。

左旋最常见于右侧过重的情况。设 x 是当前子树根，y 是 x 的右孩子，B 是 y 的左子树。旋转前，由 BST 性质可得：

所有 A < x
x < 所有 B < y
y < 所有 C

旋转后，y 成为新根，x 成为 y 的左孩子，B 接到 x 的右边。因为 B 中所有值本来就大于 x 且小于 y，把它挂到 x.right 正好合法。A 仍然在 x.left，C 仍然在 y.right，区间没有错位。

旋转前的中序顺序是：

inorder(A), x, inorder(B), y, inorder(C)

旋转后的中序顺序仍然是：

inorder(A), x, inorder(B), y, inorder(C)

这就是最直接的证明。比如取数字：A=[1,2]，x=3，B=[4,5]，y=6，C=[7,8]。旋转前后中序都为 [1,2,3,4,5,6,7,8]。树高可能变了，父子关系变了，但搜索顺序没有变。

左旋不是只交换两个节点值，而是重连三个关键指针：x.right、y.left 和父节点指向。若实现带 parent 指针，还要同步更新 parent，否则树结构会断。

TreeNode rotateLeft(TreeNode x) {
    TreeNode y = x.right;
    TreeNode b = y.left;
    y.left = x;
    x.right = b;
    return y;
}

真实红黑树或 AVL 还要更新高度、颜色、父指针或根引用。面试伪代码可以只写核心指针，但要口头说明元数据需要跟着维护。

旋转改变的是结构，不是节点值。交换值虽然可能在某些小例子里维持有序，但会破坏节点携带的业务对象、引用身份、颜色或高度信息。平衡树节点通常不只是一个整数，里面可能有 key、value、color、size、parent 等字段。

操作	改变结构	改变 key 所在节点	是否适合平衡修复
旋转	是	否	适合
交换值	否	是	通常不适合
重建子树	是	可能	成本更高

平衡修复需要保持节点对象身份稳定，只调整局部连接关系，所以旋转是核心手段。

一次旋转只涉及常数个节点和指针，时间 O(1)。但插入或删除后可能沿路径向上触发多次检查，整体复杂度取决于树高。AVL 插入最多少量旋转即可恢复，删除可能向上继续传播；红黑树插入删除也会把旋转和变色组合使用。

边界上，左旋要求 x.right != null，右旋要求 x.left != null。如果子节点不存在，旋转没有支点。工程实现里还要处理旋转节点是根的情况，此时新根要回写到整棵树的 root。

旋转的本质是「保持中序不变，调整局部高度」。左旋里 B 最关键：它从 y.left 挪到 x.right，因为它本来就满足 x < B < y。只要你能用 A < x < B < y < C 解释清楚，就能把 AVL、红黑树等平衡修复的共同底层动作讲明白。