C++如何实现二叉搜索树的平衡因子计算与旋转逻辑-C++-PHP中文网

平衡因子应通过缓存高度在o(1)内计算：bf = get_height(node->left) - get_height(node->right)，其中get_height空节点返回0，非空返回node->height；旋转由当前节点与子节点bf组合触发（如ll型为bf=+2且左孩子bf=+1），仅需更新旋转涉及的三个节点高度；插入后须递归回溯更新高度并就地旋转。

c++如何实现二叉搜索树的平衡因子计算与旋转逻辑

平衡因子怎么算？别直接用 height(left) - height(right)

平衡因子（Balance Factor）定义是左子树高度减右子树高度，但很多人写成 height(node->left) - height(node->right) 后发现性能爆炸——因为每次调用 height() 都要递归遍历整棵子树。BST 插入/删除频繁时，这会让单次操作从 O(log n) 退化到 O(n)。

真正可行的做法是在节点结构里缓存高度：int height，并在每次插入、删除后自底向上更新。更新逻辑很简单：

node->height = 1 + max(get_height(node->left), get_height(node->right))
get_height(node) 就是空节点返回 0，否则返回 node->height

这样平衡因子就能在 O(1) 拿到：get_height(node->left) - get_height(node->right)。

四种旋转怎么触发？看平衡因子组合，不是看哪边高

AVL 旋转只由当前节点及其子节点的平衡因子共同决定，不是“左边高就右旋”。比如：

LL 型：当前节点 BF = +2，且左孩子 BF = +1 → 右旋
LR 型：当前节点 BF = +2，但左孩子 BF = -1 → 先对左孩子左旋，再对当前节点右旋
RR 型：当前节点 BF = -2，右孩子 BF = -1 → 左旋
RL 型：当前节点 BF = -2，右孩子 BF = +1 → 先对右孩子右旋，再对当前节点左旋

关键点：必须先更新子节点高度，再判断子节点 BF，否则旋转后高度没更新，下一层校验会出错。

旋转后哪些节点的高度要重算？只重算参与旋转的三个节点

以右旋为例（节点 y 是 x 的左孩子）：旋转只改变 x、y 和 y->right 这三个节点的父子关系，所以只有它们的 height 需要重新计算：

void rotate_right(Node*& x) {
    Node* y = x->left;
    x->left = y->right;
    y->right = x;
    // 只更新 y、x、x->left（即原 y->right）的高度
    update_height(x);
    update_height(y);
    x = y; // 更新根指针
}

update_height() 就是上面说的那行 1 + max(...)。如果顺手把整棵树都遍历一遍更新高度，纯属浪费。