企业官网建设流程全解析

如果你维护过一个在内存里用二叉搜索树（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 T2

2.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 T4

RL型是LR的镜像，先右旋再左旋。

这类旋转在资料里通常叫LR旋转和RL旋转。其实名字不重要，关键是记住一个判断逻辑：失衡路径是“之字形”的就需要两次旋转，是“一条直线”的就一次旋转。

2.4 旋转实现中最容易写错的两个细节

第一个坑：旋转后更新高度的顺序不能乱。旋转改变了父子关系，原先的孩子变成新根，原先的根变成孩子。先更新孩子节点的高度，再更新新根的高度。如果顺序反了，新根会拿到旧的孩子高度，算出来的平衡因子是错的。

第二个坑：空节点的高度返回0，不要直接访问height属性。否则在删除时，一旦节点变成None，再取height直接抛AttributeError。稳妥的办法是写一个get_height(node)辅助函数，统一处理None。

3. 插入后的重平衡：从叶子节点逐层向上的维护链路

3.1 插入操作的三步走

AVL树的插入比普通BST多一个“恢复平衡”的环节，但递归实现下来逻辑反而很清晰：

1. 按二叉搜索树规则找到空位，插入新叶子节点。
2. 沿着递归返回路径，重新计算每个祖先节点的高度。
3. 每到一个节点就检查平衡因子，一旦发现绝对值大于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的左子树后，左子树高度再涨1，Y的平衡因子变成2，触发失衡。

右旋完成后，Y的左子树根x被提升为新根。旋转后整个子树的高度，恰好等于Y在插入前的高度。这意味着什么？意味着Y之上的所有祖先节点，它们以Y为根的这棵子树高度没有变化，所以祖先们的高度、平衡因子跟插入前完全一样，不需要继续向上调整。

直观来理解：插入操作只会让一棵子树长高1，旋转把多出来的“高度冗余”消耗掉了，整棵子树被压回原来的高度。这是插入只需要一次重平衡的理论依据。

3.3 插入时判断旋转类型的小技巧

看代码里的判断方式：

insert的平衡判断用的是“目标key与子节点key比较”

其实更通用的做法是看子节点的平衡因子。但插入时用key比较有一个好处：语义直观，容易debug。新插入的key如果小于node.left.key，说明插在左子树的更左边，这就是LL型；如果大于node.left.key，说明绕到了左子树的右边，属于LR型。两条判断配合平衡因子，正好覆盖四种情况。

如果你觉得自己容易记混，有个笨但有效的办法：在纸上把失衡节点的平衡因子符号画出来。balance>1表示左边高，接着看插入的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左子树里的一个叶子节点，左子树高度减1，P的平衡因子变成-2，P失衡了。我们对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，依然需要继续向上回溯，但右旋本身是正确的一步。这个边界情况在删除操作里很常见，插入时不怎么遇到，但在删除的代码里必须考虑。

删除与插入的判断逻辑差异，可以整理成一张表：

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_key=float("-inf"), max_key=float("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。代码里两个分支都不满足时，如果不显式返回None，node就还是原来的节点，删除操作完全没有生效。这个逻辑在普通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的插入、删除和四种旋转，然后跑随机数据验证。这个过程能帮你把“递归返回值怎么传”“高度什么时候更新”“旋转判断依据是什么”这几个数据结构里的核心思维彻底理清楚。之后再遇到任何平衡结构，心里都有底。