AVL树插入后高度差超2是因为未在递归回溯时更新节点高度且未触发旋转；insert必须返回新根节点，每层需重算height = 1 + max(left, right)，空节点height为0，旋转后须手动更新相关节点高度，选旋转类型依据平衡因子及插入路径。
AVL树插入后为什么高度差突然超2？
因为没在每次递归回溯时更新节点高度，也没触发旋转——insert 必须返回新根节点，否则上层无法感知子树结构变化。常见错误是写成 void insert(node, val) 风格，导致旋转只在局部生效，父节点仍指向旧子树。
正确做法：让 insert 返回当前子树的新根，并强制在每层更新 node.height = 1 + max(get_height(node.left), get_height(node.right))。高度必须从底向上重算，不能靠“+1”硬推。
- 漏掉
get_height(None)返回 0，会导致空节点高度为 None，比较时报TypeError - 旋转后必须重新计算被旋转节点及其子节点的高度（尤其是双旋转中的中间节点）
- 左旋/右旋函数本身不负责更新高度，调用方得手动补上——这是最容易忘的一步
四种旋转怎么选？看平衡因子和插入路径
平衡因子 = get_height(node.left) - get_height(node.right)。插入后若某节点 bf == 2，说明左子树高，需检查左孩子：
-
bf == 2 and get_height(node.left.left) > get_height(node.left.right)→ 右旋（LL） bf == 2 and get_height(node.left.left) → 先左旋左孩子，再右旋当前节点（LR）-
bf == -2 and get_height(node.right.right) > get_height(node.right.left)→ 左旋（RR） bf == -2 and get_height(node.right.right) → 先右旋右孩子，再左旋当前节点（RL）
关键点：不能只看符号，必须比子节点的左右高度——比如 LR 情况下，node.left 的平衡因子其实是 -1，但你不能直接查它，得用 get_height 算。
立即学习“Python免费学习笔记（深入）”；
删除节点后AVL树失衡，比插入更难修复？
是的。插入最多引发一次旋转（沿路径向上最多一次调整），而删除可能造成多层失衡，必须从被删节点的父节点开始，逐层向上检查并旋转，直到根或不再失衡。
-
delete同样必须返回新子树根，且每层都要更新高度、检查平衡因子 - 找中序后继时，若后继有右子树（即不是叶子），删掉它之后还得递归修复——很多人只处理了“删叶子”，漏了这层
- 平衡因子为 ±1 的节点删完可能变成 ±2，但 ±2 的节点删完也可能变回 ±1，所以不能跳过检查
示例：删一个右子树很深的节点，可能导致其父节点从 bf=1 变成 bf=2；再往上，祖父节点原本 bf=0，现在可能变成 bf=1 或 bf=2——必须全链路检查。
Python实现里哪些地方最拖慢性能？
AVL 树本意是 O(log n) 操作，但 Python 实现常因三处变慢：
- 频繁调用
get_height(node)—— 改成在每个节点存height属性，每次旋转/插入后显式更新，别每次都递归算 - 用
isinstance(node, AVLNode)做类型判断 —— 直接用node is None更快，AVLNode 类应确保所有操作都基于实例方法 - 递归深度过大（尤其在 10⁵ 级数据时）——CPython 默认递归限制约 1000，插入/删除链路过长会
RecursionError；改用栈模拟递归，或增大sys.setrecursionlimit()（慎用）
真实项目中，除非明确需要严格 O(log n) 查找+范围查询，否则直接用 sortedcontainers.SortedList 或 bisect 维护有序数组更稳——AVL 的调试成本远高于收益。
