尧图网站建设 
如果你维护过一个在内存里用二叉搜索树BST存订单号的系统你大概率见过类似的诡异现象数据量只有几十万按理说查找一次应该是微秒级可线上接口偶尔会卡到几十毫秒甚至上百毫秒。查来查去最后定位到的问题往往只有一个——树退化了。二叉搜索树在没有约束的情况下最坏会退化成一条链表。平衡二叉树AVL_Tree就是为根治这个问题而生的它给每个节点加了一个“高度”约束让任意节点的左右子树高度差不超过1从而把查找、插入、删除的最坏复杂度都锁死在O(log n)。这篇文章我想把AVL树从设计动机、平衡因子、四种旋转到插入和删除时维护平衡的完整链路再到一份可以直接运行的Python实现和调试经验系统地梳理一遍。适合刚学完二叉树、想彻底搞懂平衡树原理的同学也适合准备面试算法题、需要把AVL吃透的读者。1. 普通二叉搜索树是怎么一步步变成链表的——先理解AVL存在的理由1.1 一个让人头皮发麻的线上现象假设你在内存里维护一个按ID排序的在线用户表。因为要频繁按ID查询并且要按顺序遍历你选用了二叉搜索树。开始的时候数据是随机插入的一切正常单次查找几百纳秒非常丝滑。后来业务改了用户ID改成了趋势递增的注册号每天新增几万条。大概过了一个月报表页打开越来越慢接口耗时从几毫秒涨到了几百毫秒。问题出在哪你以为树还是平衡的实际上它已经在不知不觉中长成了一条“右斜链”。每天新增的ID都比已有的大插入时每次都往右子树走树的高度在一路涨。这不是某个人的代码写得差所有不限制形状的二叉搜索树天然就有这个问题。1.2 BST查找效率的本质树的高度二叉搜索树的查找过程很简单每比较一次要么去左子树要么去右子树路径上经过的节点数就决定了单次查找的耗时。路径长取决于树的高度而树的高度又完全由插入顺序决定。最好情况下数据均匀分散树高约为log2(n)级别。最坏情况下数据按顺序插入树退化成一条链树高就是n。用数字算一笔账在100万条有序数据里平衡的树最多20次比较就能定位目标退化的链表需要最多100万次。20次比较和100万次比较性能差了5万倍。这就是为什么说“平衡性”是二叉搜索树的命门不是锦上添花是生死攸关。1962年Adelson-Velsky和Landis提出了第一棵自平衡二叉搜索树也就是AVL_Tree。它的核心思想非常朴素不允许任何节点的左右子树高度差超过1。这个“不允许”不是碰运气而是通过一套机械化的旋转操作来强制保证。2. 平衡因子与四种旋转AVL树恢复平衡的全部底牌2.1 平衡因子怎么算失衡的定义是什么先约定一个基础规则。空节点的高度视为0叶子节点的高度视为1。任意节点的高度等于左、右子树高度较大值加1。AVL对平衡的定义是任意节点的左子树高度与右子树高度之差的绝对值不超过1。这个差值就叫平衡因子Balance Factor。balance height(left) - height(right)当某个节点的balance为2或-2时这棵树就失衡了需要进行旋转调整。读者可以先记住这个结论平衡因子只可能是-1、0、1一旦变成2或-2说明插入或删除破坏了AVL性质。2.2 右旋和左旋两个最基础的“整形手术”先看最常见的LL型失衡。假设节点y失衡它的左子树比右子树高2且导致失衡的节点插在y的左孩子的左子树里。结构大致长这样y / \ x T3 / \ T1 T2注意这里x的左孩子T1可能是新插入节点或者新节点在T1的某个子树里总之是“左边更高”的路径。解决办法是右旋。把x提上来当子树根y降为x的右孩子x原来的右子树T2改挂到y的左孩子位置。x / \ T1 y / \ T2 T3旋转完成后整棵子树重新满足BST性质T1的所有值小于x的值x的值小于T2的所有值T2的值小于y的值y的值小于T3的值。中序遍历结果旋转前后完全一致这个特点很重要——旋转本质上是一次不影响排序顺序的局部重构。RR型失衡是LL的镜像。失衡节点的右子树高2且失衡路径在右孩子的右子树。解法是左旋对称执行即可。y / \ T1 x / \ T2 T3左旋后x / \ y T3 / \ T1 T22.3 LR和RL为什么有时候必须旋转两次有些情况下一次旋转解决不了问题。看这个结构失衡节点y的左子树高2但路径是插入在y.left的右子树里。y / \ x T4 / \ T1 z / \ T2 T3如果直接对y执行右旋把x提上来x / \ T1 y / \ z T4 / \ T2 T3你会发现y的平衡因子变成了-2树仍然失衡。这是典型的“救完左边右边又倒了”。正确的做法是先对x执行左旋把z提上来担任x位置的根让结构变成LL型再对y执行右旋。两步之后结构才恢复平衡。第一步对x左旋 y / \ z T4 / \ T1 x / \ T2 T3 第二步对y右旋 z / \ x y / \ / \ T1 T2 T3 T4RL型是LR的镜像先右旋再左旋。这类旋转在资料里通常叫LR旋转和RL旋转。其实名字不重要关键是记住一个判断逻辑失衡路径是“之字形”的就需要两次旋转是“一条直线”的就一次旋转。2.4 旋转实现中最容易写错的两个细节第一个坑旋转后更新高度的顺序不能乱。旋转改变了父子关系原先的孩子变成新根原先的根变成孩子。先更新孩子节点的高度再更新新根的高度。如果顺序反了新根会拿到旧的孩子高度算出来的平衡因子是错的。第二个坑空节点的高度返回0不要直接访问height属性。否则在删除时一旦节点变成None再取height直接抛AttributeError。稳妥的办法是写一个get_height(node)辅助函数统一处理None。3. 插入后的重平衡从叶子节点逐层向上的维护链路3.1 插入操作的三步走AVL树的插入比普通BST多一个“恢复平衡”的环节但递归实现下来逻辑反而很清晰按二叉搜索树规则找到空位插入新叶子节点。沿着递归返回路径重新计算每个祖先节点的高度。每到一个节点就检查平衡因子一旦发现绝对值大于1立刻执行对应旋转。递归写法的精妙之处在于插入完成后的每一次return都会把子树的根重新赋值给上一级高度和平衡性都能被逐层刷新。这样你不需要手动维护一个“从插入点向上走”的循环递归栈天然承担了这个角色。下面是完整的插入代码class AVLNode: def __init__(self, key): self.key key self.left None self.right None self.height 1 class AVLTree: def __init__(self): self.root None def get_height(self, node): return node.height if node else 0 def get_balance(self, node): return self.get_height(node.left) - self.get_height(node.right) if node else 0 def update_height(self, node): node.height 1 max(self.get_height(node.left), self.get_height(node.right)) def rotate_right(self, y): x y.left t2 x.right x.right y y.left t2 self.update_height(y) self.update_height(x) return x def rotate_left(self, x): y x.right t2 y.left y.left x x.right t2 self.update_height(x) self.update_height(y) return y def insert(self, node, key): if not node: return AVLNode(key) if key node.key: node.left self.insert(node.left, key) elif key node.key: node.right self.insert(node.right, key) else: return node self.update_height(node) balance self.get_balance(node) # LL型 if balance 1 and key node.left.key: return self.rotate_right(node) # RR型 if balance -1 and key node.right.key: return self.rotate_left(node) # LR型 if balance 1 and key node.left.key: node.left self.rotate_left(node.left) return self.rotate_right(node) # RL型 if balance -1 and key node.right.key: node.right self.rotate_right(node.right) return self.rotate_left(node) return node插入路径上第一次遇到失衡节点时就会触发旋转旋转完成后这个子树的根会作为返回值交给更上层的节点。上层节点继续更新高度、检查平衡因子但由于旋转后子树高度已经恢复正常上层的平衡因子通常不会再超界。3.2 为什么插入只需要“一轮”旋转就能恢复平衡这是AVL树一个非常优雅的性质值得单独拿出来讲。假设某个节点Y插入前平衡因子已经是1左子树比右子树高1。插入一个节点到Y的左子树后左子树高度再涨1Y的平衡因子变成2触发失衡。右旋完成后Y的左子树根x被提升为新根。旋转后整个子树的高度恰好等于Y在插入前的高度。这意味着什么意味着Y之上的所有祖先节点它们以Y为根的这棵子树高度没有变化所以祖先们的高度、平衡因子跟插入前完全一样不需要继续向上调整。直观来理解插入操作只会让一棵子树长高1旋转把多出来的“高度冗余”消耗掉了整棵子树被压回原来的高度。这是插入只需要一次重平衡的理论依据。3.3 插入时判断旋转类型的小技巧看代码里的判断方式insert的平衡判断用的是“目标key与子节点key比较”其实更通用的做法是看子节点的平衡因子。但插入时用key比较有一个好处语义直观容易debug。新插入的key如果小于node.left.key说明插在左子树的更左边这就是LL型如果大于node.left.key说明绕到了左子树的右边属于LR型。两条判断配合平衡因子正好覆盖四种情况。如果你觉得自己容易记混有个笨但有效的办法在纸上把失衡节点的平衡因子符号画出来。balance1表示左边高接着看插入的key落在左孩子的哪一边balance-1表示右边高看右孩子那一侧。方向判断清楚了再套旋转基本不会错。4. 删除后的级联失衡比插入更棘手的重平衡过程4.1 删除节点时的BST基本规则删除节点要分三种情况叶子节点直接移除。只有一个孩子让孩子顶替被删节点。有两个孩子经典做法是找到右子树中的最小值节点中序后继把它的key复制到当前节点再递归删除位于右子树中的那个后继节点。为什么找右子树最小值而不是随便找个节点因为右子树最小值是大于当前节点key的最小值复制到当前节点后中序遍历的有序性不会被打乱BST的性质依然成立。递归实现里最容易被忽略的是如果node的两个孩子都为空要返回None。只写node node.left或者node node.right在这个分支下会保留原节点删除方法就失效了。4.2 级联失衡是怎么发生的删除和插入最大的不同在于插入操作经过一轮旋转就能恢复平衡删除却可能需要在回溯路径上多次旋转。原因是删除让某棵子树的高度减1减量会沿着递归返回路径一路向上传播。我构造一个例子说明。假设某棵AVL树中节点P的右子树比左子树高1平衡因子为-1。现在删除P左子树里的一个叶子节点左子树高度减1P的平衡因子变成-2P失衡了。我们对P执行旋转旋转完成后以P为根的子树的整体高度可能又比旋转前减了1。这个“减1”继续向上传播导致P的祖先节点也跟着失衡。处理完一个失衡点还要继续往上看直到根节点。所以删除后的重平衡逻辑必须是从递归返回路径的第一层开始每一层都检查平衡因子发现失衡就旋转然后继续向上检查。下面是删除的完整代码def get_min(self, node): while node.left: node node.left return node def delete(self, node, key): if not node: return node if key node.key: node.left self.delete(node.left, key) elif key node.key: node.right self.delete(node.right, key) else: if not node.left or not node.right: temp node.left if node.left else node.right if not temp: return None else: node temp else: temp self.get_min(node.right) node.key temp.key node.right self.delete(node.right, temp.key) if not node: return node self.update_height(node) balance self.get_balance(node) # LL型 if balance 1 and self.get_balance(node.left) 0: return self.rotate_right(node) # LR型 if balance 1 and self.get_balance(node.left) 0: node.left self.rotate_left(node.left) return self.rotate_right(node) # RR型 if balance -1 and self.get_balance(node.right) 0: return self.rotate_left(node) # RL型 if balance -1 and self.get_balance(node.right) 0: node.right self.rotate_right(node.right) return self.rotate_left(node) return node注意这段代码里我在update_height之前加了一个if not node: return node的判断。为什么需要因为删除分支里可能返回None如果不提前拦截下面直接调update_height会空指针报错。4.3 删除时旋转类型判断与插入的差异删除时的旋转类型判断不能再用key比较了。原因有两个第一被删除的key已经不在树里了。特别是两个孩子都存在的情况我们用后继节点的key覆盖了当前节点然后递归删除了后继节点本身。到回溯阶段你再拿原始key跟node.left.key做比较语义已经对不上。第二删除后左子树的平衡因子可以直接反映“问题出在哪一侧”。如果失衡节点平衡因子大于1说明左子树高这时候看node.left的平衡因子大于等于0说明左子树的失衡路径在左侧或者本身就是LL的形态小于0说明左子树的右侧偏高需要先左旋再右旋。你可能会疑惑为什么删除时要加上 0而不是 0。因为当node.left的平衡因子为0时虽然当前节点unbalance是2理论上右旋之后子树整体高度会减1依然需要继续向上回溯但右旋本身是正确的一步。这个边界情况在删除操作里很常见插入时不怎么遇到但在删除的代码里必须考虑。删除与插入的判断逻辑差异可以整理成一张表操作类型失衡判断旋转类型判断依据是否可能级联插入新key与node.left.key比较新key落在子树哪一侧不会一轮旋转即恢复删除子节点的平衡因子子节点BF符号决定旋转类型可能需回溯到根5. 一份可直接跑的AVL树Python实现与验证用例5.1 完整代码节点、旋转、插入、删除把上面的代码合并成完整文件再加上检查平衡性和中序遍历的辅助函数一份可以独立运行的AVL树实现如下class AVLNode: def __init__(self, key): self.key key self.left None self.right None self.height 1 class AVLTree: def __init__(self): self.root None def get_height(self, node): return node.height if node else 0 def get_balance(self, node): return self.get_height(node.left) - self.get_height(node.right) if node else 0 def update_height(self, node): node.height 1 max(self.get_height(node.left), self.get_height(node.right)) def rotate_right(self, y): x y.left t2 x.right x.right y y.left t2 self.update_height(y) self.update_height(x) return x def rotate_left(self, x): y x.right t2 y.left y.left x x.right t2 self.update_height(x) self.update_height(y) return y def insert(self, node, key): if not node: return AVLNode(key) if key node.key: node.left self.insert(node.left, key) elif key node.key: node.right self.insert(node.right, key) else: return node self.update_height(node) balance self.get_balance(node) # LL型 if balance 1 and key node.left.key: return self.rotate_right(node) # RR型 if balance -1 and key node.right.key: return self.rotate_left(node) # LR型 if balance 1 and key node.left.key: node.left self.rotate_left(node.left) return self.rotate_right(node) # RL型 if balance -1 and key node.right.key: node.right self.rotate_right(node.right) return self.rotate_left(node) return node def get_min(self, node): while node.left: node node.left return node def delete(self, node, key): if not node: return node if key node.key: node.left self.delete(node.left, key) elif key node.key: node.right self.delete(node.right, key) else: if not node.left or not node.right: temp node.left if node.left else node.right if not temp: return None else: node temp else: temp self.get_min(node.right) node.key temp.key node.right self.delete(node.right, temp.key) if not node: return node self.update_height(node) balance self.get_balance(node) # LL型 if balance 1 and self.get_balance(node.left) 0: return self.rotate_right(node) # LR型 if balance 1 and self.get_balance(node.left) 0: node.left self.rotate_left(node.left) return self.rotate_right(node) # RR型 if balance -1 and self.get_balance(node.right) 0: return self.rotate_left(node) # RL型 if balance -1 and self.get_balance(node.right) 0: node.right self.rotate_right(node.right) return self.rotate_left(node) return node def is_bst(self, node, min_keyfloat(-inf), max_keyfloat(inf)): if not node: return True if not (min_key node.key max_key): return False return (self.is_bst(node.left, min_key, node.key) and self.is_bst(node.right, node.key, max_key)) def is_balanced(self, node): if not node: return True if abs(self.get_balance(node)) 1: return False return self.is_balanced(node.left) and self.is_balanced(node.right) def inorder(self, node, result): if not node: return self.inorder(node.left, result) result.append(node.key) self.inorder(node.right, result)5.2 用三种典型数据验证树的平衡性验证AVL树写没写对我的习惯是跑三类用例第一类有序插入。连续插入1到7检查中序遍历是否为有序序列再检查每个节点平衡因子绝对值是否都不超过1。tree AVLTree() for i in range(1, 8): tree.root tree.insert(tree.root, i) result [] tree.inorder(tree.root, result) assert result [1, 2, 3, 4, 5, 6, 7] assert tree.is_bst(tree.root) assert tree.is_balanced(tree.root)如果这棵树的AVL实现正确插入1到7后根节点应该是4第二层是2和6第三层是1、3、5、7。树的高度是3。换成普通BST这棵树会变成深度7的右斜链AVL的性质立竿见影。第二类随机大样本。插入10万个随机不重复整数最后检查整棵树高度。理论上100万节点AVL树的高度不会超过约2 * log2(n)10万节点的树高通常在20以内。这个数据能把旋转逻辑暴露得很彻底。import random tree AVLTree() keys random.sample(range(1000000), 100000) for k in keys: tree.root tree.insert(tree.root, k) assert tree.is_bst(tree.root) assert tree.is_balanced(tree.root) print(树高:, tree.get_height(tree.root)) print(log2(n)约:, round(math.log2(len(keys)), 2))第三类删除压力测试。插入一批数据后随机删除其中的一半再验证BST性质和平衡性。特别注意删除两个孩子的节点这块是级联旋转最容易漏掉的情况。keys random.sample(range(1000000), 10000) tree AVLTree() for k in keys: tree.root tree.insert(tree.root, k) remove_keys random.sample(keys, 5000) for k in remove_keys: tree.root tree.delete(tree.root, k) result [] tree.inorder(tree.root, result) assert result sorted(result) assert tree.is_bst(tree.root) assert tree.is_balanced(tree.root)三组测试都跑通基本可以判断这棵树的插入、删除、旋转逻辑是自洽的。5.3 调试AVL树时我自己踩过的坑分享几个实际写AVL树时容易出问题的地方第一个坑是更新高度的顺序。旋转之后忘记先更新孩子节点的高度直接更新父节点结果平衡因子怎么算都是不对的。我当时是拿一个三个节点的单旋用例反复调试才意识到是这个问题。后来养成了习惯凡是rotateright或rotateleft一定先update_height孩子再update_height新根。第二个坑是删除叶子节点时返回None。代码里两个分支都不满足时如果不显式返回Nonenode就还是原来的节点删除操作完全没有生效。这个逻辑在普通BST里可能问题不大但在AVL里会导致上层节点高度计算全部出错。第三个坑是打印调试时只看中序遍历。中序遍历只能证明BST性质没被破坏不能证明平衡性。最好是把层序遍历也打出来一层一层看节点分布很快就能定位到某个节点的高度算错了。6. 写在最后AVL树与红黑树、跳表的选型逻辑6.1 为什么很多系统没选AVL树如果AVL树这么严格为什么Java的TreeMap、C STL的std::map底层默认用红黑树而不是AVL树核心原因在于平衡的严格程度不同。红黑树只要求最长路径不超过最短路径的两倍而AVL树要求任意节点左右子树高度差不超过1。这带来的直接后果是AVL树在查找时确实更快因为树更矮但插入和删除时为了维护1以内的平衡差AVL需要旋转的频率远高于红黑树。如果业务场景是写操作频繁比如每秒大量插入删除红黑树的整体吞吐往往比AVL树更高。Java的HashMap在链表转红黑树时也选了红黑树也是考虑到hash冲突场景下写操作占比不低红黑树的重平衡代价更可控。6.2 什么场景下AVL树依然是优选AVL树的应用场景没有过时。当你的数据完全在内存中且操作模式是“写入少、读取极多”时比如订单簿的价格排序、排行榜、一批需要频繁按序读取的热点数据AVL树因为树高更矮查找路径更短实测性能往往优于红黑树。另外AVL树的旋转模型是所有自平衡树的“基本功”。理解了AVL的四种旋转再去看红黑树的变色和旋转、跳表的索引层级都会觉得更轻松。准备面试算法题的时候手写AVL树虽然不常考但它是检验你递归设计和指针操作熟练度的好题目。这里顺带提一个困惑过很多人的点Redis的有序集合zset为什么用跳表而不用AVL树或红黑树因为跳表在做区间查询、按排名查找时实现更简单修改节点时不需要像树结构那样做大规模的重平衡操作而且跳表在并发环境下的锁粒度更容易控制。这并不代表跳表在“查找单点”上比AVL快而是综合了实现成本、区间操作、并发性能之后的选择。我个人在实际写代码时的体会是业务开发里真正需要手写AVL树的场景很少语言自带的有序容器大多够用。但有一件事我觉得值得做——自己用递归实现一遍AVL的插入、删除和四种旋转然后跑随机数据验证。这个过程能帮你把“递归返回值怎么传”“高度什么时候更新”“旋转判断依据是什么”这几个数据结构里的核心思维彻底理清楚。之后再遇到任何平衡结构心里都有底。 AVL树详解：从平衡因子到四种旋转的完整实现
如果你维护过一个在内存里用二叉搜索树BST存订单号的系统你大概率见过类似的诡异现象数据量只有几十万按理说查找一次应该是微秒级可线上接口偶尔会卡到几十毫秒甚至上百毫秒。查来查去最后定位到的问题往往只有一个——树退化了。二叉搜索树在没有约束的情况下最坏会退化成一条链表。平衡二叉树AVL_Tree就是为根治这个问题而生的它给每个节点加了一个“高度”约束让任意节点的左右子树高度差不超过1从而把查找、插入、删除的最坏复杂度都锁死在O(log n)。这篇文章我想把AVL树从设计动机、平衡因子、四种旋转到插入和删除时维护平衡的完整链路再到一份可以直接运行的Python实现和调试经验系统地梳理一遍。适合刚学完二叉树、想彻底搞懂平衡树原理的同学也适合准备面试算法题、需要把AVL吃透的读者。1. 普通二叉搜索树是怎么一步步变成链表的——先理解AVL存在的理由1.1 一个让人头皮发麻的线上现象假设你在内存里维护一个按ID排序的在线用户表。因为要频繁按ID查询并且要按顺序遍历你选用了二叉搜索树。开始的时候数据是随机插入的一切正常单次查找几百纳秒非常丝滑。后来业务改了用户ID改成了趋势递增的注册号每天新增几万条。大概过了一个月报表页打开越来越慢接口耗时从几毫秒涨到了几百毫秒。问题出在哪你以为树还是平衡的实际上它已经在不知不觉中长成了一条“右斜链”。每天新增的ID都比已有的大插入时每次都往右子树走树的高度在一路涨。这不是某个人的代码写得差所有不限制形状的二叉搜索树天然就有这个问题。1.2 BST查找效率的本质树的高度二叉搜索树的查找过程很简单每比较一次要么去左子树要么去右子树路径上经过的节点数就决定了单次查找的耗时。路径长取决于树的高度而树的高度又完全由插入顺序决定。最好情况下数据均匀分散树高约为log2(n)级别。最坏情况下数据按顺序插入树退化成一条链树高就是n。用数字算一笔账在100万条有序数据里平衡的树最多20次比较就能定位目标退化的链表需要最多100万次。20次比较和100万次比较性能差了5万倍。这就是为什么说“平衡性”是二叉搜索树的命门不是锦上添花是生死攸关。1962年Adelson-Velsky和Landis提出了第一棵自平衡二叉搜索树也就是AVL_Tree。它的核心思想非常朴素不允许任何节点的左右子树高度差超过1。这个“不允许”不是碰运气而是通过一套机械化的旋转操作来强制保证。2. 平衡因子与四种旋转AVL树恢复平衡的全部底牌2.1 平衡因子怎么算失衡的定义是什么先约定一个基础规则。空节点的高度视为0叶子节点的高度视为1。任意节点的高度等于左、右子树高度较大值加1。AVL对平衡的定义是任意节点的左子树高度与右子树高度之差的绝对值不超过1。这个差值就叫平衡因子Balance Factor。balance height(left) - height(right)当某个节点的balance为2或-2时这棵树就失衡了需要进行旋转调整。读者可以先记住这个结论平衡因子只可能是-1、0、1一旦变成2或-2说明插入或删除破坏了AVL性质。2.2 右旋和左旋两个最基础的“整形手术”先看最常见的LL型失衡。假设节点y失衡它的左子树比右子树高2且导致失衡的节点插在y的左孩子的左子树里。结构大致长这样y / \ x T3 / \ T1 T2注意这里x的左孩子T1可能是新插入节点或者新节点在T1的某个子树里总之是“左边更高”的路径。解决办法是右旋。把x提上来当子树根y降为x的右孩子x原来的右子树T2改挂到y的左孩子位置。x / \ T1 y / \ T2 T3旋转完成后整棵子树重新满足BST性质T1的所有值小于x的值x的值小于T2的所有值T2的值小于y的值y的值小于T3的值。中序遍历结果旋转前后完全一致这个特点很重要——旋转本质上是一次不影响排序顺序的局部重构。RR型失衡是LL的镜像。失衡节点的右子树高2且失衡路径在右孩子的右子树。解法是左旋对称执行即可。y / \ T1 x / \ T2 T3左旋后x / \ y T3 / \ T1 T22.3 LR和RL为什么有时候必须旋转两次有些情况下一次旋转解决不了问题。看这个结构失衡节点y的左子树高2但路径是插入在y.left的右子树里。y / \ x T4 / \ T1 z / \ T2 T3如果直接对y执行右旋把x提上来x / \ T1 y / \ z T4 / \ T2 T3你会发现y的平衡因子变成了-2树仍然失衡。这是典型的“救完左边右边又倒了”。正确的做法是先对x执行左旋把z提上来担任x位置的根让结构变成LL型再对y执行右旋。两步之后结构才恢复平衡。第一步对x左旋 y / \ z T4 / \ T1 x / \ T2 T3 第二步对y右旋 z / \ x y / \ / \ T1 T2 T3 T4RL型是LR的镜像先右旋再左旋。这类旋转在资料里通常叫LR旋转和RL旋转。其实名字不重要关键是记住一个判断逻辑失衡路径是“之字形”的就需要两次旋转是“一条直线”的就一次旋转。2.4 旋转实现中最容易写错的两个细节第一个坑旋转后更新高度的顺序不能乱。旋转改变了父子关系原先的孩子变成新根原先的根变成孩子。先更新孩子节点的高度再更新新根的高度。如果顺序反了新根会拿到旧的孩子高度算出来的平衡因子是错的。第二个坑空节点的高度返回0不要直接访问height属性。否则在删除时一旦节点变成None再取height直接抛AttributeError。稳妥的办法是写一个get_height(node)辅助函数统一处理None。3. 插入后的重平衡从叶子节点逐层向上的维护链路3.1 插入操作的三步走AVL树的插入比普通BST多一个“恢复平衡”的环节但递归实现下来逻辑反而很清晰按二叉搜索树规则找到空位插入新叶子节点。沿着递归返回路径重新计算每个祖先节点的高度。每到一个节点就检查平衡因子一旦发现绝对值大于1立刻执行对应旋转。递归写法的精妙之处在于插入完成后的每一次return都会把子树的根重新赋值给上一级高度和平衡性都能被逐层刷新。这样你不需要手动维护一个“从插入点向上走”的循环递归栈天然承担了这个角色。下面是完整的插入代码class AVLNode: def __init__(self, key): self.key key self.left None self.right None self.height 1 class AVLTree: def __init__(self): self.root None def get_height(self, node): return node.height if node else 0 def get_balance(self, node): return self.get_height(node.left) - self.get_height(node.right) if node else 0 def update_height(self, node): node.height 1 max(self.get_height(node.left), self.get_height(node.right)) def rotate_right(self, y): x y.left t2 x.right x.right y y.left t2 self.update_height(y) self.update_height(x) return x def rotate_left(self, x): y x.right t2 y.left y.left x x.right t2 self.update_height(x) self.update_height(y) return y def insert(self, node, key): if not node: return AVLNode(key) if key node.key: node.left self.insert(node.left, key) elif key node.key: node.right self.insert(node.right, key) else: return node self.update_height(node) balance self.get_balance(node) # LL型 if balance 1 and key node.left.key: return self.rotate_right(node) # RR型 if balance -1 and key node.right.key: return self.rotate_left(node) # LR型 if balance 1 and key node.left.key: node.left self.rotate_left(node.left) return self.rotate_right(node) # RL型 if balance -1 and key node.right.key: node.right self.rotate_right(node.right) return self.rotate_left(node) return node插入路径上第一次遇到失衡节点时就会触发旋转旋转完成后这个子树的根会作为返回值交给更上层的节点。上层节点继续更新高度、检查平衡因子但由于旋转后子树高度已经恢复正常上层的平衡因子通常不会再超界。3.2 为什么插入只需要“一轮”旋转就能恢复平衡这是AVL树一个非常优雅的性质值得单独拿出来讲。假设某个节点Y插入前平衡因子已经是1左子树比右子树高1。插入一个节点到Y的左子树后左子树高度再涨1Y的平衡因子变成2触发失衡。右旋完成后Y的左子树根x被提升为新根。旋转后整个子树的高度恰好等于Y在插入前的高度。这意味着什么意味着Y之上的所有祖先节点它们以Y为根的这棵子树高度没有变化所以祖先们的高度、平衡因子跟插入前完全一样不需要继续向上调整。直观来理解插入操作只会让一棵子树长高1旋转把多出来的“高度冗余”消耗掉了整棵子树被压回原来的高度。这是插入只需要一次重平衡的理论依据。3.3 插入时判断旋转类型的小技巧看代码里的判断方式insert的平衡判断用的是“目标key与子节点key比较”其实更通用的做法是看子节点的平衡因子。但插入时用key比较有一个好处语义直观容易debug。新插入的key如果小于node.left.key说明插在左子树的更左边这就是LL型如果大于node.left.key说明绕到了左子树的右边属于LR型。两条判断配合平衡因子正好覆盖四种情况。如果你觉得自己容易记混有个笨但有效的办法在纸上把失衡节点的平衡因子符号画出来。balance1表示左边高接着看插入的key落在左孩子的哪一边balance-1表示右边高看右孩子那一侧。方向判断清楚了再套旋转基本不会错。4. 删除后的级联失衡比插入更棘手的重平衡过程4.1 删除节点时的BST基本规则删除节点要分三种情况叶子节点直接移除。只有一个孩子让孩子顶替被删节点。有两个孩子经典做法是找到右子树中的最小值节点中序后继把它的key复制到当前节点再递归删除位于右子树中的那个后继节点。为什么找右子树最小值而不是随便找个节点因为右子树最小值是大于当前节点key的最小值复制到当前节点后中序遍历的有序性不会被打乱BST的性质依然成立。递归实现里最容易被忽略的是如果node的两个孩子都为空要返回None。只写node node.left或者node node.right在这个分支下会保留原节点删除方法就失效了。4.2 级联失衡是怎么发生的删除和插入最大的不同在于插入操作经过一轮旋转就能恢复平衡删除却可能需要在回溯路径上多次旋转。原因是删除让某棵子树的高度减1减量会沿着递归返回路径一路向上传播。我构造一个例子说明。假设某棵AVL树中节点P的右子树比左子树高1平衡因子为-1。现在删除P左子树里的一个叶子节点左子树高度减1P的平衡因子变成-2P失衡了。我们对P执行旋转旋转完成后以P为根的子树的整体高度可能又比旋转前减了1。这个“减1”继续向上传播导致P的祖先节点也跟着失衡。处理完一个失衡点还要继续往上看直到根节点。所以删除后的重平衡逻辑必须是从递归返回路径的第一层开始每一层都检查平衡因子发现失衡就旋转然后继续向上检查。下面是删除的完整代码def get_min(self, node): while node.left: node node.left return node def delete(self, node, key): if not node: return node if key node.key: node.left self.delete(node.left, key) elif key node.key: node.right self.delete(node.right, key) else: if not node.left or not node.right: temp node.left if node.left else node.right if not temp: return None else: node temp else: temp self.get_min(node.right) node.key temp.key node.right self.delete(node.right, temp.key) if not node: return node self.update_height(node) balance self.get_balance(node) # LL型 if balance 1 and self.get_balance(node.left) 0: return self.rotate_right(node) # LR型 if balance 1 and self.get_balance(node.left) 0: node.left self.rotate_left(node.left) return self.rotate_right(node) # RR型 if balance -1 and self.get_balance(node.right) 0: return self.rotate_left(node) # RL型 if balance -1 and self.get_balance(node.right) 0: node.right self.rotate_right(node.right) return self.rotate_left(node) return node注意这段代码里我在update_height之前加了一个if not node: return node的判断。为什么需要因为删除分支里可能返回None如果不提前拦截下面直接调update_height会空指针报错。4.3 删除时旋转类型判断与插入的差异删除时的旋转类型判断不能再用key比较了。原因有两个第一被删除的key已经不在树里了。特别是两个孩子都存在的情况我们用后继节点的key覆盖了当前节点然后递归删除了后继节点本身。到回溯阶段你再拿原始key跟node.left.key做比较语义已经对不上。第二删除后左子树的平衡因子可以直接反映“问题出在哪一侧”。如果失衡节点平衡因子大于1说明左子树高这时候看node.left的平衡因子大于等于0说明左子树的失衡路径在左侧或者本身就是LL的形态小于0说明左子树的右侧偏高需要先左旋再右旋。你可能会疑惑为什么删除时要加上 0而不是 0。因为当node.left的平衡因子为0时虽然当前节点unbalance是2理论上右旋之后子树整体高度会减1依然需要继续向上回溯但右旋本身是正确的一步。这个边界情况在删除操作里很常见插入时不怎么遇到但在删除的代码里必须考虑。删除与插入的判断逻辑差异可以整理成一张表操作类型失衡判断旋转类型判断依据是否可能级联插入新key与node.left.key比较新key落在子树哪一侧不会一轮旋转即恢复删除子节点的平衡因子子节点BF符号决定旋转类型可能需回溯到根5. 一份可直接跑的AVL树Python实现与验证用例5.1 完整代码节点、旋转、插入、删除把上面的代码合并成完整文件再加上检查平衡性和中序遍历的辅助函数一份可以独立运行的AVL树实现如下class AVLNode: def __init__(self, key): self.key key self.left None self.right None self.height 1 class AVLTree: def __init__(self): self.root None def get_height(self, node): return node.height if node else 0 def get_balance(self, node): return self.get_height(node.left) - self.get_height(node.right) if node else 0 def update_height(self, node): node.height 1 max(self.get_height(node.left), self.get_height(node.right)) def rotate_right(self, y): x y.left t2 x.right x.right y y.left t2 self.update_height(y) self.update_height(x) return x def rotate_left(self, x): y x.right t2 y.left y.left x x.right t2 self.update_height(x) self.update_height(y) return y def insert(self, node, key): if not node: return AVLNode(key) if key node.key: node.left self.insert(node.left, key) elif key node.key: node.right self.insert(node.right, key) else: return node self.update_height(node) balance self.get_balance(node) # LL型 if balance 1 and key node.left.key: return self.rotate_right(node) # RR型 if balance -1 and key node.right.key: return self.rotate_left(node) # LR型 if balance 1 and key node.left.key: node.left self.rotate_left(node.left) return self.rotate_right(node) # RL型 if balance -1 and key node.right.key: node.right self.rotate_right(node.right) return self.rotate_left(node) return node def get_min(self, node): while node.left: node node.left return node def delete(self, node, key): if not node: return node if key node.key: node.left self.delete(node.left, key) elif key node.key: node.right self.delete(node.right, key) else: if not node.left or not node.right: temp node.left if node.left else node.right if not temp: return None else: node temp else: temp self.get_min(node.right) node.key temp.key node.right self.delete(node.right, temp.key) if not node: return node self.update_height(node) balance self.get_balance(node) # LL型 if balance 1 and self.get_balance(node.left) 0: return self.rotate_right(node) # LR型 if balance 1 and self.get_balance(node.left) 0: node.left self.rotate_left(node.left) return self.rotate_right(node) # RR型 if balance -1 and self.get_balance(node.right) 0: return self.rotate_left(node) # RL型 if balance -1 and self.get_balance(node.right) 0: node.right self.rotate_right(node.right) return self.rotate_left(node) return node def is_bst(self, node, min_keyfloat(-inf), max_keyfloat(inf)): if not node: return True if not (min_key node.key max_key): return False return (self.is_bst(node.left, min_key, node.key) and self.is_bst(node.right, node.key, max_key)) def is_balanced(self, node): if not node: return True if abs(self.get_balance(node)) 1: return False return self.is_balanced(node.left) and self.is_balanced(node.right) def inorder(self, node, result): if not node: return self.inorder(node.left, result) result.append(node.key) self.inorder(node.right, result)5.2 用三种典型数据验证树的平衡性验证AVL树写没写对我的习惯是跑三类用例第一类有序插入。连续插入1到7检查中序遍历是否为有序序列再检查每个节点平衡因子绝对值是否都不超过1。tree AVLTree() for i in range(1, 8): tree.root tree.insert(tree.root, i) result [] tree.inorder(tree.root, result) assert result [1, 2, 3, 4, 5, 6, 7] assert tree.is_bst(tree.root) assert tree.is_balanced(tree.root)如果这棵树的AVL实现正确插入1到7后根节点应该是4第二层是2和6第三层是1、3、5、7。树的高度是3。换成普通BST这棵树会变成深度7的右斜链AVL的性质立竿见影。第二类随机大样本。插入10万个随机不重复整数最后检查整棵树高度。理论上100万节点AVL树的高度不会超过约2 * log2(n)10万节点的树高通常在20以内。这个数据能把旋转逻辑暴露得很彻底。import random tree AVLTree() keys random.sample(range(1000000), 100000) for k in keys: tree.root tree.insert(tree.root, k) assert tree.is_bst(tree.root) assert tree.is_balanced(tree.root) print(树高:, tree.get_height(tree.root)) print(log2(n)约:, round(math.log2(len(keys)), 2))第三类删除压力测试。插入一批数据后随机删除其中的一半再验证BST性质和平衡性。特别注意删除两个孩子的节点这块是级联旋转最容易漏掉的情况。keys random.sample(range(1000000), 10000) tree AVLTree() for k in keys: tree.root tree.insert(tree.root, k) remove_keys random.sample(keys, 5000) for k in remove_keys: tree.root tree.delete(tree.root, k) result [] tree.inorder(tree.root, result) assert result sorted(result) assert tree.is_bst(tree.root) assert tree.is_balanced(tree.root)三组测试都跑通基本可以判断这棵树的插入、删除、旋转逻辑是自洽的。5.3 调试AVL树时我自己踩过的坑分享几个实际写AVL树时容易出问题的地方第一个坑是更新高度的顺序。旋转之后忘记先更新孩子节点的高度直接更新父节点结果平衡因子怎么算都是不对的。我当时是拿一个三个节点的单旋用例反复调试才意识到是这个问题。后来养成了习惯凡是rotateright或rotateleft一定先update_height孩子再update_height新根。第二个坑是删除叶子节点时返回None。代码里两个分支都不满足时如果不显式返回Nonenode就还是原来的节点删除操作完全没有生效。这个逻辑在普通BST里可能问题不大但在AVL里会导致上层节点高度计算全部出错。第三个坑是打印调试时只看中序遍历。中序遍历只能证明BST性质没被破坏不能证明平衡性。最好是把层序遍历也打出来一层一层看节点分布很快就能定位到某个节点的高度算错了。6. 写在最后AVL树与红黑树、跳表的选型逻辑6.1 为什么很多系统没选AVL树如果AVL树这么严格为什么Java的TreeMap、C STL的std::map底层默认用红黑树而不是AVL树核心原因在于平衡的严格程度不同。红黑树只要求最长路径不超过最短路径的两倍而AVL树要求任意节点左右子树高度差不超过1。这带来的直接后果是AVL树在查找时确实更快因为树更矮但插入和删除时为了维护1以内的平衡差AVL需要旋转的频率远高于红黑树。如果业务场景是写操作频繁比如每秒大量插入删除红黑树的整体吞吐往往比AVL树更高。Java的HashMap在链表转红黑树时也选了红黑树也是考虑到hash冲突场景下写操作占比不低红黑树的重平衡代价更可控。6.2 什么场景下AVL树依然是优选AVL树的应用场景没有过时。当你的数据完全在内存中且操作模式是“写入少、读取极多”时比如订单簿的价格排序、排行榜、一批需要频繁按序读取的热点数据AVL树因为树高更矮查找路径更短实测性能往往优于红黑树。另外AVL树的旋转模型是所有自平衡树的“基本功”。理解了AVL的四种旋转再去看红黑树的变色和旋转、跳表的索引层级都会觉得更轻松。准备面试算法题的时候手写AVL树虽然不常考但它是检验你递归设计和指针操作熟练度的好题目。这里顺带提一个困惑过很多人的点Redis的有序集合zset为什么用跳表而不用AVL树或红黑树因为跳表在做区间查询、按排名查找时实现更简单修改节点时不需要像树结构那样做大规模的重平衡操作而且跳表在并发环境下的锁粒度更容易控制。这并不代表跳表在“查找单点”上比AVL快而是综合了实现成本、区间操作、并发性能之后的选择。我个人在实际写代码时的体会是业务开发里真正需要手写AVL树的场景很少语言自带的有序容器大多够用。但有一件事我觉得值得做——自己用递归实现一遍AVL的插入、删除和四种旋转然后跑随机数据验证。这个过程能帮你把“递归返回值怎么传”“高度什么时候更新”“旋转判断依据是什么”这几个数据结构里的核心思维彻底理清楚。之后再遇到任何平衡结构心里都有底。