C++如何实现二叉搜索树的AVL自平衡逻辑与节点高度维护

AVL树节点必须持久化height字段并严格自底向上更新：插入/删除递归回退时调用updateHeight(node)，基于子节点当前height重新计算；所有旋转后显式更新涉及节点height；bf判断需结合当前节点与失衡子节点的bf值，且旋转后高度变化量须准确反映。

AVL树节点必须额外存height字段，且只在插入/删除后更新

AVL平衡依赖每个节点的height值计算平衡因子（bf = left->height - right->height），这个值不能每次计算时递归求——太慢。必须作为节点成员持久化，并在结构变更时**严格按路径自底向上更新**。

常见错误是只更新被旋转节点的height，漏掉祖父或更高层节点；或者在插入后从根往下更新，导致中间节点高度错乱。正确做法是：插入/删除递归回退时，每层都调用updateHeight(node)，该函数仅基于子节点当前height重新赋值：node->height = 1 + max(left ? left->height : -1, right ? right->height : -1)。

• height初始值设为0（单个节点高度为0），空指针对应-1，这样叶子节点height算出来才是0
• 所有旋转操作（LL、RR、LR、RL）前后，必须显式调用updateHeight()更新涉及的2~3个节点
• 删除后回溯更新时，需判断子树是否真被修改——可加返回值标识子树高度是否变化，避免无谓更新

四种旋转的触发条件与子树高度变化必须匹配

不是“左子树高就LL旋转”，而是先算出当前节点bf，再结合**失衡子节点的bf** 判断类型。例如：当前节点bf == 2（左偏重），此时若左孩子bf == 1，才是LL；若左孩子bf == -1，则是LR——后者必须先对左孩子做RR旋转，再对当前节点做LL旋转。

容易忽略的是旋转后各节点height的变化量：一次LL或RR旋转会使得原根节点高度减1，新根高度不变；LR/RL则让原根和原孙子节点高度各减1。如果更新height顺序错或漏，后续平衡因子就全错。

立即学习“C++免费学习笔记（深入）”；

• 写旋转函数时，把updateHeight()调用写死在旋转逻辑末尾，别依赖外部调用
• 判断bf用getBalanceFactor(node)封装，内部处理空指针，避免NULL->height崩溃
• LL/RR是单旋，LR/RL是双旋，但双旋不是两次单旋拼接——中间节点的左右指针在第一次旋转后已变，第二次旋转必须用新结构

插入后只需检查并修复从插入点到根的路径，删除后可能需继续向上修复

插入最多破坏一个地方的平衡，所以从插入位置回溯到根，遇到第一个|bf| > 1的节点就旋转，之后该子树高度恢复，其父节点height不变，无需继续处理。但删除不同：即使某层旋转修复了失衡，其父节点的height可能已减少，导致父节点自身|bf|超限，必须继续向上检查。

• 插入递归返回时，一旦完成旋转就直接返回，不必再更新祖先height（因为旋转已保证子树高度与插入前一致）
• 删除递归返回时，即使做了旋转，也要继续执行updateHeight()并检查父节点bf，直到根或不再失衡
• 可在删除函数中加一个bool返回值，表示“本层子树高度是否变化”，只有变化才需要父节点重新计算bf

C++实现中指针管理与移动语义的取舍

用裸指针实现AVL树最直接，但需手动管理内存；用std::unique_ptr能自动析构，但旋转时指针交换要小心——std::swap(a, b)对unique_ptr安全，但直接赋值（如newRoot->left = oldRoot）会触发移动语义，旧指针自动置空。若没注意这点，后续访问oldRoot->left就是空指针解引用。

• 若用裸指针，务必在delete后置nullptr，并在旋转前后检查空指针
• 若用unique_ptr，所有节点指针声明为std::unique_ptr<node></node>，旋转中用std::move()转移所有权，避免拷贝
• 不建议用shared_ptr——AVL树结构天然是单所有权，引入引用计数纯属拖慢性能

高度维护和旋转逻辑本身不依赖内存模型，但指针操作一错，segmentation fault立刻出现。调试时优先打日志输出每个节点的height和bf，比单步跟指针更高效。