前言:AVL 树。它由两位苏联数学家 Adelson-Velsky 和 Landis 在 1962 年发明是史上第一个自平衡二叉搜索树也是理解红黑树和所有平衡树思想的基础。1. 什么是 AVL 树AVL 树是一种严格平衡的二叉搜索树它满足任意节点的左子树高度与右子树高度之差称为平衡因子的绝对值不超过 1。平衡因子bf height(left) - height(right)取值只能是-1、0、1。因为高度差被严格限制AVL 树能保证树高始终是O(log n)从而所有基本操作查找、插入、删除的最坏时间复杂度都是O(log n)。2. 为什么需要 AVL 树在普通 BST 中依次插入1, 2, 3, 4, 5会变成1 \ 2 \ 3 \ 4 \ 5高度变成 5查找 5 要走 5 步。而 AVL 树通过旋转操作会把树调整为近似完全二叉树的形态保持树高在1.44 * log2(n)以内。同样的数据AVL 树大概是2 / \ 1 4 / \ 3 5查找效率高得多。3. AVL 树节点的定义相比 BST 节点我们需要增加一个height字段来记录以该节点为根的子树高度。高度定义为左右子树高度的最大值 1空节点高度视为 0。struct AVLNode { int key; AVLNode* left; AVLNode* right; int height; AVLNode(int k) : key(k), left(nullptr), right(nullptr), height(1) {} };常用辅助函数int height(AVLNode* node) { return node ? node-height : 0; } int getBalance(AVLNode* node) { return node ? height(node-left) - height(node-right) : 0; } void updateHeight(AVLNode* node) { if (node) { node-height std::max(height(node-left), height(node-right)) 1; } }4. 旋转操作 —— AVL 树的核心当插入或删除节点后某节点的平衡因子变为2 或 -2就需要通过旋转来恢复平衡。旋转共四种情况。4.1 右旋Right Rotation——解决“左左”失衡当节点的左子树的左侧插入导致不平衡bf 1且左孩子的bf 0进行一次右旋。y x / \ / \ x T3 --- T1 y / \ / \ T1 T2 T2 T3代码AVLNode* rightRotate(AVLNode* y) { AVLNode* x y-left; AVLNode* T2 x-right; // 旋转 x-right y; y-left T2; // 更新高度先更新 y再更新 x updateHeight(y); updateHeight(x); return x; // 新的根 }4.2 左旋Left Rotation——解决“右右”失衡当节点的右子树的右侧插入导致不平衡bf -1且右孩子的bf 0进行一次左旋。x y / \ / \ T1 y --- x T3 / \ / \ T2 T3 T1 T2代码AVLNode* leftRotate(AVLNode* x) { AVLNode* y x-right; AVLNode* T2 y-left; y-left x; x-right T2; updateHeight(x); updateHeight(y); return y; }4.3 左右旋Left-Right Rotation——解决“左右”失衡当节点左子树的右侧插入导致不平衡bf 1且左孩子的bf 0需要先对左子树做左旋再对当前节点做右旋。y y z / \ / \ / \ x T3 --- z T3 --- x y / \ / \ / \ / \ T1 z x T2 T1 T2 T3 / \ / \ T2 T3 T1 T2代码调用上面两个旋转AVLNode* leftRightRotate(AVLNode* y) { y-left leftRotate(y-left); // 左旋左孩子 return rightRotate(y); // 右旋自己 }4.4 右左旋Right-Left Rotation——解决“右左”失衡当节点右子树的左侧插入导致不平衡bf -1且右孩子的bf 0先对右子树做右旋再对当前节点做左旋。x x z / \ / \ / \ T1 y --- T1 z --- x y / \ / \ / \ / \ z T4 T2 y T1 T2 T4 / \ / \ T2 T3 T3 T4代码AVLNode* rightLeftRotate(AVLNode* x) { x-right rightRotate(x-right); return leftRotate(x); }5. 插入操作插入和 BST 一样递归进行插入后回溯更新高度并检查平衡因子一旦失衡立即做对应旋转。AVLNode* insert(AVLNode* node, int key) { // 1. 普通 BST 插入 if (!node) return new AVLNode(key); if (key node-key) node-left insert(node-left, key); else if (key node-key) node-right insert(node-right, key); else return node; // 重复键不插入 // 2. 更新当前节点高度 updateHeight(node); // 3. 计算平衡因子检查是否失衡 int balance getBalance(node); // 左左情况 if (balance 1 key node-left-key) return rightRotate(node); // 右右情况 if (balance -1 key node-right-key) return leftRotate(node); // 左右情况 if (balance 1 key node-left-key) { node-left leftRotate(node-left); return rightRotate(node); } // 右左情况 if (balance -1 key node-right-key) { node-right rightRotate(node-right); return leftRotate(node); } return node; // 未失衡直接返回 }重要细节每个if里的条件key node-left-key等判断确保了旋转的正确性。如果重复键存在代码会直接返回不会插入也无需平衡。6. 删除操作由于删除操作过于复杂博主本人也还没完全搞明白因此就不在这里讲解了。7. 复杂度与性能特点时间复杂度查找、插入、删除均为 O(log n)而且是最坏情况保证不像 BST 可能退化为 O(n)。空间复杂度每个节点需要额外存储高度int相比 BST 多出常数级内存。旋转开销插入最多只需一次旋转单旋或双旋删除可能需要 O(log n) 次旋转回溯到根。正因为插入/删除时旋转的常数开销比红黑树稍高所以实际工程中红黑树更常见。但 AVL 树在查找密集型场景下性能更好因为它更严格平衡树更矮。8. 小结AVL 树是严格平衡的二叉搜索树左右子树高度差不超过 1。通过四种旋转左旋、右旋、左右旋、右左旋在插入和删除后恢复平衡。所有操作均为 O(log n)适合查找频繁的场景。理解 AVL 树是理解一切平衡树的基础也是数据结构面试的常客。