Python如何实现AVL平衡二叉树_通过旋转操作保持查找效率

A VL树插完新节点之后，为什么非得转那么一下？答案很简单：不转，它就不叫A VL了。平衡因子的绝对值一旦突破1，整个树的查找效率就会开始滑坡，而且这种滑坡是隐性的——你查数据可能还挺快，但一动手删除，空指针异常就冒出来了。

A VL树插入后为什么必须旋转？

插入一个节点，本质上是破坏了height(left) - height(right)必须在[-1, 0, 1]范围内的约定。一旦某个节点的平衡因子变成±2，旋转就不是可选项，而是维持A VL定义的强制操作。

常见的问题场景是：get_balance(root)明明返回了2或-2，但旋转没有被触发。这时候search()可能还正常，但delete()会直接报AttributeError: 'NoneType' object has no attribute 'left'——这说明失衡已经沿着路径传导下去，在某个子树里触发了空指针访问。

旋转类型无非四种，但每种背后都有清晰的几何逻辑：

• 左左（LL）：新节点插在左子树的左侧 → 右旋rotate_right(y)
• 右右（RR）：新节点插在右子树的右侧 → 左旋rotate_left(x)
• 左右（LR）：插在左子树的右侧 → 先对左子节点左旋，再对当前节点右旋
• 右左（RL）：插在右子树的左侧 → 先对右子节点右旋，再对当前节点左旋

旋转函数必须同时更新高度和父引用吗？

高度是必须更新的，父引用则视实现方式而定。如果节点不存parent字段，那是比较推荐的做法——旋转时只需要调整left和right的指向，然后重新计算涉及节点的height。如果硬要维护parent，每次旋转后得同步修正三个节点（原根、新根、孙子）的父指针，这里特别容易出错。

性能方面，每次旋转最多影响3个节点的高度。update_height(node)应该只依赖node.left和node.right的height来计算，千万别递归遍历整棵子树，那会白白浪费O(log n)的复杂度。

来看一个右旋的核心逻辑示例：

def rotate_right(y):    x = y.left    y.left = x.right    x.right = y    update_height(y)  # 先更新原根（现在是子节点）    update_height(x)  # 再更新新根    return x

insert()里何时调用rotate？

这里有一个常见的误解：有人以为插入完成后在根节点统一检查平衡性就够了。但实际做法是，在递归回溯的过程中，每层都检查并修复当前节点的平衡性——因为插入只影响从插入点到根的路径，也只有这条路径上的节点可能失衡。

典型的错误写法是这样的：root = insert(root, val); if get_balance(root) not in [-1,0,1]: root = rebalance(root)。这只能修复根节点，中间层的失衡节点被完全漏掉，树很快就会退化成链表。

正确的顺序其实很清晰：

• 递归插入左或右子树
• 更新当前节点的height
• 计算get_balance(current)，如果返回2或-2，执行对应的旋转
• 返回旋转后的新子树根

这里有个关键细节：旋转后返回的节点才是该子树新的根，必须赋值给上层的current.left或current.right。另外，get_balance()的实现必须用getattr(node.left, 'height', -1)，而不是直接写node.left.height——否则遇到空节点就直接崩了。

为什么A VL删除比插入更难处理？

删除操作可能引发向上多层连续失衡，而且失衡类型不能仅凭被删节点的位置来预判。举个例子，删掉右子树的一个叶子，可能导致父节点变成左重（LL），但祖父节点却因为高度变化变成了RL。

关键在于：删除后的修复必须严格沿着递归返回路径逐层进行。每层修复之后，都得重新计算高度，否则下一层调用get_balance()时拿到的数据是错的。

还有一个容易被忽略的细节：delete()里找到替换节点（比如中序前驱）之后，不能简单地node.val = predecessor.val然后直接删前驱——这样会绕过旋转逻辑。正确的做法是真正删除那个节点，让删除操作自然触发向上的修复过程。