AVL树本质是单键二叉搜索树，不支持节点分裂与合并；其平衡仅通过旋转（LL/LR/RR/RL）和严格的高度更新维护，每个节点仅存一个键值对，平衡因子限于[-1,0,1]。
AVL 树没有节点分裂与合并逻辑——这是 B-tree 或 B+tree 的操作，不是 AVL 的设计范畴。 混淆这两个概念会导致实现完全偏离 AVL 的本质：它靠旋转（left_rotate、right_rotate）和高度更新来维持平衡，所有插入/删除都在单个节点上完成，不拆分键集、不合并子树。
为什么 AVL 不需要 split / merge？
AVL 是二叉搜索树（BST）的自平衡变种，每个节点只存一个键值对，左右子树高度差（balance factor）严格限制在 [-1, 0, 1]。它的平衡动作粒度是「单节点」：insert 后自底向上检查高度差，遇到 -2 或 2 就用最多两次旋转修复；delete 同理。而 split 和 merge 是为应对“节点内多键”场景设计的（如 B-tree 节点满/空时的再分配），AVL 根本不存在“节点容量”这个概念。
常见误判现象：
– 写出 split_node() 函数但从未被调用
– 在 insert 中试图把一个新键“塞进”已有节点导致逻辑混乱
– 把 AVL 和红黑树或 B-tree 的平衡策略混在一起调试数小时无果
真正该关注的：旋转触发条件与平衡因子更新顺序
错误常发生在高度更新和旋转判断的时序上——必须先递归更新子树高度，再计算当前 balance factor，再决定是否旋转。顺序颠倒会导致 balance factor 计算错误，进而漏转或误转。
-
height(node)必须定义为node ? 1 + max(height(node->left), height(node->right)) : 0，不能省略空节点返回 0 - 每次递归回溯时，必须立刻重算
node->height，否则后续父节点的 balance factor 会错 - 旋转前要先更新被旋转子树的高度（例如
right_rotate中，先更新new_root->right高度，再更新原root高度） - 四种旋转场景对应明确 balance factor 组合：
–LL:bf(root) == 2 && bf(root->left) >= 0
–RR:bf(root) == -2 && bf(root->right)
–LR:bf(root) == 2 && bf(root->left)
–RL:bf(root) == -2 && bf(root->right) > 0
一个典型 insert 后平衡维护片段（C++）
Node* insert(Node* node, int key) {
if (!node) return new Node(key);
if (key key)
node->left = insert(node->left, key);
else if (key > node->key)
node->right = insert(node->right, key);
else
return node; // duplicate ignored
<pre class="brush:php;toolbar:false;">// ✅ 关键：先更新高度，再算平衡因子
node->height = 1 + max(height(node->left), height(node->right));
int bf = get_balance_factor(node);
// ✅ 四种 case 判断（注意符号和 >= / 1 && key left->key)
return right_rotate(node);
if (bf node->right->key)
return left_rotate(node);
if (bf > 1 && key > node->left->key) {
node->left = left_rotate(node->left);
return right_rotate(node);
}
if (bf right->key) {
node->right = right_rotate(node->right);
return left_rotate(node);
}
return node;
}
最容易被忽略的一点：AVL 的旋转不是独立操作，它和高度更新构成原子性修复单元。写代码时如果把高度更新抽成单独函数又忘了在每处旋转后显式调用，或者用缓存 height 导致脏值，就会出现“看起来转了但树仍不平衡”的静默故障——这种 bug 往往要打印整棵树的 height 和 bf 才能定位。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
