前言AVL 树是最早被提出的自平衡二叉搜索树由 Adelson-Velsky 和 Landis 在 1962 年发表。它在普通二叉搜索树的基础上增加一条约束任意节点的左右子树高度差不超过 1。每次插入或删除后如果某条路径上的节点失衡就通过旋转把它调整回来从而保证树高始终是 O(log n)。常见误解有三个。第一把空树的高度定义成 -1 和 0 混用。两种约定本身都可以但必须在整份代码里统一否则平衡因子会整体偏移 1旋转条件永远不成立或永远成立。第二以为插入只需要在根节点检查平衡。失衡可能发生在从插入点到根的整条路径上必须沿着递归返回的路径逐层更新高度并重平衡。第三以为 AVL 树和红黑树没有区别。两者都保持 O(log n)但 AVL 对平衡的要求更严格查找路径更短插入删除时可能需要更多次旋转红黑树放松了平衡写操作通常更省调整。本文实现 AVL 树的插入部分包括四种旋转和平衡因子维护并给出中序遍历与平衡性检查。示例以 C17 为准。删除操作的思路会在文中说明但代码只保留插入避免篇幅失控。一、节点、高度与平衡因子节点保存键、高度和两个子指针。高度定义为「从该节点到最远叶子的边数加一」空节点高度为 0叶子高度为 1。这个约定下节点高度等于左右孩子高度的较大值加一。平衡因子balance factor定义为左子树高度减右子树高度。AVL 要求每个节点的平衡因子只能是 -1、0 或 1。大于 1 说明左边过高小于 -1 说明右边过高。高度必须缓存在节点里而不是每次递归计算。如果每次求高度都遍历子树单次插入的代价会从 O(log n) 退化到 O(n)。缓存的代价是每次结构变化后要更新更新顺序错了会导致平衡因子基于过期数据计算旋转方向可能选错。量定义空节点叶子高度到最远叶子的边数加一01平衡因子左高减右高00允许范围平衡因子的绝对值不超过 1——二、四种失衡与旋转插入导致失衡时从失衡节点往下看新节点所在的方向有四种组合类型失衡节点的平衡因子左孩子/右孩子的平衡因子调整方式LL大于 1左孩子不小于 0对失衡节点右旋一次LR大于 1左孩子小于 0先对左孩子左旋再对失衡节点右旋RR小于 -1右孩子不大于 0对失衡节点左旋一次RL小于 -1右孩子大于 0先对右孩子右旋再对失衡节点左旋右旋rotate right以失衡节点 y 为轴把它的左孩子 x 提上来x 的右子树变成 y 的左子树y 变成 x 的右孩子。左旋是镜像操作。旋转只改变三条指针不搬移节点代价是常数时间。旋转完成后必须更新高度而且顺序不能反。以右旋为例y 下沉后成为 x 的孩子y 的高度依赖它的新孩子所以要先更新 y再更新 x。反过来先更新 x 时x 的高度还没算上 y 的最终高度结果偏小。LR 和 RL 是「双旋」先对孩子的方向做一次单旋把折线形变成直线形再对失衡节点做一次单旋。只做一次单旋无法解决折线形失衡这是实现中最常见的错误之一。三、插入与重平衡插入沿用二叉搜索树的递归框架比较键往左或往右递归遇到空位创建节点。区别在于递归返回后不能直接返回当前节点而要先把当前节点的高度更新再检查平衡因子必要时旋转最后返回新的子树根。由于旋转可能改变子树的根父节点必须用返回值重新接上孩子。写成insert(n-left, key);而忽略返回值旋转后的新根就丢了树会被破坏。正确写法是n-left insert(n-left, key);。重复键的处理要事先约定。本文选择忽略重复插入直接返回原节点。也可以在每个节点上增加计数或者允许重复键放到右子树不同约定影响查找和删除的语义但都必须保持一致。删除比插入复杂。删除节点后要从被删除位置一路向上重平衡被删节点有两个孩子时通常用中序后继右子树的最小节点替换它的键再删除后继。后继节点也可能触发失衡旋转的四种情况与插入相同但判断条件要覆盖孩子平衡因子为 0 的情形。本文不展开删除代码实现时应当以标准教材或权威资料为准。四、完整示例// 适用于 C17#include algorithm#include iostreamstruct Node {int key;int height;Node* left;Node* right;explicit Node(int k) : key(k), height(1), left(nullptr), right(nullptr) {}};class AVLTree {public:AVLTree() default;~AVLTree() { destroy(root_); }AVLTree(const AVLTree) delete;AVLTree operator(const AVLTree) delete;void insert(int key) { root_ insert(root_, key); }void printInOrder() const {print(root_);std::cout \n;}int height() const { return height(root_); }bool balanced() const { return balanced(root_); }private:static int height(const Node* n) {return n nullptr ? 0 : n-height;}static void update(Node* n) {n-height 1 std::max(height(n-left), height(n-right));}static int balanceFactor(const Node* n) {return n nullptr ? 0 : height(n-left) - height(n-right);}static Node* rotateRight(Node* y) {Node* x y-left;Node* middle x-right;x-right y;y-left middle;update(y); // 先更新下沉的节点update(x); // 再更新新的子树根return x;}static Node* rotateLeft(Node* x) {Node* y x-right;Node* middle y-left;y-left x;x-right middle;update(x);update(y);return y;}static Node* rebalance(Node* n) {update(n);const int bf balanceFactor(n);if (bf 1) {if (balanceFactor(n-left) 0) {n-left rotateLeft(n-left); // LR}return rotateRight(n); // LL}if (bf -1) {if (balanceFactor(n-right) 0) {n-right rotateRight(n-right); // RL}return rotateLeft(n); // RR}return n;}static Node* insert(Node* n, int key) {if (n nullptr) {return new Node(key);}if (key n-key) {n-left insert(n-left, key);} else if (key n-key) {n-right insert(n-right, key);} else {return n; // 重复键忽略}return rebalance(n);}static void print(const Node* n) {if (n nullptr) return;print(n-left);std::cout n-key ;print(n-right);}static bool balanced(const Node* n) {if (n nullptr) return true;const int diff height(n-left) - height(n-right);if (diff -1 || diff 1) return false;return balanced(n-left) balanced(n-right);}static void destroy(Node* n) {if (n nullptr) return;destroy(n-left);destroy(n-right);delete n;}Node* root_ nullptr;};int main() {AVLTree tree;for (int key : {30, 20, 10, 25, 28, 27, 5, 40, 50}) {tree.insert(key);}tree.printInOrder();std::cout height tree.height() \n;std::cout std::boolalpha tree.balanced() \n;return 0;}推演插入序列。先插入 30、20、10此时 30 的平衡因子为 2属于 LL对 30 右旋一次20 成为根10 和 30 分别是左右孩子。继续插入 25、2828 挂在 25 的右边25 所在子树出现 LR 形状先对 25 左旋再对 20 右旋实际失衡点要沿路径判断28 被提到该子树的根。接着插入 27触发新的调整最后插入 5、40、5050 使 40 的平衡因子变成 -2属于 RR对 40 左旋一次。中序遍历的结果应当是按升序排列的键因为 AVL 树首先是一棵二叉搜索树旋转不改变中序序列。height()返回根节点缓存的高度balanced()递归检查每个节点的左右高度差用于确认调整逻辑没有遗漏。rotateRight里的middle是 x 的右子树。右旋之后x 的右孩子变成 y而 x 原来的右子树必须挂到 y 的左边否则这部分节点会丢失。左旋同理。这两条「转移子树」的语句是旋转正确性的关键不能省略。五、复杂度与取舍AVL 树的查找、插入、删除都是 O(log n)因为树高被限制在约 1.44 log(n) 的量级。每个节点额外保存一个int高度空间开销是常数。与红黑树相比AVL 的平衡更严格查找时经过的节点更少但插入和删除后可能需要沿路径做更多次旋转写操作的成本更高。读多写少的场景更适合 AVL读写均衡或写操作频繁的场景红黑树例如std::map的常见实现通常更合适。实现上递归写法简洁但树很深时会有栈溢出风险AVL 的树高是对数级正常数据量下问题不大。析构函数是递归的对于极端深的树同样要注意如果需要处理不可信输入应限制树高或改用迭代式释放。常见坑点坑点一空节点高度在代码里前后不一致。❌ 一处按 -1 处理另一处按 0 处理平衡因子整体偏移。✅ 全文统一用空节点高度 0、叶子高度 1或统一用 -1 和 0。坑点二旋转后高度更新顺序反了。❌ 先update(x)再update(y)x 的高度基于 y 的旧值计算。✅ 右旋先更新 y再更新 x左旋先更新 x再更新 y。坑点三LR/RL 只做单旋。❌ 左孩子右重时直接右旋折线形没有拉直旋转后仍然失衡。✅ 先对孩子做反向单旋再对失衡节点做同向单旋。坑点四插入后忽略递归返回值。❌insert(n-left, key);旋转产生的新子树根没有接回父节点。✅n-left insert(n-left, key);。坑点五只在根节点检查平衡。❌ 插入后只判断root_的平衡因子路径中间的失衡被漏掉。✅ 在递归返回的每一层都更新高度并调用重平衡。坑点六平衡因子的符号定义反了。❌ 用右高减左高却按左高减右高的条件写旋转分支。✅ 明确定义为左高减右高并让判断条件与定义一致。坑点七重复键处理不一致。❌ 插入时允许重复查找时假设唯一删除时只删一个。✅ 明确约定忽略、计数或放到某一侧并让所有操作遵守。坑点八以为 AVL 在任何场景都比红黑树好。❌ 写操作频繁的系统也一律选 AVL。✅ 读多写少选 AVL写多或需要与标准库容器行为接近时选红黑树。总结操作复杂度关键点查找O(log n)树高受平衡因子约束插入O(log n)递归返回时逐层更新与重平衡删除O(log n)删除后沿路径重平衡双孩子用后继替换旋转O(1)转移子树、按顺序更新高度空间O(n)每个节点多存一个高度AVL 树的代码量不大难点在于把「高度约定、平衡因子方向、旋转后的高度更新顺序、递归返回值」这四件事保持一致。任何一处不一致树可能仍然能跑但会悄悄失去平衡最终退化成链表。写完插入后用中序遍历检查有序性、用递归检查每个节点的平衡因子是成本最低的自检方式。 
长河君 · 2026/11/5 2:12:46 · 阅读 1.2k C++数据结构之AVL树的实现
前言AVL 树是最早被提出的自平衡二叉搜索树由 Adelson-Velsky 和 Landis 在 1962 年发表。它在普通二叉搜索树的基础上增加一条约束任意节点的左右子树高度差不超过 1。每次插入或删除后如果某条路径上的节点失衡就通过旋转把它调整回来从而保证树高始终是 O(log n)。常见误解有三个。第一把空树的高度定义成 -1 和 0 混用。两种约定本身都可以但必须在整份代码里统一否则平衡因子会整体偏移 1旋转条件永远不成立或永远成立。第二以为插入只需要在根节点检查平衡。失衡可能发生在从插入点到根的整条路径上必须沿着递归返回的路径逐层更新高度并重平衡。第三以为 AVL 树和红黑树没有区别。两者都保持 O(log n)但 AVL 对平衡的要求更严格查找路径更短插入删除时可能需要更多次旋转红黑树放松了平衡写操作通常更省调整。本文实现 AVL 树的插入部分包括四种旋转和平衡因子维护并给出中序遍历与平衡性检查。示例以 C17 为准。删除操作的思路会在文中说明但代码只保留插入避免篇幅失控。一、节点、高度与平衡因子节点保存键、高度和两个子指针。高度定义为「从该节点到最远叶子的边数加一」空节点高度为 0叶子高度为 1。这个约定下节点高度等于左右孩子高度的较大值加一。平衡因子balance factor定义为左子树高度减右子树高度。AVL 要求每个节点的平衡因子只能是 -1、0 或 1。大于 1 说明左边过高小于 -1 说明右边过高。高度必须缓存在节点里而不是每次递归计算。如果每次求高度都遍历子树单次插入的代价会从 O(log n) 退化到 O(n)。缓存的代价是每次结构变化后要更新更新顺序错了会导致平衡因子基于过期数据计算旋转方向可能选错。量定义空节点叶子高度到最远叶子的边数加一01平衡因子左高减右高00允许范围平衡因子的绝对值不超过 1——二、四种失衡与旋转插入导致失衡时从失衡节点往下看新节点所在的方向有四种组合类型失衡节点的平衡因子左孩子/右孩子的平衡因子调整方式LL大于 1左孩子不小于 0对失衡节点右旋一次LR大于 1左孩子小于 0先对左孩子左旋再对失衡节点右旋RR小于 -1右孩子不大于 0对失衡节点左旋一次RL小于 -1右孩子大于 0先对右孩子右旋再对失衡节点左旋右旋rotate right以失衡节点 y 为轴把它的左孩子 x 提上来x 的右子树变成 y 的左子树y 变成 x 的右孩子。左旋是镜像操作。旋转只改变三条指针不搬移节点代价是常数时间。旋转完成后必须更新高度而且顺序不能反。以右旋为例y 下沉后成为 x 的孩子y 的高度依赖它的新孩子所以要先更新 y再更新 x。反过来先更新 x 时x 的高度还没算上 y 的最终高度结果偏小。LR 和 RL 是「双旋」先对孩子的方向做一次单旋把折线形变成直线形再对失衡节点做一次单旋。只做一次单旋无法解决折线形失衡这是实现中最常见的错误之一。三、插入与重平衡插入沿用二叉搜索树的递归框架比较键往左或往右递归遇到空位创建节点。区别在于递归返回后不能直接返回当前节点而要先把当前节点的高度更新再检查平衡因子必要时旋转最后返回新的子树根。由于旋转可能改变子树的根父节点必须用返回值重新接上孩子。写成insert(n-left, key);而忽略返回值旋转后的新根就丢了树会被破坏。正确写法是n-left insert(n-left, key);。重复键的处理要事先约定。本文选择忽略重复插入直接返回原节点。也可以在每个节点上增加计数或者允许重复键放到右子树不同约定影响查找和删除的语义但都必须保持一致。删除比插入复杂。删除节点后要从被删除位置一路向上重平衡被删节点有两个孩子时通常用中序后继右子树的最小节点替换它的键再删除后继。后继节点也可能触发失衡旋转的四种情况与插入相同但判断条件要覆盖孩子平衡因子为 0 的情形。本文不展开删除代码实现时应当以标准教材或权威资料为准。四、完整示例// 适用于 C17#include algorithm#include iostreamstruct Node {int key;int height;Node* left;Node* right;explicit Node(int k) : key(k), height(1), left(nullptr), right(nullptr) {}};class AVLTree {public:AVLTree() default;~AVLTree() { destroy(root_); }AVLTree(const AVLTree) delete;AVLTree operator(const AVLTree) delete;void insert(int key) { root_ insert(root_, key); }void printInOrder() const {print(root_);std::cout \n;}int height() const { return height(root_); }bool balanced() const { return balanced(root_); }private:static int height(const Node* n) {return n nullptr ? 0 : n-height;}static void update(Node* n) {n-height 1 std::max(height(n-left), height(n-right));}static int balanceFactor(const Node* n) {return n nullptr ? 0 : height(n-left) - height(n-right);}static Node* rotateRight(Node* y) {Node* x y-left;Node* middle x-right;x-right y;y-left middle;update(y); // 先更新下沉的节点update(x); // 再更新新的子树根return x;}static Node* rotateLeft(Node* x) {Node* y x-right;Node* middle y-left;y-left x;x-right middle;update(x);update(y);return y;}static Node* rebalance(Node* n) {update(n);const int bf balanceFactor(n);if (bf 1) {if (balanceFactor(n-left) 0) {n-left rotateLeft(n-left); // LR}return rotateRight(n); // LL}if (bf -1) {if (balanceFactor(n-right) 0) {n-right rotateRight(n-right); // RL}return rotateLeft(n); // RR}return n;}static Node* insert(Node* n, int key) {if (n nullptr) {return new Node(key);}if (key n-key) {n-left insert(n-left, key);} else if (key n-key) {n-right insert(n-right, key);} else {return n; // 重复键忽略}return rebalance(n);}static void print(const Node* n) {if (n nullptr) return;print(n-left);std::cout n-key ;print(n-right);}static bool balanced(const Node* n) {if (n nullptr) return true;const int diff height(n-left) - height(n-right);if (diff -1 || diff 1) return false;return balanced(n-left) balanced(n-right);}static void destroy(Node* n) {if (n nullptr) return;destroy(n-left);destroy(n-right);delete n;}Node* root_ nullptr;};int main() {AVLTree tree;for (int key : {30, 20, 10, 25, 28, 27, 5, 40, 50}) {tree.insert(key);}tree.printInOrder();std::cout height tree.height() \n;std::cout std::boolalpha tree.balanced() \n;return 0;}推演插入序列。先插入 30、20、10此时 30 的平衡因子为 2属于 LL对 30 右旋一次20 成为根10 和 30 分别是左右孩子。继续插入 25、2828 挂在 25 的右边25 所在子树出现 LR 形状先对 25 左旋再对 20 右旋实际失衡点要沿路径判断28 被提到该子树的根。接着插入 27触发新的调整最后插入 5、40、5050 使 40 的平衡因子变成 -2属于 RR对 40 左旋一次。中序遍历的结果应当是按升序排列的键因为 AVL 树首先是一棵二叉搜索树旋转不改变中序序列。height()返回根节点缓存的高度balanced()递归检查每个节点的左右高度差用于确认调整逻辑没有遗漏。rotateRight里的middle是 x 的右子树。右旋之后x 的右孩子变成 y而 x 原来的右子树必须挂到 y 的左边否则这部分节点会丢失。左旋同理。这两条「转移子树」的语句是旋转正确性的关键不能省略。五、复杂度与取舍AVL 树的查找、插入、删除都是 O(log n)因为树高被限制在约 1.44 log(n) 的量级。每个节点额外保存一个int高度空间开销是常数。与红黑树相比AVL 的平衡更严格查找时经过的节点更少但插入和删除后可能需要沿路径做更多次旋转写操作的成本更高。读多写少的场景更适合 AVL读写均衡或写操作频繁的场景红黑树例如std::map的常见实现通常更合适。实现上递归写法简洁但树很深时会有栈溢出风险AVL 的树高是对数级正常数据量下问题不大。析构函数是递归的对于极端深的树同样要注意如果需要处理不可信输入应限制树高或改用迭代式释放。常见坑点坑点一空节点高度在代码里前后不一致。❌ 一处按 -1 处理另一处按 0 处理平衡因子整体偏移。✅ 全文统一用空节点高度 0、叶子高度 1或统一用 -1 和 0。坑点二旋转后高度更新顺序反了。❌ 先update(x)再update(y)x 的高度基于 y 的旧值计算。✅ 右旋先更新 y再更新 x左旋先更新 x再更新 y。坑点三LR/RL 只做单旋。❌ 左孩子右重时直接右旋折线形没有拉直旋转后仍然失衡。✅ 先对孩子做反向单旋再对失衡节点做同向单旋。坑点四插入后忽略递归返回值。❌insert(n-left, key);旋转产生的新子树根没有接回父节点。✅n-left insert(n-left, key);。坑点五只在根节点检查平衡。❌ 插入后只判断root_的平衡因子路径中间的失衡被漏掉。✅ 在递归返回的每一层都更新高度并调用重平衡。坑点六平衡因子的符号定义反了。❌ 用右高减左高却按左高减右高的条件写旋转分支。✅ 明确定义为左高减右高并让判断条件与定义一致。坑点七重复键处理不一致。❌ 插入时允许重复查找时假设唯一删除时只删一个。✅ 明确约定忽略、计数或放到某一侧并让所有操作遵守。坑点八以为 AVL 在任何场景都比红黑树好。❌ 写操作频繁的系统也一律选 AVL。✅ 读多写少选 AVL写多或需要与标准库容器行为接近时选红黑树。总结操作复杂度关键点查找O(log n)树高受平衡因子约束插入O(log n)递归返回时逐层更新与重平衡删除O(log n)删除后沿路径重平衡双孩子用后继替换旋转O(1)转移子树、按顺序更新高度空间O(n)每个节点多存一个高度AVL 树的代码量不大难点在于把「高度约定、平衡因子方向、旋转后的高度更新顺序、递归返回值」这四件事保持一致。任何一处不一致树可能仍然能跑但会悄悄失去平衡最终退化成链表。写完插入后用中序遍历检查有序性、用递归检查每个节点的平衡因子是成本最低的自检方式。