【C++】手搓AVL树

Ne0inhk

— 37 min read
【C++】手搓AVL树

手搓AVL树

手搓AVL树

github地址

有梦想的电信狗

0. 前言

之前的文章我们实现了二叉搜索树（BST），虽然它能在平均情况下提供不错的查找性能，但当输入数据趋于有序时，BST 会退化为链表结构，查找效率将从 O ( log ⁡ N ) O(\log N) O(logN) 直降为 O ( N ) O(N) O(N) —— 这在工程中几乎是无法接受的。

为了解决这种性能退化问题，我们引入了更“聪明”的树形结构 —— AVL 树。
它通过在插入和删除过程中实时调整自身结构，让整棵树始终保持“平衡”状态，使得查找、插入、删除操作的时间复杂度都能稳定在 O ( log ⁡ N ) O(\log N) O(logN)。

本文将从最基础的平衡因子概念讲起，逐步实现一棵功能完整的 AVLTree<K, V> 模板类，详细剖析其核心操作：

  • 插入逻辑的演化过程（从 BST 到 AVL）
  • 平衡因子的更新与传播机制
  • 单旋与双旋的触发与实现原理
  • 旋转后平衡因子的维护策略
文章最后还将通过数千万随机数据进行验证，确保代码逻辑与性能的可靠性。让我们一起手搓出一棵真正能“自我修复”的平衡二叉搜索树吧 🚀

1. 二叉搜索树的缺陷

性能分析

  • 查找 / 插入 / 删除（平均）时间复杂度：O(h)，h 为树高。
  • 空间：迭代版本额外 O(1)；递归版本额外 O(h) 递归栈。
  • 拷贝构造/Copy: O(n) 时间与 O(h) 递归栈。
在这里插入图片描述

结点数为N的二叉搜索树，最多查找高度次。对于随机插入的平衡树平均 h = O(log n)；最坏情况下 h = O(n)。

  • 最优情况下：⼆叉搜索树为完全⼆叉树(或者接近完全二叉树)，其高度为： log2 N
  • 最差情况下：⼆叉搜索树（退化为单链表），其高度为： N，查找效率退化为O(N)，这也正是二叉搜索树的缺陷

综合而言，⼆叉搜索树增删查改时间复杂度为： O(N)，这样的效率显然是⽆法满⾜我们需求的

  • 今天我们来认识二叉搜索树的进阶形态——AVL 树，满足我们在内存中存储和搜索数据高性能需求。

2. 什么是AVL树

概念与定义

二叉搜索树虽可以缩短查找的效率，但如果数据有序或接近有序二叉搜索树将退化为单支树，查找元素相当于在链表中搜索元素，效率低下。

AVL树：是一种 自平衡二叉搜索树，由苏联数学家 Georgy Adelson-Velsky 和 Evgenii Landis 在 1962 年提出，其名称来源于这两位发明者的名字缩写。

  • AVL树是最早发明的自平衡二叉搜索树
    • 当向二叉搜索树中插入新结点后，如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整)，即可降低树的高度，从而减少平均搜索长度。
  • AVL树是在普通二叉搜索树的基础上增加了平衡条件，确保树始终保持近似平衡状态
  • AVL树要么是空树，要么是满足以下性质的二叉搜索树：
    • 其左、右子树也都是 AVL 树
    • 左、右子树高度之差(简称平衡因子)的绝对值不超过 1

如果一棵二叉搜索树是高度平衡的，它就是AVL树。如果它有n个结点，其高度可保持在O( l o g 2 n log_2 n log2​n)，搜索时间复杂度O( l o g 2 n log_2 n log2​n)

平衡因子

AVL 树是一颗高度平衡的搜索二叉树，通过控制高度差去控制平衡

AVL树可以始终保持平衡状态，是因为在实现 AVL 树时，我们引入了 平衡因子（balance factor） 的概念：

每个节点都有一个平衡因子，其值等于该节点右子树的高度减去左子树的高度

  • 因此：任何节点的平衡因子只能是 0、1 或 - 1

当然平衡因子并非 AVL 树的必需属性，因为AVL 树的维持平衡不一定需要平衡因子，也可以动态计算高度或其他方法使 AVL 树保持平衡

  • 使用平衡因子实现只是实现平衡的其中一种方式

但平衡因子如同一个 “风向标”：

  • 可以更方便我们去观察和控制树是否平衡
  • 高效控制树的平衡维护过程 —— 通过判断平衡因子是否超出 [-1, 1] 范围
  • 可快速定位需要调整的节点，进而通过旋转操作恢复树的平衡

以下就是一颗AVL树，同时附有相应的平衡因子

在这里插入图片描述

而下面这棵树就不是一棵 AVL 树，因为 10 这个节点它的左右子树的高度差超过了 1

在这里插入图片描述

基本性质

核心特点：

  • 高度近似平衡：AVL 树通过不断调整树的结构，保证树的左右子树高度差始终在允许范围内，使得树的高度相对较低。
    • 例如：在插入或删除节点后，会通过旋转操作（左旋、右旋、左右双旋、右左双旋）来重新平衡树，从而维持高度平衡。
  • 查找效率稳定：
    • 由于 AVL 树高度平衡，其高度近似于 O ( l o g N ) O(logN) O(logN)，其中n是节点数量，这意味着在 AVL 树中进行查找操作时，时间复杂度稳定在O ( l o g N ) O(log N) O(logN)
    • 相比于普通二叉搜索树在最坏情况下可能退化为链表，查找时间复杂度为 O ( n ) O(n) O(n)，AVL 树查找效率更高且稳定

基本操作：

  • 插入：
    • 新节点插入后，从插入节点开始向上检查祖先节点的平衡因子。如果发现某个节点的平衡因子绝对值超过 1，就需要进行旋转操作来恢复平衡。
  • 查找：
    • 按照普通二叉搜索树的查找逻辑查找，时间复杂度为O ( log N )

优缺比较：

  • 优点：查找效率高且稳定，时间复杂度为O ( log N ) ，适用于对查找效率要求较高，且插入和删除操作相对不太频繁的场景。
  • 缺点：每次插入和删除操作都可能需要进行旋转来维持平衡，这会增加额外的计算开销，导致插入和删除操作的时间复杂度比普通二叉搜索树要高一些。

为什么AVL树不要求左右子树的高度为0呢？

为什么AVL 树要求左右子树的高度差不超过 1，而非必须为 0 呢？

从平衡的理想状态看，高度差为 0 确实更平衡，但实际情况中，部分树的结构无法满足这一要求：

  • 当树的节点数为 2、4 ……等特定数量时，最优的高度差只能是 1，无法强制达到 0
  • 这说明 AVL 树的平衡条件是在 “绝对平衡” 和 “实现可行性” 之间的权衡设计

3. AVL树的实现

整体架构设计

AVL树的结点定义

  • AVL树为模版实现
template<classK,classV>structAVLTreeNode{ pair<K, V> _kv;// 键值对// 三叉链 AVLTreeNode<K, V>* _left; AVLTreeNode<K, V>* _right; AVLTreeNode<K, V>* _parent;// 插入结点后，需要更新平衡因子，有了_parent,可以很方便的找父节点int _balanceFactor;// balance factor 平衡因子，用于判断当前子树 有没有出现不平衡的问题// Node结点 的构造函数AVLTreeNode(const pair<K, V>& kv):_kv(kv),_left(nullptr),_right(nullptr),_parent(nullptr),_balanceFactor(0)// 新结点 初始的平衡因子为 0{}};
  • 搜索树常用于存储键值，方便查找关键字，这里我们使用std::pair<K, V>来存储我们的键值对
  • 结点中的成员变量：采用三叉链的方式实现
    • AVLTreeNode<K, V>* _left：指向左孩子的指针
    • AVLTreeNode<K, V>* _right：指向右孩子的指针
    • AVLTreeNode<K, V>* _parent：指向父节点的指针
      • 插入结点后，需要更新平衡因子，有了_parent,可以很方便的找父节点
    • int _balanceFactor：平衡因子，用于判断当前子树 有没有出现不平衡的问题
  • 默认构造函数AVLTreeNode(const pair<K, V>& kv)：
    • 将三个指针初始化为nullptr，初始化平衡因子为0
    • 使用kv初始化类内的_kv成员
  • 结点采用struct设计，默认权限为public，方便下文的AVLTree类访问成员

AVL树设计

  • 我们采用的设计：左右子树高度之差的绝对值 小于等于 1 (-1 0 1)
  • 方便起见：我们使用 平衡因子 == 右子树的高度 - 左子树的高度
template<classK,classV>classAVLTree{typedef AVLTreeNode<K, V> Node;private: AVLTreeNode<K, V>* _root =nullptr;public:// ... 对外共有接口private:// ... 内部私有成员函数};
  • AVLTreeNode<K, V>* _root = nullptr：初始时根节点为空
  • typedef AVLTreeNode<K, V> Node：结点类型重定义，简化书写

AVL树的操作实现

插入

1. 本质

插入操作的本质是：

  • AVL 树的插入操作是在二叉搜索树插入逻辑基础上，增加了平衡维护的关键步骤，核心要解决 “插入新节点可能破坏树的平衡，导致查询效率下降” 的问题。
2. 思路简述

插入操作思路的简述：

AVL 树插入 == 二叉搜索树插入（找位置、挂节点） + 平衡修复（更新平衡因子 + 旋转调整）

流程分 5 步：

  1. 空树处理：树为空时，新节点直接作为根
  2. 查找插入位置：从根出发，**按二叉搜索树规则（小往左、大往右）**找到新节点的父节点 parent，确定挂左还是挂右
  3. 挂载新节点：创建新节点，连接到 parent 的 左 or 右 子树，并维护 parent 指针
  4. 更新平衡因子：从新节点的父节点开始，向上更新路径上所有节点的平衡因子（_balacnFactor），反映子树高度变化
  5. 平衡修复：根据平衡因子判断是否失衡（绝对值 ≥ 2），若失衡则通过旋转操作（单旋 / 双旋）恢复平衡，同时更新旋转后节点的平衡因子
3. 二叉搜索树的插入逻辑
public:boolinsert(const pair<K, V>& kv){// 先走二叉搜索树的插入逻辑if(_root ==nullptr){ _root =newNode(kv);returntrue;}// _root 不为空时的操作 Node* parent =nullptr; Node* curNode = _root;// 先找空，找到一个可以插入的位置while(curNode){if(kv.first < curNode->_kv.first){ parent = curNode; curNode = curNode->_left;}elseif(kv.first > curNode->_kv.first){ parent = curNode; curNode = curNode->_right;}// 搜索树中不允许有重复的值 对于已有值，不插入elsereturnfalse;}// while 循环结束后，代表找到了可以插入的位置// 找到位置了，但父节点不知道 新结点 比自己大还是比自己小，需要再次判断 curNode =newNode(kv);if(curNode->_kv.first < parent->_kv.first) parent->_left = curNode;else parent->_right = curNode; curNode->_parent = parent;// 以上是二叉搜索树的插入逻辑，这样插入可能导致树不平衡，从而导致查找效率退化为 O(n)// 以下是AVL树对二叉搜索树 进行的 控制平衡 操作 的代码 // 控制平衡 ... }

详细讲解二叉搜索树迭代插入的逻辑）：

  • 插入时，需要先找到空位置，默认插入的元素不能重复
  1. 空树特判：若 _root == nullptr，直接把根设为新节点（new Node(key)）。
  2. 否则从 _root 向下查找插入位置：
    • 使用 curNode 跟随，parent 保存其父节点（因为当 curNode 为 nullptr 时需要把新节点挂到 parent）。
    • 如果 kv.first > curNode->_kv.first，curNode沿右子树移动；kv.first < curNode->_kv.first时，curNode沿左子树移动。
    • 如果kv.first == curNode->_kv.first，返回 false（二叉搜索树默认不允许重复键）。
  3. 当 curNode 走到 nullptr（找到空位）后，代表curNode已找到合适的可以插入的位置。
  4. new Node(kv) 建节点
    • 要插入新结点，必须修改curNode的父节点内的左右孩子指针，但父节点并不知道要插入的 key 比自己大还是自己小，只知道下面由位置可以插入，不知道插入到哪个位置
    • 因此要根据 key 与 parent->_key 的比较把它接为左/右子节点。
      • 如果 curNode->_kv.first > parent->_kv.first → 插到右边 (parent->_right = curNode)
      • 如果 curNode->_kv.first < parent->_kv.first → 插到左边 (parent->_left = curNode)
  • 总结：✔️ 循环结束时，位置已经找到了，就是 curNode == nullptr 的地方。
    ✔️ 但是插入操作不能直接修改 curNode，必须通过 parent 去改指针。
    ✔️ 而 parent 自己并不知道空位是在左边还是右边，所以需要再比较一次来决定。
4. 更新平衡因子
1. 插入后父节点的平衡因子变化分析
  • 新创建结点的平衡因子：
  • 新结点插入在右：
  • 新结点插入在左：
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
2. 平衡因子更新后的三种情况：
    1. 更新后平衡因子 == 0：不用继续沿着到root的路径往上更新平衡因子
    1. 更新后平衡因子 == 1 or -1：继续沿着到root的路径往上更新平衡因子
    1. 更新后平衡因子 == 2 or -2：树已失衡，需进行旋转
在这里插入图片描述
3. 更新平衡因子的最坏情况
  • 更新平衡因子的最坏情况：为一路更新到根节点，因此可以使用循环控制更新，循环条件为while(parent)
在这里插入图片描述
4. 更新平衡因子的代码实现
public:boolinsert(const pair<K, V>& kv){// ... 以上是二叉搜索树的插入逻辑，这样插入可能导致树不平衡，从而导致查找效率退化为 O(n)// 以下是AVL树对二叉搜索树 进行的 控制平衡 操作 ... // 插入后，最坏情况时: 可能root的平衡因子需要更新，只有root的parent为空while(parent){// 插入后 ，先更新平衡因子if(curNode == parent->_left)--parent->_balanceFactor;else// if (curNode == parent->_right)++parent->_balanceFactor;// 当前parent结点更新完了，判断是否还需要再往上更新 // 处理平衡因子更新后有三种情况// 情况一 parent所在子树高度不变且平衡，无需更新 和 旋转， 结束循环if(parent->_balanceFactor ==0){break;}// 情况二 parent 所在子树高度变了，继续往上更新elseif(parent->_balanceFactor ==1|| parent->_balanceFactor ==-1){ curNode = parent; parent = parent->_parent;}// 情况三 当前子树不平衡了，需要旋转elseif(parent->_balanceFactor ==2|| parent->_balanceFactor ==-2){// 旋转的情况和操作}else// 其他情况报错assert(false);// 平衡因子不是 0 1 -1 2 -2 直接报错}// 插入结束后，return truereturntrue;}

核心操作：

while (parent)

/-------------第一步：更新新插入节点的父节点的平衡因子-------------/

  • 新插入节点是左子节点 —> 父节点的平衡因子 -1
  • 新插入节点是右子节点 —> 父节点的平衡因子 +1

/-------------第二步：根据父节点的平衡因子做进一步的更新-------------/

  • 情况1：父节点的平衡因子为 0 —> 高度变化未影响上层，结束更新
  • 情况2：父节点的平衡因子为±1 —> 高度变化需向上传递，继续更新上层节点
  • 情况3：父节点的平衡因子为±2 —> 树失衡，需要旋转调整
  • 情况4：非法平衡因子 —> 断言失败
    return true;

旋转操作

旋转的目的
  • 保持搜索树的规则
  • 不平衡的树变成平衡的，其次降低旋转树的高度

旋转总共分为四种：根据不同的不平衡情况我们需要采取不同的旋转方式，这些操作在插入或删除节点导致树失衡时自动触发

  • 左单旋：处理 RR 型失衡
  • 右单旋：处理 LL 型失衡
  • 左右双旋：处理 RL 型失衡
  • 右左双旋：处理 LR 型失衡

需要旋转的情况：父节点的平衡因子为±2 —> 树失衡，需要旋转调整

  • 失衡1：左左失衡（父子平衡因子都为“负”） —> 右单旋
  • 失衡2：右右失衡（父子平衡因子都为“正”） —> 左单旋
  • 失衡3：左右失衡（父为“负”，子为“正”） —> 左右双旋
  • 失衡4：右左失衡（父为“正”，子为“负”） ----> 右左双旋
  • 特殊情况：非法平衡因子 —> 断言失败
一、左单旋
触发条件
  • 左单旋的触发条件：
    • 当AVL树中某个节点的右子树高度比左子树高度大2，且失衡是由右子树的右子树插入节点导致（即右子树的右子树深度增加，称
      为“RR 型失衡”）时，需要通过**左单旋**恢复平衡。
在这里插入图片描述
左单旋原理与核心操作

核心操作：旋转过程分为三步（以节点 60(curNode) 为旋转中心，对parent进行左单旋）

  1. 先处理 curNode 的 left 结点或子树：处理 curLeft 和 parent 的链接关系，注意curLeft可能为空
  2. parent 可能是整棵树的根节点，也可能是某棵树的子树
    • parent 是根节点时：curNode成为整棵树的新根，_parent 指向 nullptr。最后再将parent正确挂载，成为curNode的左子树
    • parent 不是根节点时：需要先保存curNode的祖父结点ppNode，判断parent 是 ppNode 的左孩子还是右孩子，再更改链接关系。最后再将parent正确挂载，成为curNode的左子树
  3. 最后将parent和curNode的平衡因子都更改为0

左单旋原理：

在这里插入图片描述
代码实现
private:// 左单旋 2 1 newNode 练成线，单纯的右边高voidRotateL(Node* parent){if(parent ==nullptr|| parent->_right ==nullptr)return; Node* curNode = parent->_right; Node* curLeft = curNode->_left;// curLeft 有可能为空// 先处理 curNode 的 left 结点，curLeft 有可能是空 parent->_right = curLeft;if(curLeft) curLeft->_parent = parent;// 再处理 curNode 结点// parent 有可能是根节点，也有可能是子树的根节点if(parent == _root){// 先立新根 _root = curNode; curNode->_parent =nullptr;// 再挂旧根 parent->_parent = curNode; curNode->_left = parent;}else{ Node* ppNode = parent->_parent;// 这里不知道 parent 是 ppNode 的 左孩子 还是 右孩子 if(parent == ppNode->_left) ppNode->_left = curNode;else ppNode->_right = curNode; curNode->_parent = ppNode;// 挂 parent parent->_parent = curNode; curNode->_left = parent;} parent->_balanceFactor = curNode->_balanceFactor =0;}
二、右单旋
右单旋可以看做是左单旋的镜像操作
触发条件
  • 右单旋的触发条件：
    • 当AVL树中某个节点的左子树高度比右子树高度大2，且失衡是由左子树的左子树插入节点导致（即右子树的右子树深度增加，称
      为“LL 型失衡”）时，需要通过**右单旋**恢复平衡。
右单旋原理与核心操作

核心操作：旋转过程分为三步（以节点 30(curNode) 为旋转中心，对parent进行右单旋）

  1. 先处理 curNode 的 right 结点或子树：处理 curRight 和 parent 的链接关系，注意curRight可能为空
  2. parent 可能是整棵树的根节点，也可能是某棵树的子树
    • parent 是根节点时：curNode成为整棵树的新根，_parent 指向 nullptr。最后再将parent正确挂载，成为curNode的左子树
    • parent 不是根节点时：需要先保存curNode的祖父结点ppNode，判断parent 是 ppNode 的左孩子还是右孩子，再更改链接关系。最后再将parent正确挂载，成为curNode的右子树
  3. 最后将parent和curNode的平衡因子都更改为0
parent为根节点的情况：
在这里插入图片描述
parent为某棵树的子树的情况：
在这里插入图片描述
代码实现
private:// 右单旋 -2 -1 newNode 连成线，单纯的左边高voidRotateR(Node* parent){// parent 为空 或 curNode 为空的情况if(parent ==nullptr|| parent->_left ==nullptr)return; Node* curNode = parent->_left; Node* curRight = curNode->_right;// 把 curNode 的 right 给给 parent 的 left parent->_left = curRight;if(curRight) curRight->_parent = parent;if(parent == _root){// 先立新根 _root = curNode; curNode->_parent =nullptr;// 再挂旧根 curNode->_right = parent; parent->_parent = curNode;}else{ Node* ppNode = parent->_parent;// 找 parent 是 ppNode 的左还是右if(parent == ppNode->_left) ppNode->_left = curNode;else ppNode->_right = curNode; curNode->_parent = ppNode;// 挂 parent curNode->_right = parent; parent->_parent = curNode;} curNode->_balanceFactor = parent->_balanceFactor =0;}
三、单旋有效与失效的场景
在这里插入图片描述
仅单旋有效的场景总结：

单旋失效场景总结：
在这里插入图片描述
四、双旋的分析
双旋的简单样例
在这里插入图片描述
双旋的本质
在这里插入图片描述
双旋后平衡因子的更新
  • 双旋平衡因子的更新分为三种情况讨论，以下为左右双旋的场景：
在这里插入图片描述
  • 双旋的核心操作不在于旋转，因为双旋只是左单旋和右单旋的简单组合
    • 双旋的核心操作在于旋转后平衡因子的更新
五、左右双旋
触发条件
  • 左右双旋的触发条件：折线的拐角在左边
  • 当 AVL 树中某个节点的左子树高度比右子树高度大 2，且失衡是由左子树的右子树插入节点导致（即左子树的右子树深度增加，称为 “LR 型失衡” ）时，需要通过左右双旋恢复平衡。
  • 左右双旋是 左单旋 + 右单旋 的复合操作，专门处理 LR 型失衡
  • 左右双旋通过 “先左旋修正左子树方向，再右旋整体平衡” 的两步操作，解决 LR 型失衡问题

左右双旋的过程以及平衡因子的更新：

在这里插入图片描述
代码实现

关键操作：

  1. 对cur结点进行左旋
  2. 再对parent结点进行右旋
  3. 最终curRight结点成为树的新根
  4. 旋转完后进行平衡因子的更新
// 左右双旋voidRotateLR(Node* parent){ Node* curNode = parent->_left; Node* curRight = curNode->_right;int bf_curRight = curRight->_balanceFactor;// 旋转RotateL(parent->_left);RotateR(parent);// 双旋 这里的麻烦事 是平衡因子的更新// 更新平衡因子if(bf_curRight ==0)// { parent->_balanceFactor =0; curNode->_balanceFactor =0; curRight->_balanceFactor =0;}elseif(bf_curRight ==1){ parent->_balanceFactor =0; curNode->_balanceFactor =-1; curRight->_balanceFactor =0;}elseif(bf_curRight ==-1){ parent->_balanceFactor =1; curNode->_balanceFactor =0; curRight->_balanceFactor =0;}elseassert(false);}
六、右左双旋
右左双旋可以看做是左右双旋的镜像操作，二者可以看作是一个对称的关系。当插入节点在不平衡节点的右子树的左边时，可以记作右左型 (RL 型)，此时采用右左双旋的方法去调整平衡，即先对不平衡节点的右子树进行一次右单旋，之后再对不平衡节点为根的子树进行一次左单旋。
触发条件
  • 右左双旋的触发条件：折线的拐角在右边
  • 当 AVL 树中某个节点的右子树高度比左子树高度大 2，且失衡是由右子树的左子树插入节点导致（即右子树的左子树深度增加，称为 “RL 型失衡” ）时，需要通过右左双旋恢复平衡。
  • 左双旋是 右单旋 + 左单旋 的复合操作，专门处理RL型失衡
  • 右左双旋通过 “先右旋修正右子树方向，再左旋整体平衡” 的两步操作，解决 RL 型失衡问题

右左双旋的过程以及平衡因子的更新：

在这里插入图片描述
代码实现

关键操作：

  1. 对cur结点进行右旋
  2. 再对parent结点进行左旋
  3. 最终curLeft结点成为树的新根
  4. 旋转完后进行平衡因子的更新
// 右左双旋 parent 的平衡因子为 2 或 -2voidRotateRL(Node* parent){ Node* curNode = parent->_right; Node* curLeft = curNode->_left;int bf_curLeft = curLeft->_balanceFactor;// 旋转RotateR(parent->_right);RotateL(parent);// 双旋 这里的麻烦事 是平衡因子的更新// 更新平衡因子if(bf_curLeft ==0){ parent->_balanceFactor =0; curNode->_balanceFactor =0; curLeft->_balanceFactor =0;}elseif(bf_curLeft ==1){ parent->_balanceFactor =-1; curNode->_balanceFactor =0; curLeft->_balanceFactor =0;}elseif(bf_curLeft ==-1){ parent->_balanceFactor =0; curNode->_balanceFactor =1; curLeft->_balanceFactor =0;}elseassert(false);}

插入的总结与完整代码

总结流程：
  1. 空树处理：树为空时，新节点直接作为根
  2. 查找插入位置：从根出发，**按二叉搜索树规则（小往左、大往右）**找到新节点的父节点 parent，确定挂左还是挂右
  3. 挂载新节点：创建新节点，连接到 parent 的 左 or 右 子树，并维护 parent 指针
  4. 更新平衡因子：从新节点的父节点开始，向上更新路径上所有节点的平衡因子（_balacnFactor），反映子树高度变化
  5. 平衡修复：根据平衡因子判断是否失衡（绝对值 ≥ 2），若失衡则通过旋转操作（单旋 / 双旋）恢复平衡，同时更新旋转后节点的平衡因子
    • 右单旋：处理 LL 型失衡
    • 左单旋：处理 RR 型失衡
    • 左右双旋：处理 RL 型失衡
    • 右左双旋：处理 LR 型失衡
完整插入代码
public:boolinsert(const pair<K, V>& kv){// 先走二叉搜索树的插入逻辑if(_root ==nullptr){ _root =newNode(kv);returntrue;}// _root 不为空时，二叉搜索树的逻辑 Node* parent =nullptr; Node* curNode = _root;// 先找空，找到一个可以插入的位置while(curNode){if(kv.first < curNode->_kv.first){ parent = curNode; curNode = curNode->_left;}elseif(kv.first > curNode->_kv.first){ parent = curNode; curNode = curNode->_right;}// 搜索树中不允许有重复的值 对于已有值，不插入elsereturnfalse;}// while 循环结束后，代表找到了可以插入的位置// 找到位置了，但父节点不知道 新结点比自己大还是比自己小 curNode =newNode(kv);if(curNode->_kv.first < parent->_kv.first){ parent->_left = curNode;}else{ parent->_right = curNode;} curNode->_parent = parent;// 以上是二叉搜索树的插入逻辑，这样插入可能导致树不平衡，从而导致查找效率退化为 O(n)// 以下是AVL树对二叉搜索树 进行的 控制平衡 操作// 控制平衡 ... // 插入后 ，先更新平衡因子// 插入后，最坏情况时: 可能root的平衡因子需要更新，只有root的parent为空while(parent){// 更新平衡因子if(curNode == parent->_left)--parent->_balanceFactor;else// if (curNode == parent->_right)++parent->_balanceFactor;// 当前parent结点更新完了，判断是否还需要再往上更新 // 处理平衡因子更新后有三种情况// 情况一 parent所在子树高度不变且平衡，无需更新 和 旋转 结束循环if(parent->_balanceFactor ==0){break;}// 情况二 parent所在子树高度变了，继续往上更新elseif(parent->_balanceFactor ==1|| parent->_balanceFactor ==-1){ curNode = parent; parent = parent->_parent;}// 情况三 当前子树不平衡了，需要旋转elseif(parent->_balanceFactor ==2|| parent->_balanceFactor ==-2){// 左单旋 “右子树右高”的一种情况// 2 1 newNode 排成直线，单纯的右边高，进行 左单旋// 2 -> 右高，1 -> 右高，右右 左单旋if(parent->_balanceFactor ==2&& curNode->_balanceFactor ==1){RotateL(parent);}// -2 -1 newNode 排成直线，单纯的右边高，进行，右单旋// -2 -> 左高，-1 -> 左高，左左 右单旋elseif(parent->_balanceFactor ==-2&& curNode->_balanceFactor ==-1){RotateR(parent);}// 2 -1 newNode 排成折线 右左双旋elseif(parent->_balanceFactor ==2&& curNode->_balanceFactor ==-1){RotateRL(parent);}// -2 1 newNode 排成折线 左右双旋elseif(parent->_balanceFactor ==-2&& curNode->_balanceFactor ==1){RotateLR(parent);}else{assert(false);}// 旋转后，让这棵树平衡，且降低了这棵树的高度,// 旋转后 就无需再更新平衡因子了，可以跳出循环break;}else{assert(false);// 平衡因子不是 0 1 -1 2 -2 直接报错}}returntrue;}

AVL树的删除

AVL 树的删除操作这里不做重点讲解，这个操作会比插入稍复杂一些，但核心思路依然是走正常的二叉搜索树的删除操作 + 更新平衡因子 + 失衡时进行旋转

只不过与二叉搜索树删除不同的是，删除节点后的平衡因子更新，最差情况下一直要调整到根节点的位置。
具体实现可参考《算法导论》或《数据结构-用面向对象方法与C++描述》殷人昆版

4. 验证操作

求树的高度

求树的高度思路如下：

  • 先分别求树的左右子树高度
  • 最终返回左右子树中 高度更大的高度 + 1
public:intHeight(Node* root){if(root ==nullptr)return0;// 分别求左右子树的高度int leftHeight =Height(root->_left);int rightHeight =Height(root->_right);// 左右子树中 高度更大的那个 + 1return leftHeight > rightHeight ? leftHeight +1: rightHeight +1;}

判断树是否是AVL平衡树

  • 先分别求树的左右子树高度
  • AVL平衡树的条件：
    • 当前树是AVL树：abs(rightHeight - leftHeight) < 2 &&
      • 左右子树也都是AVL树：_IsBalance(root->_left) && _IsBalance(root->_right);
public:// 判断是否是 AVL 树boolisBalance(){return_IsBalance(_root);}private:bool_IsBalance(Node* root){if(root ==nullptr)returntrue;int leftHeight =Height(root->_left);int rightHeight =Height(root->_right);// 加一层保障if(rightHeight - leftHeight != root->_balanceFactor){ cout <<" 平衡因子异常: "<< root->_kv.first <<"->"<< root->_balanceFactor << endl;returnfalse;}returnabs(rightHeight - leftHeight)<2&&_IsBalance(root->_left)&&_IsBalance(root->_right);}

测试 AVL树的正确性

  • 使用 20000000 个随机数测试
voidtest(){constint N =20000000; vector<int> v; v.reserve(N);srand(time(0)); AVLTree<int,int> t;for(size_t i =0; i < N;++i) v.push_back(rand());for(auto e : v) t.insert(make_pair(e, e)); cout << t.isBalance()<< endl;}intmain(){test();return0;}
在这里插入图片描述

4. 完整代码实现

#pragmaonce#include<iostream>#include<assert.h>usingnamespace std;template<classK,classV>structAVLTreeNode{ pair<K, V> _kv;// 键值对// 三叉链 AVLTreeNode<K, V>* _left; AVLTreeNode<K, V>* _right; AVLTreeNode<K, V>* _parent;// 插入结点后，需要更新平衡因子，有了_parent,可以很方便的找父节点// 平衡因子，用于判断当前子树 有没有出现不平衡的问题int _balanceFactor;// balance factor 平衡因子// Node 的构造函数AVLTreeNode(const pair<K, V>& kv):_kv(kv),_left(nullptr),_right(nullptr),_parent(nullptr),_balanceFactor(0)// 新结点 初始的平衡因子为 0{}// 我们使用 平衡因子 = 右子树的高度 - 左子树的高度// AVL 树的实现不是一定需要平衡因子，也可以动态的计算高度来判断// 使用平衡因子实现只是其中一种方式};// 左右子树高度之差的绝对值 小于等于 1 (-1 0 1)template<classK,classV>classAVLTree{typedef AVLTreeNode<K, V> Node;private: AVLTreeNode<K, V>* _root =nullptr;public:boolinsert(const pair<K, V>& kv){// 先走二叉搜索树的插入逻辑if(_root ==nullptr){ _root =newNode(kv);returntrue;}// _root 不为空时，二叉搜索树的逻辑 Node* parent =nullptr; Node* curNode = _root;// 先找空，找到一个可以插入的位置while(curNode){if(kv.first < curNode->_kv.first){ parent = curNode; curNode = curNode->_left;}elseif(kv.first > curNode->_kv.first){ parent = curNode; curNode = curNode->_right;}// 搜索树中不允许有重复的值 对于已有值，不插入elsereturnfalse;}// while 循环结束后，代表找到了可以插入的位置// 找到位置了，但父节点不知道 新结点比自己大还是比自己小 curNode =newNode(kv);if(curNode->_kv.first < parent->_kv.first){ parent->_left = curNode;}else{ parent->_right = curNode;} curNode->_parent = parent;// 以上是二叉搜索树的插入逻辑，这样插入可能导致树不平衡，从而导致查找效率退化为 O(n)// 以下是AVL树对二叉搜索树 进行的 控制平衡 操作// 控制平衡 ... // 插入后 ，先更新平衡因子// 插入后，最坏情况时: 可能root的平衡因子需要更新，只有root的parent为空while(parent){// 更新平衡因子if(curNode == parent->_left)--parent->_balanceFactor;else// if (curNode == parent->_right)++parent->_balanceFactor;// 当前parent结点更新完了，判断是否还需要再往上更新 // 处理平衡因子更新后有三种情况// 情况一 parent所在子树高度不变且平衡，无需更新 和 旋转 结束循环if(parent->_balanceFactor ==0){break;}// 情况二 parent所在子树高度变了，继续往上更新elseif(parent->_balanceFactor ==1|| parent->_balanceFactor ==-1){ curNode = parent; parent = parent->_parent;}// 情况三 当前子树不平衡了，需要旋转elseif(parent->_balanceFactor ==2|| parent->_balanceFactor ==-2){// 左单旋 “右子树右高”的一种情况// 2 1 newNode 排成直线，单纯的右边高，进行 左单旋// 2 -> 右高，1 -> 右高，右右 左单旋if(parent->_balanceFactor ==2&& curNode->_balanceFactor ==1){RotateL(parent);}// -2 -1 newNode 排成直线，单纯的右边高，进行，右单旋// -2 -> 左高，-1 -> 左高，左左 右单旋elseif(parent->_balanceFactor ==-2&& curNode->_balanceFactor ==-1){RotateR(parent);}// 2 -1 newNode 排成折线 右左双旋elseif(parent->_balanceFactor ==2&& curNode->_balanceFactor ==-1){RotateRL(parent);}// -2 1 newNode 排成折线 左右双旋elseif(parent->_balanceFactor ==-2&& curNode->_balanceFactor ==1){RotateLR(parent);}else{assert(false);}// 旋转后，让这棵树平衡，且降低了这棵树的高度,// 旋转后 就无需再更新平衡因子了，可以跳出循环break;}else{assert(false);// 平衡因子不是 0 1 -1 2 -2 直接报错}}returntrue;}// 判断是否是 AVL 树boolisBalance(){return_IsBalance(_root);}private:bool_IsBalance(Node* root){if(root ==nullptr)returntrue;int leftHeight =Height(root->_left);int rightHeight =Height(root->_right);// 加一层保障if(rightHeight - leftHeight != root->_balanceFactor){ cout <<" 平衡因子异常: "<< root->_kv.first <<"->"<< root->_balanceFactor << endl;returnfalse;}returnabs(rightHeight - leftHeight)<2&&_IsBalance(root->_left)&&_IsBalance(root->_right);}intHeight(Node* root){if(root ==nullptr)return0;// 分别求左右子树的高度int leftHeight =Height(root->_left);int rightHeight =Height(root->_right);// 左右子树中 高度更大的那个 + 1return leftHeight > rightHeight ? leftHeight +1: rightHeight +1;}// 左单旋 复习版voidRotateL_review(Node* parent){if(parent ==nullptr|| parent->_right ==nullptr)return; Node* curNode = parent->_right; Node* curLeft = curNode->_left; parent->_right = curLeft;if(curLeft)// curLeft 可能为空 curLeft->_parent = parent;// parent 可能是根节点，也可能是一颗子树if(parent == _root){// 先立新根 _root = curNode; curNode->_parent =nullptr;// 再挂旧根 parent->_parent = curNode; curNode->_left = parent;}else{ Node* ppNode = parent->_parent;// 先立新根// 这里不知道 parent 是 ppNode 的左 还是右if(parent == ppNode->_left) ppNode->_left = curNode;else ppNode->_right = curNode; curNode->_parent = ppNode;// 再挂parent parent->_parent = curNode; curNode->_left = parent;} parent->_balanceFactor = curNode->_balanceFactor =0;}// 左单旋 2 1 newNode 练成线，单纯的右边高voidRotateL(Node* parent){if(parent ==nullptr|| parent->_right ==nullptr)return; Node* curNode = parent->_right; Node* curLeft = curNode->_left;// curLeft 有可能为空// 先处理 curNode 的 left 结点，curLeft 有可能是空 parent->_right = curLeft;if(curLeft) curLeft->_parent = parent;// 再处理 curNode 结点// parent 有可能是根节点，也有可能是子树的根节点if(parent == _root){// 先立新根 _root = curNode; curNode->_parent =nullptr;// 再挂旧根 parent->_parent = curNode; curNode->_left = parent;}else{ Node* ppNode = parent->_parent;// 这里不知道 parent 是 ppNode 的 左孩子 还是 右孩子 if(parent == ppNode->_left) ppNode->_left = curNode;else ppNode->_right = curNode; curNode->_parent = ppNode;// 挂 parent parent->_parent = curNode; curNode->_left = parent;} parent->_balanceFactor = curNode->_balanceFactor =0;}// 右单旋 -2 -1 newNode 连成线，单纯的左边高voidRotateR(Node* parent){// parent 为空 或 curNode 为空的情况if(parent ==nullptr|| parent->_left ==nullptr)return; Node* curNode = parent->_left; Node* curRight = curNode->_right;// 把 curNode 的 right 给给 parent 的 left parent->_left = curRight;if(curRight) curRight->_parent = parent;if(parent == _root){// 先立新根 _root = curNode; curNode->_parent =nullptr;// 再挂旧根 curNode->_right = parent; parent->_parent = curNode;}else{ Node* ppNode = parent->_parent;// 找 parent 是 ppNode 的左还是右if(parent == ppNode->_left) ppNode->_left = curNode;else ppNode->_right = curNode; curNode->_parent = ppNode;// 挂 parent curNode->_right = parent; parent->_parent = curNode;} curNode->_balanceFactor = parent->_balanceFactor =0;}// 右左双旋 parent 的平衡因子为 2 或 -2voidRotateRL(Node* parent){ Node* curNode = parent->_right; Node* curLeft = curNode->_left;int bf_curLeft = curLeft->_balanceFactor;// 旋转RotateR(parent->_right);RotateL(parent);// 双旋 这里的麻烦事 是平衡因子的更新// 更新平衡因子if(bf_curLeft ==0){ parent->_balanceFactor =0; curNode->_balanceFactor =0; curLeft->_balanceFactor =0;}elseif(bf_curLeft ==1){ parent->_balanceFactor =-1; curNode->_balanceFactor =0; curLeft->_balanceFactor =0;}elseif(bf_curLeft ==-1){ parent->_balanceFactor =0; curNode->_balanceFactor =1; curLeft->_balanceFactor =0;}elseassert(false);}// 左右双旋voidRotateLR(Node* parent){ Node* curNode = parent->_left; Node* curRight = curNode->_right;int bf_curRight = curRight->_balanceFactor;// 旋转RotateL(parent->_left);RotateR(parent);// 双旋 这里的麻烦事 是平衡因子的更新// 更新平衡因子if(bf_curRight ==0)// { parent->_balanceFactor =0; curNode->_balanceFactor =0; curRight->_balanceFactor =0;}elseif(bf_curRight ==1){ parent->_balanceFactor =0; curNode->_balanceFactor =-1; curRight->_balanceFactor =0;}elseif(bf_curRight ==-1){ parent->_balanceFactor =1; curNode->_balanceFactor =0; curRight->_balanceFactor =0;}elseassert(false);}};

5. 结语

从最初的二叉搜索树到 AVL 树，我们一步步地走完了“从失衡到平衡”的进化历程。
AVL 树通过平衡因子 + 旋转操作巧妙地在插入、删除之间保持树的高度稳定，让查找性能始终维持在对数级别。

它是现代平衡树结构（如红黑树、Treap、B 树等）的理论基石，也让我们深刻理解了“以空间换时间”、“以维护换性能”的设计哲学。
虽然 AVL 树在插入删除时的维护成本略高，但在查找密集的场景中，它的稳定性与高效性仍然无可替代。

希望这篇文章能帮助你彻底理解平衡二叉树的核心思想，为你后续深入学习红黑树、STL map/set 底层实现打下坚实的基础。

以上就是本文的所有内容了，如果觉得文章对你有帮助，欢迎 点赞⭐收藏 支持！如有疑问或建议，请在评论区留言交流，我们一起进步

分享到此结束啦
一键三连，好运连连！你的每一次互动，都是对作者最大的鼓励！征程尚未结束，让我们在广阔的世界里继续前行！ 🚀

Read more

诺奖得主辛顿最新访谈：1 万个 AI 可以瞬间共享同一份“灵魂”，这就是为什么人类注定被超越

诺奖得主辛顿最新访谈：1 万个 AI 可以瞬间共享同一份“灵魂”，这就是为什么人类注定被超越

当宇宙级的“嘴炮”遇到降维打击。 编译 | 王启隆 来源 | youtu.be/l6ZcFa8pybE 出品丨AI 科技大本营（ID：rgznai100） 打开最新一期知名播客 StarTalk 的 YouTube 评论区，最高赞的一条留言是这样写的： “我长这么大，第一次看到尼尔·德葛司·泰森（Neil deGrasse Tyson）在一档节目里几乎全程闭嘴，像个手足无措的小学生一样乖乖听讲。” 作为全美最知名的天体物理学家，泰森平时的画风是充满激情、喋喋不休、用宇宙的宏大来震撼嘉宾。但这一次，坐在他对面的那位满头银发、带着温和英音的英国老人，仅仅用最平淡的语气，就让整个演播室陷入了数次令人窒息的沉默。 这位老人是 Geoffrey Hinton。深度学习三巨头之一，2024 年诺贝尔物理学奖得主，被公认为“AI 教父”。 对经常阅读 Hinton 演讲的我来说，这也是比较新奇的一幕—

By Ne0inhk
48小时“烧光”56万！三人创业团队濒临破产，仅因Gemini API密钥被盗：“AI账单远超我们的银行余额”

48小时“烧光”56万！三人创业团队濒临破产，仅因Gemini API密钥被盗：“AI账单远超我们的银行余额”

整理 | 苏宓 出品 | ZEEKLOG（ID：ZEEKLOGnews） 「仅过了 48 小时，一笔 8.2 万美元的天价费用凭空出现，较这家小型初创公司的正常月费暴涨近 46000%。」 这不是假设的虚幻故事，而是一家墨西哥初创公司正在经历的真实危机。 近日，一位名为 RatonVaquero 的开发者在 Reddit 发帖求助称，由于他的 Gemini API 密钥被盗用，原本每月仅约 180 美元（约 1242 元）的费用，在短短 48 小时内暴涨到 82,314.44 美元（约 56.8 万元）。对于这家只有三名开发者的小型创业团队来说，这笔突如其来的账单，几乎等同于灭顶之灾。 “我现在整个人都处在震惊和恐慌之中。”RatonVaquero

By Ne0inhk
假网站排全网第二，真官网翻五页都找不到！NanoClaw创始人破防：SEO之战，我快要输了

假网站排全网第二，真官网翻五页都找不到！NanoClaw创始人破防：SEO之战，我快要输了

整理 | 苏宓 出品 | ZEEKLOG（ID：ZEEKLOGnews） 自从 OpenClaw 爆火之后，各种“Claw”项目接连出现，其中以安全优化版 NanoClaw 最为知名。它的核心代码仅有 4000 行，却获得了 AI 大牛 Andrej Karpathy 的点赞。 可谁也没想到，这款口碑极佳的开源项目，近来竟被一个仿冒网站抢了风头。 投诉无门之下，NanoClaw 创始人 Gavriel Cohen 在 X 社交平台上无奈发文怒斥：谷歌搜索错误地将假网站排在真官网前面，不仅破坏了项目声誉，还埋下了严重的安全隐患，而他费尽心力，却只能哀叹一句——“我正在为自己的开源项目打 SEO 战，但我快要输了。” 那么，NanoClaw 究竟发生了什么？又是怎么走红的？事情还要从 OpenClaw

By Ne0inhk
曝Windows 12将于今年发布？以AI为核心、NPU成「硬件门槛」，网友吐槽：“不想要的全塞进来了”

曝Windows 12将于今年发布？以AI为核心、NPU成「硬件门槛」，网友吐槽：“不想要的全塞进来了”

整理 | 郑丽媛 出品 | ZEEKLOG（ID：ZEEKLOGnews） 当年，微软一句“Windows 10 将是最后一个版本”的表态，让不少用户以为 Windows 进入了“只更新、不换代”的时代。但几年过去，现实却完全不同。 在 Windows 11 发布之后，如今关于 Windows 12 的传闻再次密集出现。从内部代号、代码片段，到硬件厂商的暗示与 OEM 预热标签，种种线索拼在一起，勾勒出一个明显的趋势——这不会只是一次常规升级，而更像是一次围绕 AI 的平台级重构。 更关键的是，这次争议，可能远比当年 TPM 2.0 更大。 精准卡位 Windows 10 退场的时间？

By Ne0inhk