C++ AVL 树详解（二）：四种旋转、完整代码与平衡验证
·
C++ AVL 树详解（二）：四种旋转、完整代码与平衡验证
文章目录
- C++ AVL 树详解（二）：四种旋转、完整代码与平衡验证
前言
上一篇已经讲清了 AVL 树插入的基本过程：
按照 BST 规则插入
↓
沿祖先路径更新平衡因子
↓
平衡因子为 0：停止
平衡因子为 ±1：继续
平衡因子为 ±2：旋转
真正实现 AVL 树时，难点主要集中在旋转。
旋转不是简单交换两个结点，而是要同时维护：
二叉搜索树的大小关系
左孩子指针
右孩子指针
父指针
整棵树的根指针
局部子树与上一层的连接
结点的平衡因子
本文将依次讲解：
右单旋
左单旋
左右双旋
右左双旋
最后给出一套可以直接在 Linux 环境中编译运行的完整 C++ 实现。
一、旋转必须满足什么原则？
AVL 树的旋转有两个基本目标。
1.1 保持二叉搜索树性质
旋转前后，中序遍历结果必须完全相同。
假设旋转前满足：
a 中所有 key < 5
5 < b 中所有 key < 10
10 < c 中所有 key
旋转后仍然必须满足同样的大小顺序。
旋转只改变结点之间的连接方式，不改变关键字的有序关系。
1.2 恢复高度平衡
失衡结点满足：
|bf| == 2
旋转后应重新满足：
|bf| <= 1
对于插入场景，还希望局部子树的高度恢复到插入前，从而不再影响更高祖先。
1.3 旋转只修改局部结构
一次旋转不会重新构造整棵树。
它只会修改局部的少量结点和指针。
因此单旋和双旋本身都属于：
O(1)
时间操作。
二、右单旋：解决左左型失衡
2.1 什么是左左型？
假设失衡结点为 parent：
parent._bf == -2
说明 parent 左边比右边高 2。
再看 parent 的左孩子 subL：
subL._bf == -1
说明 subL 也是左边更高。
新结点位于：
parent 的左子树
再往左子树
所以称为：
左左型
LL
结构可以抽象为：
parent
/ \
subL c
/ \
a b
其中：
a 中所有 key < subL
subL < b 中所有 key < parent
parent < c 中所有 key
由于左边过高，需要执行右单旋。
2.2 右单旋后的结构
旋转后：
subL
/ \
a parent
/ \
b c
关键变化是：
subL 成为局部新根
parent 成为 subL 的右孩子
b 从 subL 的右子树变成 parent 的左子树
为什么 b 可以放在 parent 左边？
因为旋转前：
subL < b 中所有 key < parent
所以 b 正好适合作为 parent 的左子树。
2.3 右单旋需要修改哪些指针？
设：
Node* subL = parent->_left;
Node* subLR = subL->_right;
需要执行：
1. parent 的左孩子改成 subLR
2. subLR 的父亲改成 parent
3. subL 的右孩子改成 parent
4. parent 的父亲改成 subL
5. subL 与 parent 原来的父结点重新连接
6. 必要时更新 _root
7. 更新平衡因子
2.4 右单旋代码
void RotateR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
Node* parentParent = parent->_parent;
// b 子树交给 parent
parent->_left = subLR;
if (subLR != nullptr)
{
subLR->_parent = parent;
}
// parent 变成 subL 的右孩子
subL->_right = parent;
parent->_parent = subL;
// 连接原来的上一层
if (parentParent == nullptr)
{
_root = subL;
subL->_parent = nullptr;
}
else
{
if (parentParent->_left == parent)
{
parentParent->_left = subL;
}
else
{
parentParent->_right = subL;
}
subL->_parent = parentParent;
}
parent->_bf = 0;
subL->_bf = 0;
}
三、左单旋：解决右右型失衡
3.1 什么是右右型？
失衡结点：
parent._bf == 2
parent 的右孩子：
subR._bf == 1
新结点位于：
parent 的右子树
再往右子树
因此称为：
右右型
RR
结构：
parent
/ \
a subR
/ \
b c
由于右边过高，需要向左旋转。
3.2 左单旋后的结构
subR
/ \
parent c
/ \
a b
关键变化：
subR 成为局部新根
parent 成为 subR 的左孩子
b 从 subR 的左子树变成 parent 的右子树
由于：
parent < b 中所有 key < subR
所以 b 适合作为 parent 的右子树。
3.3 左单旋代码
void RotateL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
Node* parentParent = parent->_parent;
// b 子树交给 parent
parent->_right = subRL;
if (subRL != nullptr)
{
subRL->_parent = parent;
}
// parent 变成 subR 的左孩子
subR->_left = parent;
parent->_parent = subR;
// 连接原来的上一层
if (parentParent == nullptr)
{
_root = subR;
subR->_parent = nullptr;
}
else
{
if (parentParent->_left == parent)
{
parentParent->_left = subR;
}
else
{
parentParent->_right = subR;
}
subR->_parent = parentParent;
}
parent->_bf = 0;
subR->_bf = 0;
}
四、为什么有时单旋不能解决问题？
考虑下面的结构：
10
/
5
\
8
站在 10 上：
左边过高
但站在 5 上：
右边过高
它不是纯粹的左左型，而是：
先向左，再向右
即：
左右型
LR
如果直接对 10 执行右单旋，会得到：
5
\
10
/
8
这棵树仍然不平衡。
问题在于：
parent 和较高孩子的倾斜方向不一致。
这时需要先把折线结构转换成直线结构，再执行单旋。
五、左右双旋：解决左右型失衡
5.1 左右型条件
parent._bf == -2
subL._bf == 1
结构：
parent
/
subL
\
subLR
插入路径为：
左 → 右
所以称为左右型。
5.2 两次旋转
第一步，对 subL 执行左单旋：
parent
/
subLR
/
subL
第二步，对 parent 执行右单旋：
subLR
/ \
subL parent
因此：
左右双旋
=
先左单旋
+
再右单旋
代码框架：
RotateL(parent->_left);
RotateR(parent);
5.3 为什么双旋的平衡因子不能全部直接设为 0？
最简单的三个结点场景：
10
/
5
\
8
旋转后：
8
/ \
5 10
此时三个结点的平衡因子确实都是 0。
但是在更一般的情况下，subLR 下面还可能有子树。
旋转前 subLR 的平衡因子可能为：
-1
0
1
不同情况表示新增高度来自不同方向，旋转后 subL 和 parent 的平衡因子也不同。
5.4 左右双旋平衡因子更新
旋转前 subLR->_bf | 旋转后 subL->_bf | 旋转后 parent->_bf | subLR->_bf |
|---|---|---|---|
0 | 0 | 0 | 0 |
-1 | 0 | 1 | 0 |
1 | -1 | 0 | 0 |
5.5 左右双旋代码
void RotateLR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
int bf = subLR->_bf;
RotateL(subL);
RotateR(parent);
if (bf == 0)
{
subL->_bf = 0;
parent->_bf = 0;
}
else if (bf == -1)
{
subL->_bf = 0;
parent->_bf = 1;
}
else if (bf == 1)
{
subL->_bf = -1;
parent->_bf = 0;
}
else
{
assert(false);
}
subLR->_bf = 0;
}
六、右左双旋：解决右左型失衡
6.1 右左型条件
parent._bf == 2
subR._bf == -1
结构：
parent
\
subR
/
subRL
插入路径：
右 → 左
所以称为右左型。
6.2 两次旋转
第一步，对 subR 执行右单旋：
parent
\
subRL
\
subR
第二步，对 parent 执行左单旋：
subRL
/ \
parent subR
因此：
右左双旋
=
先右单旋
+
再左单旋
代码框架：
RotateR(parent->_right);
RotateL(parent);
6.3 右左双旋平衡因子更新
旋转前 subRL->_bf | 旋转后 parent->_bf | 旋转后 subR->_bf | subRL->_bf |
|---|---|---|---|
0 | 0 | 0 | 0 |
1 | -1 | 0 | 0 |
-1 | 0 | 1 | 0 |
6.4 右左双旋代码
void RotateRL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
int bf = subRL->_bf;
RotateR(subR);
RotateL(parent);
if (bf == 0)
{
parent->_bf = 0;
subR->_bf = 0;
}
else if (bf == 1)
{
parent->_bf = -1;
subR->_bf = 0;
}
else if (bf == -1)
{
parent->_bf = 0;
subR->_bf = 1;
}
else
{
assert(false);
}
subRL->_bf = 0;
}
七、四种旋转如何快速判断？
本文采用：
bf = 右高 - 左高
可以整理成下面的判断表。
| 失衡结点 | 较高孩子 | 类型 | 操作 |
|---|---|---|---|
parent->_bf == -2 | cur->_bf == -1 | LL | 右单旋 |
parent->_bf == 2 | cur->_bf == 1 | RR | 左单旋 |
parent->_bf == -2 | cur->_bf == 1 | LR | 先左后右 |
parent->_bf == 2 | cur->_bf == -1 | RL | 先右后左 |
八、旋转代码中最容易漏掉什么？
8.1 中间子树不能丢失
右单旋中的：
Node* subLR = subL->_right;
必须连接为：
parent->_left = subLR;
否则 subLR 整棵子树会丢失。
8.2 非空中间子树要修改父指针
if (subLR != nullptr)
{
subLR->_parent = parent;
}
只修改孩子指针而不修改父指针，会让树的双向关系不一致。
8.3 局部根可能就是整棵树的根
如果：
parent->_parent == nullptr
说明 parent 是整棵树根。
旋转后必须修改：
_root
8.4 局部根也可能只是某棵子树
旋转前 parent 可能是上一层结点的左孩子，也可能是右孩子。
所以要判断：
parentParent->_left == parent
还是：
parentParent->_right == parent
再把新根连接回去。
九、完整 AVL 树代码
下面给出一套完整实现，包含：
插入
四种旋转
查找
中序遍历
高度统计
结点数量统计
平衡检测
析构释放
为了防止默认浅拷贝导致多个对象共享结点，示例中暂时禁用了拷贝构造和拷贝赋值。
#include <algorithm>
#include <cassert>
#include <cstdlib>
#include <iostream>
#include <utility>
template<class K, class V>
struct AVLTreeNode
{
std::pair<K, V> _kv;
AVLTreeNode* _left;
AVLTreeNode* _right;
AVLTreeNode* _parent;
int _bf;
explicit AVLTreeNode(
const std::pair<K, V>& kv)
: _kv(kv)
, _left(nullptr)
, _right(nullptr)
, _parent(nullptr)
, _bf(0)
{
}
};
template<class K, class V>
class AVLTree
{
using Node = AVLTreeNode<K, V>;
public:
AVLTree() = default;
AVLTree(const AVLTree&) = delete;
AVLTree& operator=(const AVLTree&) = delete;
~AVLTree()
{
Destroy(_root);
}
bool Insert(const std::pair<K, V>& kv)
{
if (_root == nullptr)
{
_root = new Node(kv);
return true;
}
Node* parent = nullptr;
Node* cur = _root;
// 按 BST 规则查找插入位置
while (cur != nullptr)
{
parent = cur;
if (kv.first < cur->_kv.first)
{
cur = cur->_left;
}
else if (cur->_kv.first < kv.first)
{
cur = cur->_right;
}
else
{
return false;
}
}
// 创建并连接新结点
cur = new Node(kv);
cur->_parent = parent;
if (kv.first < parent->_kv.first)
{
parent->_left = cur;
}
else
{
parent->_right = cur;
}
// 更新祖先平衡因子
while (parent != nullptr)
{
if (cur == parent->_left)
{
--parent->_bf;
}
else
{
++parent->_bf;
}
if (parent->_bf == 0)
{
// 当前子树高度没有增加
break;
}
if (parent->_bf == -1 ||
parent->_bf == 1)
{
// 当前子树高度增加，继续向上
cur = parent;
parent = parent->_parent;
continue;
}
if (parent->_bf == -2)
{
if (cur->_bf == -1)
{
RotateR(parent);
}
else if (cur->_bf == 1)
{
RotateLR(parent);
}
else
{
assert(false);
}
}
else if (parent->_bf == 2)
{
if (cur->_bf == 1)
{
RotateL(parent);
}
else if (cur->_bf == -1)
{
RotateRL(parent);
}
else
{
assert(false);
}
}
else
{
assert(false);
}
// 插入场景旋转后结束
break;
}
return true;
}
Node* Find(const K& key)
{
Node* cur = _root;
while (cur != nullptr)
{
if (key < cur->_kv.first)
{
cur = cur->_left;
}
else if (cur->_kv.first < key)
{
cur = cur->_right;
}
else
{
return cur;
}
}
return nullptr;
}
const Node* Find(const K& key) const
{
const Node* cur = _root;
while (cur != nullptr)
{
if (key < cur->_kv.first)
{
cur = cur->_left;
}
else if (cur->_kv.first < key)
{
cur = cur->_right;
}
else
{
return cur;
}
}
return nullptr;
}
void InOrder() const
{
InOrder(_root);
std::cout << '\n';
}
int Height() const
{
return Height(_root);
}
std::size_t Size() const
{
return Size(_root);
}
bool IsBalanceTree() const
{
return Check(_root).first;
}
private:
void RotateR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
Node* parentParent = parent->_parent;
parent->_left = subLR;
if (subLR != nullptr)
{
subLR->_parent = parent;
}
subL->_right = parent;
parent->_parent = subL;
ConnectParent(
parentParent,
parent,
subL
);
parent->_bf = 0;
subL->_bf = 0;
}
void RotateL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
Node* parentParent = parent->_parent;
parent->_right = subRL;
if (subRL != nullptr)
{
subRL->_parent = parent;
}
subR->_left = parent;
parent->_parent = subR;
ConnectParent(
parentParent,
parent,
subR
);
parent->_bf = 0;
subR->_bf = 0;
}
void RotateLR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
const int bf = subLR->_bf;
RotateL(subL);
RotateR(parent);
if (bf == 0)
{
parent->_bf = 0;
subL->_bf = 0;
}
else if (bf == -1)
{
parent->_bf = 1;
subL->_bf = 0;
}
else if (bf == 1)
{
parent->_bf = 0;
subL->_bf = -1;
}
else
{
assert(false);
}
subLR->_bf = 0;
}
void RotateRL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
const int bf = subRL->_bf;
RotateR(subR);
RotateL(parent);
if (bf == 0)
{
parent->_bf = 0;
subR->_bf = 0;
}
else if (bf == 1)
{
parent->_bf = -1;
subR->_bf = 0;
}
else if (bf == -1)
{
parent->_bf = 0;
subR->_bf = 1;
}
else
{
assert(false);
}
subRL->_bf = 0;
}
void ConnectParent(
Node* parentParent,
Node* oldRoot,
Node* newRoot)
{
if (parentParent == nullptr)
{
_root = newRoot;
newRoot->_parent = nullptr;
return;
}
if (parentParent->_left == oldRoot)
{
parentParent->_left = newRoot;
}
else
{
parentParent->_right = newRoot;
}
newRoot->_parent = parentParent;
}
static void Destroy(Node* root)
{
if (root == nullptr)
{
return;
}
Destroy(root->_left);
Destroy(root->_right);
delete root;
}
static void InOrder(const Node* root)
{
if (root == nullptr)
{
return;
}
InOrder(root->_left);
std::cout
<< root->_kv.first
<< ':'
<< root->_kv.second
<< "(bf="
<< root->_bf
<< ") ";
InOrder(root->_right);
}
static int Height(const Node* root)
{
if (root == nullptr)
{
return 0;
}
return std::max(
Height(root->_left),
Height(root->_right)
) + 1;
}
static std::size_t Size(const Node* root)
{
if (root == nullptr)
{
return 0;
}
return Size(root->_left)
+ Size(root->_right)
+ 1;
}
// 返回值：
// first 表示当前子树是否为合法 AVL 树
// second 表示当前子树高度
static std::pair<bool, int>
Check(const Node* root)
{
if (root == nullptr)
{
return {true, 0};
}
const auto [leftOk, leftHeight] =
Check(root->_left);
const auto [rightOk, rightHeight] =
Check(root->_right);
const int diff =
rightHeight - leftHeight;
const bool currentOk =
std::abs(diff) <= 1
&& root->_bf == diff;
return {
leftOk && rightOk && currentOk,
std::max(
leftHeight,
rightHeight
) + 1
};
}
private:
Node* _root = nullptr;
};
十、测试四种旋转
10.1 测试右单旋
插入：
10 5 3
void TestRotateR()
{
AVLTree<int, int> tree;
tree.Insert({10, 10});
tree.Insert({5, 5});
tree.Insert({3, 3});
tree.InOrder();
std::cout
<< std::boolalpha
<< tree.IsBalanceTree()
<< '\n';
}
10.2 测试左单旋
插入：
10 15 20
10.3 测试左右双旋
插入：
10 5 8
10.4 测试右左双旋
插入：
10 15 12
完整测试：
#include <iostream>
int main()
{
{
AVLTree<int, int> tree;
int values[] = {10, 5, 3};
for (int value : values)
{
tree.Insert({value, value});
}
std::cout << "右单旋：";
tree.InOrder();
std::cout << tree.IsBalanceTree()
<< "\n\n";
}
{
AVLTree<int, int> tree;
int values[] = {10, 15, 20};
for (int value : values)
{
tree.Insert({value, value});
}
std::cout << "左单旋：";
tree.InOrder();
std::cout << tree.IsBalanceTree()
<< "\n\n";
}
{
AVLTree<int, int> tree;
int values[] = {10, 5, 8};
for (int value : values)
{
tree.Insert({value, value});
}
std::cout << "左右双旋：";
tree.InOrder();
std::cout << tree.IsBalanceTree()
<< "\n\n";
}
{
AVLTree<int, int> tree;
int values[] = {10, 15, 12};
for (int value : values)
{
tree.Insert({value, value});
}
std::cout << "右左双旋：";
tree.InOrder();
std::cout << tree.IsBalanceTree()
<< '\n';
}
return 0;
}
十一、为什么要同时检查平衡因子和真实高度？
只检查：
每个结点的 _bf 是否属于 -1、0、1
是不够的。
假设代码错误地把所有 _bf 都设成 0，那么数值看起来合法，但实际树可能已经严重失衡。
因此验证时要同时检查：
1. 真实左右高度差绝对值是否不超过 1
2. 记录的 _bf 是否等于真实高度差
即：
int diff = rightHeight - leftHeight;
bool currentOk =
std::abs(diff) <= 1
&& root->_bf == diff;
这样才能发现两类错误：
树的真实结构不平衡
记录的平衡因子与真实结构不一致
十二、为什么课程中的直观检测可能是 O(N²)？
一种直接写法是：
bool IsBalance(Node* root)
{
int leftHeight = Height(root->_left);
int rightHeight = Height(root->_right);
return ...
&& IsBalance(root->_left)
&& IsBalance(root->_right);
}
问题在于：
检查每个结点时
都会重新计算左右子树高度
在退化结构中，同一批结点会被重复访问很多次，最坏复杂度可能达到：
O(N²)
本文完整代码中的 Check 使用后序遍历一次性返回：
当前子树是否合法
当前子树高度
每个结点只处理一次，因此验证复杂度为：
O(N)
这是一种很常见的递归优化思想：
不要让父结点反复重新计算子树已经得到的信息。
十三、随机数据测试
除了四种固定旋转场景，还应该插入大量随机数据验证。
#include <cstdlib>
#include <ctime>
#include <iostream>
#include <vector>
void TestRandom()
{
const int count = 100000;
AVLTree<int, int> tree;
std::srand(
static_cast<unsigned>(
std::time(nullptr)
)
);
for (int i = 0; i < count; ++i)
{
int value = std::rand() + i;
tree.Insert({
value,
value
});
}
std::cout
<< std::boolalpha
<< "是否平衡："
<< tree.IsBalanceTree()
<< '\n';
std::cout
<< "高度："
<< tree.Height()
<< '\n';
std::cout
<< "结点数量："
<< tree.Size()
<< '\n';
}
因为示例不允许重复 key，所以实际结点数量可能小于尝试插入次数。
十四、Linux 下编译运行
把代码保存为：
avl_tree.cpp
普通编译：
g++ -std=c++17 \
-Wall -Wextra -pedantic \
avl_tree.cpp -o avl_tree
./avl_tree
建议打开 AddressSanitizer 和 UndefinedBehaviorSanitizer：
g++ -std=c++17 \
-Wall -Wextra -pedantic \
-fsanitize=address,undefined \
-g avl_tree.cpp -o avl_tree
./avl_tree
它们可以帮助发现：
空指针访问
释放后继续使用
重复释放
部分未定义行为
不过，平衡因子计算错误属于逻辑错误，仍然要依靠：
IsBalanceTree()
和针对性的测试用例发现。
十五、AVL 树查找为什么是 O(log N)？
AVL 树仍然保持二叉搜索树规则。
查找代码与普通 BST 基本相同：
Node* Find(const K& key)
{
Node* cur = _root;
while (cur != nullptr)
{
if (key < cur->_kv.first)
{
cur = cur->_left;
}
else if (cur->_kv.first < key)
{
cur = cur->_right;
}
else
{
return cur;
}
}
return nullptr;
}
每次比较后只进入一棵子树。
访问结点数量与树高成正比：
O(h)
AVL 树保证：
h = O(log N)
因此查找复杂度为：
O(log N)
十六、扩展：AVL 删除为什么比插入更复杂？
这里只介绍整体思想。
16.1 先按照 BST 规则删除
普通二叉搜索树删除分成：
叶子结点
只有一个孩子
左右孩子都存在
两个孩子时，通常使用：
前驱
或
后继
替换后，再删除一个至多只有一个孩子的结点。
16.2 删除会让子树高度降低
插入只会让路径上的子树高度增加。
删除则可能让某一侧高度降低。
如果父结点原来平衡，删除后可能出现：
bf == 2
或
bf == -2
需要旋转。
16.3 删除旋转后可能继续向上
插入旋转后，局部子树高度通常恢复到插入前，所以可以停止。
删除旋转后，局部子树高度仍可能继续降低。
因此可能继续影响更高祖先：
删除结点
↓
更新父结点
↓
旋转
↓
继续向上更新
↓
再次旋转
所以 AVL 删除最坏可能在一条路径上执行多次旋转。
16.4 删除时孩子平衡因子可能为 0
在插入场景中，第一个失衡结点较高一侧的孩子通常为：
-1 或 1
删除场景中还可能出现：
孩子 bf == 0
这会带来额外的平衡因子更新分支。
因此不能把只适用于插入的旋转代码，未经分析直接用于删除。
十七、AVL 树适合什么场景？
AVL 树对高度控制比较严格。
它的特点是：
查找路径较短
查询性能稳定
插入和删除需要维护高度或平衡因子
结构调整逻辑较复杂
适合：
查询操作很多
需要有序数据
需要稳定的对数级查找
更新频率相对可控
例如：
内存索引
有序字典
符号表
范围查询结构的基础组件
工程中是否直接选择 AVL 树，还要综合考虑：
更新频率
缓存局部性
并发模型
内存开销
标准库已有容器
学习 AVL 树的主要价值，是理解：
如何通过维护局部不变量，把可能退化的搜索树稳定控制在对数高度。
十八、常见错误整理
18.1 旋转后忘记连接上一层
只完成局部三个结点的旋转，却没有让新根连接原来的父结点，会让整棵树断开。
18.2 旋转根结点后忘记更新 _root
当：
parent->_parent == nullptr
旋转后的新根必须赋给：
_root
18.3 只修改孩子指针，不修改父指针
必须保证：
父亲指向孩子
孩子也指回父亲
二者一致。
18.4 丢失中间子树
右单旋中的 subLR、左单旋中的 subRL 都不能丢失。
它们需要转移给原来的失衡根。
18.5 双旋时直接把三个平衡因子全设为 0
只有最简单的三结点场景可以这样做。
一般场景必须根据中间结点旋转前的平衡因子更新。
18.6 双旋顺序写反
LR：先左旋子结点，再右旋失衡根
RL：先右旋子结点，再左旋失衡根
18.7 使用默认拷贝
AVL 树结点由动态内存组织。
默认拷贝只会复制 _root 地址，导致：
两棵树共享结点
重复释放
悬空指针
需要实现深拷贝，或者像示例一样暂时禁止拷贝。
18.8 只检查中序有序
中序有序只能说明二叉搜索树关系可能正确。
它不能证明：
树是平衡的
_bf 记录正确
父指针正确
需要额外执行平衡检测。
18.9 把插入旋转规则直接照搬到删除
删除可能出现孩子平衡因子为 0，并且旋转后可能继续向上调整。
两者不能完全共用停止逻辑。
十九、把所有知识点串起来
19.1 AVL 首先是一棵 BST
所以插入、查找和中序遍历仍然遵循关键字大小关系。
19.2 平衡因子负责发现倾斜
bf = 右高 - 左高
合法值：
-1、0、1
失衡值：
-2、2
19.3 插入只影响祖先路径
从新结点向根更新平衡因子。
19.4 第一个失衡祖先决定旋转类型
LL：右单旋
RR：左单旋
LR：先左后右
RL：先右后左
19.5 旋转必须同时维护两类规则
搜索树规则
高度平衡规则
并同步更新：
孩子指针
父指针
根指针
平衡因子
19.6 旋转后还要验证
通过：
中序遍历
真实高度差
记录的平衡因子
父子关系
验证实现是否正确。
AtomGit 是由开放原子开源基金会联合 CSDN 等生态伙伴共同推出的新一代开源与人工智能协作平台。平台坚持“开放、中立、公益”的理念，把代码托管、模型共享、数据集托管、智能体开发体验和算力服务整合在一起，为开发者提供从开发、训练到部署的一站式体验。
更多推荐
19
0- 0
已为社区贡献27条内容
所有评论(0)