当前位置：首页 > news >正文

数据结构：利用旋转在AVL树中维持平衡（Inserting in AVL with Rotation）

news 2025/8/21 7:09:35

插入操作的起点 —— 问题在哪一步出现？

如何修复失衡？—— 旋转的本质

推导最简单的失衡情况 —— 左-左 (LL) 和右-右 (RR)

情况一：左-左 (Left-Left, LL) 失衡

情况二：右-右 (Right-Right, RR) 失衡

情况三：左-右 (Left-Right, LR) 失衡

情况四：右-左 (Right-Left, RL) 失衡

整合代码

上一部分我们已经从第一性原理搞清楚了为什么需要 AVL 树以及它的定义。现在，我们来解决最核心的问题：当向一棵 AVL 树插入一个新节点后，如何通过“旋转”来维持它的平衡。

数据结构：AVL 树-CSDN博客

插入操作的起点 —— 问题在哪一步出现？

向 AVL 树插入一个新节点，其过程的前半部分和普通 BST 完全一样。

从根节点开始，比较新节点的值和当前节点的值。
如果新节点的值小，就往左子树走；如果大，就往右子树走。
重复此过程，直到找到一个 NULL 的位置，这就是新节点的插入点。

代码框架的起点：

我们先写一个递归的插入函数框架，它暂时只实现了普通 BST 的插入逻辑。

// 创建一个新节点
AVLTreeNode* createNode(int data) {AVLTreeNode* newNode = new AVLTreeNode();newNode->data = data;newNode->left = NULL;newNode->right = NULL;newNode->height = 0; // 新插入的节点作为叶子，高度为 0return newNode;
}// AVL 树的插入函数（目前还只是 BST 的插入）
AVLTreeNode* insert(AVLTreeNode* node, int data) {// 1. 找到插入位置，和普通 BST 一样if (node == NULL) {return createNode(data);}if (data < node->data) {node->left = insert(node->left, data);} else if (data > node->data) {node->right = insert(node->right, data);} else {// 不允许插入重复值return node;}// ... 问题就出在接下来的步骤 ...return node;
}

问题的出现：

插入完成后，从新插入的节点到根节点的路径上，所有祖先节点的高度都可能发生变化。

在这个“高度+1”的传播路径上，可能会有某个节点的平衡因子（Balance Factor, 简称 BF）从 1 变成 2，或者从 -1 变成 -2。

一旦出现 2 或 -2，AVL 树的平衡条件就被打破了。这个节点，我们称之为第一个失衡的祖先节点。我们的任务，就是在这个节点上动手术，让它重新平衡。

插入操作导致失衡的根本原因，是插入路径上祖先节点高度的连锁更新。因此，在插入的递归调用返回之后，我们必须更新高度并检查平衡。

如何修复失衡？—— 旋转的本质

我们的核心目标：

设计一种操作，它必须满足两个条件：

能够修正失衡节点的平衡因子，使其回归到 {-1, 0, 1} 的范围内。
操作完成后，整棵树仍然必须是一棵二叉搜索树（BST），即所有节点满足“左小右大”的规则。

怎么修？我们唯一能做的操作就是改变节点间的父子关系。这个操作，就叫做旋转。

旋转的本质，是在保持 BST 中序遍历序列不变的前提下，通过改变局部父子关系，降低过高子树的高度，同时提升过矮子树的高度，最终达到平衡，同时维持 BST 的性质。

中序遍历序列不变，意味着树的“有序性”没有被破坏。它依然是一棵搜索二叉树。

失衡一共有四种情况，我们先从最简单的两种开始推导。

推导最简单的失衡情况 —— 左-左 (LL) 和右-右 (RR)

情况一：左-左 (Left-Left, LL) 失衡

定义：由于在失衡节点 A 的左子树 B 的左子树上插入了新节点，导致 A 的平衡因子变成了 +2。

图示：

A 的 BF = 2，意味着它的左子树比右子树高 2。

B (A的左孩子) 的 BF = 1 (或 0)，意味着新节点加在了 B 的左边，导致 B 也是“左倾”的。

      (A) BF=2             // A 失衡/   \(B)   (T3)/   \
(C)   (T2)                 // 新节点插入在 C 的子树中，或 C 就是新节点
/ \
...

（这里的 T2, T3 代表某个子树，可能是 NULL）

如何修复？

A 节点现在太“靠右”了，它的左边太重。为了让树变“矮”，我们需要把 B 提上来，让 A 降下去。

想象一下，你用手捏住 B，然后向右上方“提”，A 就会顺时针“掉下去”，成为 B 的右孩子。这个操作就是右旋。

目标：让 B 成为新的根节点。
约束 (BST性质)： B 的值小于 A 的值。所以当 B 成为新根后，A 必须成为 B 的右孩子。
产生的问题： B 原本的右孩子（子树 T2）怎么办？它不能凭空消失。
寻找解决方案：我们观察 T2 中所有节点的值，根据 BST 定义，它们都大于 B 但小于 A。这个范围正好可以把它安置在 A 的左孩子位置上！

操作流程（称为“右旋”）：

让 B 成为新的根。
A 成为 B 的右孩子。
最关键的一步：B 原本的右子树 (Br) 怎么办？

根据 BST 的性质，Br 上的所有节点都比 B 大，但比 A 小。正好，A 降下去之后，它的左孩子位置空出来了，Br 就可以顺理成章地成为 A 的新左孩子。

旋转后结构：

     (B)/   \(C)   (A)/ \   /   \
... (T2) (T3)

看，树变矮了，并且 C -> B -> T2 -> A -> T3 的中序遍历顺序没有改变。平衡恢复了！

图示变化：

      A (+2)                   B (0)/ \                      /   \B (+1)  AR   --右旋-->      BL     A (0)/ \                      /      / \BL  Br                            Br  AR

（BL, Br, AR 分别代表 B 的左右子树和 A 的右子树）

代码实现（右旋）：

节点结构与右旋函数

首先，我们需要一个节点结构。为了计算平衡因子，我们需要存储每个节点的高度。

// C/C++ 风格的节点定义
struct Node {int key;       // 键值Node* left;    // 左孩子指针Node* right;   // 右孩子指针int height;    // 节点的高度
};// 获取节点高度的辅助函数（处理空节点）
int height(Node* N) {if (N == NULL)return 0;return N->height;
}// max 辅助函数
int max(int a, int b) {return (a > b) ? a : b;
}

现在，我们来实现刚才推导的右旋函数。

这个函数输入一个失衡的根节点 A (在代码里我们叫 y)，返回旋转后新的根节点 B (在代码里我们叫 x)。

// 对以 y 为根的子树进行右旋
// 返回旋转后新的根节点
Node* rightRotate(Node* y) {// 步骤1：确定 x 和 T2Node* x = y->left;Node* T2 = x->right;// 步骤2：执行旋转 (改变指针)x->right = y;y->left = T2;// 步骤3：更新高度 (必须先更新 y, 再更新 x)// 因为 x 的新高度依赖于 y 的新高度y->height = max(height(y->left), height(y->right)) + 1;x->height = max(height(x->left), height(x->right)) + 1;// 步骤4：返回新的根节点return x;
}

情况二：右-右 (Right-Right, RR) 失衡

这和 LL 是完全对称的镜像情况。

定义：由于在失衡节点 A 的右子树 B 的右子树上插入了新节点，导致 A 的平衡因子变成了 -2。

图示：

   (A)     BF=-2/   \
(T1)  (B)/   \(T2)  (C)/       \...

A 现在太“靠左”了，右边太重。我们需要把 B “提”上来，让 A “掉下去”。

操作流程（称为“左旋”）：

让 B 成为新的根。
A 成为 B 的左孩子。
B 原来的左子树 T2 成为 A 的新右孩子。

图示变化：

    A (-2)                      B (0)/ \                         /  \AL  B (-1)   --左旋-->      A    BR/ \                     / \     \BL  BR                  AL  BL   ...

代码实现（左旋）：

左旋的代码是右旋的镜像。

// 对以 x 为根的子树进行左旋
// 返回旋转后新的根节点
Node* leftRotate(Node* x) {Node* y = x->right;Node* T2 = y->left;// 执行旋转y->left = x;x->right = T2;// 更新高度x->height = max(height(x->left), height(x->right)) + 1;y->height = max(height(y->left), height(y->right)) + 1;// 返回新的根节点return y;
}

情况三：左-右 (Left-Right, LR) 失衡

定义：由于在失衡节点 A 的左子树 B 的右子树上插入了新节点，导致 A 的平衡因子变成了 +2。

图示：

这次，A 是左倾 (BF=2)，但它的左孩子 B 却是右倾的 (BF=-1)。形成了一个 "之" 字形或“拐角”的结构。

      (A)   BF=2/   \(B)   (T3)/   \
(T1) (C)/ \...

如何修复？

如果我们直接对 A 进行右旋，会发生什么？

     (B)/   \(T1) (A)/   \(C)   (T3)

这棵树依然不平衡，只是把问题从 A 的左边转移到了右边。所以，单次旋转无法解决 "拐角" 问题。

观察 B 和 C 的关系，C 是 B 的右孩子，这不就是一个 RR 型的子结构吗？我们可以对 B 进行一次左旋。

"拐角" 问题的本质是结构不“直”。我们必须先通过一次旋转，把 "拐角" 拉直，转换成我们已经会解决的 LL 或 RR 问题。

操作流程：

1. 拉直： 观察 B-C 这个局部，它是一个 RR 结构的失衡雏形。我们对 B 节点执行一次左旋。

      A (+2)                     A (+2)/ \                        / \B   AR      --对B左旋-->   C   AR/ \                        / \BL  C                      B   .../ \                    /...                 BL

2. 转换： 经过上一步，整棵树从 A 节点看，已经变成了一个标准的 LL 失衡！

3. 解决： 既然是 LL 问题，我们再对 `A` 节点执行一次右旋，问题就解决了。

      A (+2)                        C/ \                          /   \C   AR       --对A右旋-->     B     A/ \                          /  \   / \B  ...                       BL ... ... AR/
BL

LR 型失衡，需要进行两次旋转：先对子节点(B)进行一次反向的旋转（左旋），把它变成 LL 型，再对当前节点(A)进行一次正向的旋转（右旋）。

情况四：右-左 (Right-Left, RL) 失衡

这和 LR 是完全对称的镜像情况。

A 的平衡因子变成了 -2（右边重），但新节点被插入到了 A 的右孩子 B 的左子树上。路径是 A -> B -> C (右-左)。

    A (-2)/ \AL  B (+1)/ \C  BR/ \... 新节点 ...

操作流程：

拉直：对 B 节点执行右旋，将其转换成 RR 问题。
解决：对 A 节点执行左旋。

整合代码

现在我们已经推导出了所有情况和对应的解决方案。让我们把这些逻辑整合到 insert 函数中。

AVL 树的插入函数是在标准 BST 插入的基础上，增加了“更新高度”和“检查并修正平衡”的步骤。这通常在递归调用之后执行。

// 获取节点高度（处理 NULL 的情况）
int getHeight(AVLTreeNode* node) {if (node == NULL) {return -1; // 约定空树的高度是 -1}return node->height;
}// 获取两个数中的较大值
int max(int a, int b) {return (a > b) ? a : b;
}

AVLTreeNode* insert(AVLTreeNode* node, int data) {// 1. 普通 BST 的插入逻辑 (同上)if (node == NULL) return createNode(data);if (data < node->data) node->left = insert(node->left, data);else if (data > node->data) node->right = insert(node->right, data);else return node;// 2. 更新当前节点的高度// 一个节点的高度 = 1 + max(左子树高度, 右子树高度)node->height = 1 + max(getHeight(node->left), getHeight(node->right));// 3. 计算当前节点的平衡因子int balance = getHeight(node->left) - getHeight(node->right);// 4. 检查是否失衡，并执行旋转 (下一步的核心)// ...return node;
}

公式总结：

平衡因子 Balance Factor (BF): BF(node) = height(node->left) - height(node->right)
LL 型: BF(A) = 2, BF(B) = 1. 解决：对 A 进行一次 rightRotate。
RR 型: BF(A) = -2, BF(B) = -1. 解决：对 A 进行一次 leftRotate。
LR 型: BF(A) = 2, BF(B) = -1. 解决：先对 B leftRotate，再对 A rightRotate。
RL 型: BF(A) = -2, BF(B) = 1. 解决：先对 B rightRotate，再对 A leftRotate。

AVLTreeNode* insert(AVLTreeNode* node, int data) {// 1. 普通 BST 插入if (node == NULL) return createNode(data);if (data < node->data) node->left = insert(node->left, data);else if (data > node->data) node->right = insert(node->right, data);else return node;// 2. 更新高度node->height = 1 + max(getHeight(node->left), getHeight(node->right));// 3. 获取平衡因子int balance = getHeight(node->left) - getHeight(node->right);// 4. 检查并处理四种失衡情况// LL Caseif (balance > 1 && data < node->left->data) {return rightRotate(node);}// RR Caseif (balance < -1 && data > node->right->data) {return leftRotate(node);}// LR Caseif (balance > 1 && data > node->left->data) {node->left = leftRotate(node->left); // 先对子节点左旋return rightRotate(node);            // 再对当前节点右旋}// RL Caseif (balance < -1 && data < node->right->data) {node->right = rightRotate(node->right); // 先对子节点右旋return leftRotate(node);               // 再对当前节点左旋}// 5. 如果没有失衡，直接返回当前节点return node;
}

data < node->left->data 这个判断是用来确定新节点插入在哪一侧，从而区分 LL 和 LR (或 RR 和 RL) 的。

至此，我们已经从第一性原理出发，完整地推导并实现了 AVL 树的插入和旋转操作。每一步操作都是为了达到“在维持 BST 有序性的前提下，恢复局部平衡”这一根本目的。

查看全文

http://www.xdnf.cn/news/1331083.html