平衡树与二叉树旋转 (BBST Rotations)

理解 AVL、Treap、Splay 等自平衡树核心的左旋与右旋操作，维持树的高效平衡状态

什么是平衡树旋转？

在二叉搜索树（BST）中，如果插入的数据接近有序，树的结构会退化成一个单向链表，导致检索复杂度从最优秀的 $O(\log N)$ 恶化为慢速的 $O(N)$。为了维护树的高度平衡，自平衡树（如 AVL 树）会在检测到失衡时，执行核心的旋转（Rotation）操作：

旋转三大原则（以左旋为例，设根为 A，右孩子为 B）

  1. B 的左子树转移：由于 B 的左子树 $T_2$ 中的所有节点数值在 $A$ 和 $B$ 之间，因此旋转后 $T_2$ 移交给 $A$ 的右子树（$A \rightarrow right = T_2$）。
  2. B 荣登父位：B 成为这个局部树的全新根节点（$B \rightarrow left = A$）。
  3. 二叉搜索树（BST）性质在旋转前后保持完全一致。
点击"执行左旋"或"执行右旋"观察节点在空间中的翻转流动、以及子树 $T_1$, $T_2$, $T_3$ 的无缝接力重组。

C++ 核心代码对照

自平衡二叉搜索树的单旋实现
struct Node {
    int val;
    Node* left;
    Node* right;
};

// 1. 左单旋 (Left Rotate)
Node* leftRotate(Node* A) {
    Node* B = A->right;
    Node* T2 = B->left;

    // 旋转重组
    B->left = A;
    A->right = T2;

    return B; // 返回新的局部根节点 B
}

// 2. 右单旋 (Right Rotate)
Node* rightRotate(Node* B) {
    Node* A = B->left;
    Node* T2 = A->right;

    // 旋转重组
    A->right = B;
    B->left = T2;

    return A; // 返回新的局部根节点 A
}