C++如何实现二分搜索树的AVL自平衡算法-C++-PHP中文网

avl树平衡因子必须为左子树高度减右子树高度，节点需存储height字段并沿路径向上更新，范围仅限−1、0、1；失衡时按ll、lr、rr、rl四种形态对应右旋、先右后左、左旋、先左后右旋转，插入删除后须自底向上逐层updateheight并rebalance。

c++如何实现二分搜索树的avl自平衡算法

AVL树的平衡因子怎么算才不会错

平衡因子必须是左子树高度减右子树高度，不是反过来。很多初学者在 getBalanceFactor 里写成 rightHeight - leftHeight，结果旋转逻辑全反了，树越插越歪。

实际计算时别手写递归求高——每次插入都重新遍历整棵子树太慢。应该在节点结构里存 height 字段，插入/删除后沿路径向上更新，时间复杂度从 O(n) 降到 O(log n)。

height 初始设为 1（单节点高度为 1），空节点高度为 0
更新公式固定为：node->height = 1 + max(getHeight(node->left), getHeight(node->right))
平衡因子范围只能是 -1、0、1；超出就得旋转

四种旋转什么时候用哪种

不是看平衡因子正负决定左旋还是右旋，而是看「失衡节点」和「较高子节点」的「较高孙子节点」三者相对位置。核心判断依据是：LL、LR、RR、RL 四种形态。

LL 型（左左）：当前节点平衡因子 > 1，且左孩子平衡因子 ≥ 0 → 右旋
RR 型（右右）：当前节点平衡因子 LR 型（左右）：当前节点平衡因子 > 1，且左孩子平衡因子 RL 型（右左）：当前节点平衡因子 0 → 先对右孩子右旋，再对当前节点左旋

注意：LR/RL 中第一次旋转后，原孩子的 height 必须先更新，再更新当前节点
旋转后所有涉及节点的 height 都要重算，漏掉一个就可能导致后续判断失效
旋转函数返回新根节点，调用处必须用返回值覆盖原指针，比如：root = rotateRight(root)

插入后如何正确回溯更新和旋转

AVL 插入不是插完就完了，关键在递归返回时检查并修复路径上每个祖先节点。很多人只在插入点做一次平衡，忽略了上面可能还存在失衡。

标准做法是让插入函数返回更新后的子树根，并在每一层返回前调用 updateHeight 和 rebalance：

C++14

C++14 对 C++11 的修正与增强版本，适合旧系统维护和较老工具链兼容。

下载

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; // 重复键不插入
<pre class="brush:php;toolbar:false;">updateHeight(node); // 必须先更新高度
return rebalance(node); // 再平衡，可能返回新根

}