【高阶数据结构】AVL树：从原理到旋转平衡艺术（附完整代码）

Ne0inhk

— 17 min read
【高阶数据结构】AVL树：从原理到旋转平衡艺术（附完整代码）
🔥拾Ծ光：个人主页👨🏻‍💻

👏👏👏欢迎来到我的专栏:

🎉《C++》

📌《数据结构》

💡《C语言》

🚀《Linux》

前言：

AVL树，又称平衡二叉搜索树，即AVL树是基于二叉搜索树实现的。

如果你对二叉搜索树的结构还不太熟悉，看看这个呢👇️👇️👇️

【数据结构】二叉搜索树C++实现：增删查改全攻略

为什么我们有二叉搜索树还要实现AVL树这样的数据结构呢？原因就是，二叉搜索树当数据有序时或者接近有序时，其结构就会退化为单支或趋近与单支给结构，此时时间复杂度为O(N)。

所以，就出现了AVL树这种更稳定的高效数据结构。因为，AVL树可以在插入数据的同时，可以保持其左右子树的平衡，所以AVL树的高度始终保持 logN，即时间复杂度为O(logN)。

小知识：AVL树得名于它的发明者G. M. Adelson-Velsky和E. M. Landis是两个前苏联的科学家，他们在1962 年的论文《An algorithm for the organization of information》中发表了它。

一、AVL树的概念与性质

AVL树即对于任意结点的左右子树高度差不超过1，这里我们再引入一个概念：平衡因子((balance factor)，每个节点都有一个平衡因子，其值等于该节点的左右子树的高度差（右子树高度 - 左子树高度），所以，AVL树任意节点的平衡因子取值为0/-1/1。

AVL树性质如下：

1、AVL树可以是空树；

2、AVL树的左右子树仍为AVL树；

3、AVL树任意节点的左右子树高度差不超过1（即 -1<= 平衡因子 <=1）

如图所示：

二、AVL树的节点结构

对于AVL树的节点，根据前面对二叉搜索树的学习，节点中肯定要有一个left指针指向左孩子节点，right指针指向右孩子节点，用一个pair类来存储key（键值）和value（映射值）。

还需要用一个变量来存储上面提到的平衡因子，平衡因子可以帮我们快速地判断当前节点的左右子树高度是否平衡，当平衡因子等于2或-2时，即平衡被破坏。

此外，当我们再调整平衡的过程中需要频繁的访问节点的父亲节点，所以，还需要一个记录父亲节点的指针，即AVL树的结构为一个三叉链的结构，每个节点同时指向其左孩子，右孩子与父亲节点。

说明：我们选择实现key_value类型且数据不冗余（即数据不重复）。

节点结构定义如下：

template<class K,class V> struct AVLTreeNode { pair<K, V> _kv; // 存储键值key与映射值value AVLTreeNode<K, V>* _left; // 指向左孩子节点 AVLTreeNode<K, V>* _right; // 指向右孩子节点 AVLTreeNode<K, V>* _parent; // 指向父亲节点的指针 int _bf; // 记录平衡因子 // 构造 AVLTreeNode(const pair<K, V>& kv) :_kv(kv) ,_left(nullptr) ,_right(nullptr) ,_parent(nullptr) ,_bf(0) {} };

三、AVL树的插入

AVL树插入节点时，遵循二叉搜索树的规则，即大的往右走，小的往左走。不同的是：当插入节点之后，如果不满足平衡要求，就需要调整数的结构使其任意节点的左右子树高度差不超过1。具体插入节点有以下四种情况：

前两种为：由于节点已经有一个左孩子或者右孩子，所以，插入新节点后高度不发生变化，即树结构的平衡不会被破坏，因此，不需要处理。

后两种为：新节点的父亲节点的左右孩子为空，插入新节点后高度改变，此时如果parent为空，即8为根结点，结构满足平衡条件，就不需要处理；如果parent不为空，那么平衡就有可能被破坏，我们需要向上更新平衡因子来进一步判断，具体又需要分情况讨论。

•  更新到10结点，平衡因子为2，10所在的子树已经不平衡，需要旋转处理

•  更新到中间结点，3为根的子树高度不变，不会影响上一层，更新结束

•  最坏更新到根停止

分析到这里，插入新节点的大概的代码框架我们就可以先搭建起来了，然后，对于需要旋转调整的情况，我们再封装函数来处理。

template<class K,class V> class AVLTree { typedef AVLTreeNode<K, V> Node; public: bool insert(const pair<K, V>& kv) { // 处理空树 if (_root == nullptr) { _root = new Node(kv); return true; } Node* cur = _root; Node* parent = nullptr; // 根据二叉搜索树规则查找新节点插入位置 while (cur) { if (kv.first > cur->_kv.first) { parent = cur; cur = cur->_right; } else if (kv.first < cur->_kv.first) { parent = cur; cur = cur->_left; } else { return false; } } // 插入 cur = new Node(kv); if (kv.first < parent->_kv.first) { parent->_left = cur; } else { parent->_right = cur; } // 链接父亲节点（三叉链） cur->_parent = parent; // 调整平衡因子 while (parent) { if (cur == parent->_left) { parent->_bf--; // 左边插入节点，平衡因子-- } else { parent->_bf++; // 右边插入节点，平衡因子++ } // 父亲节点平衡因子为0，即前两种情况（不需要处理） if (parent->_bf == 0) { break; } // 后两种情况，需要进行向上调整平衡因子 else if (parent->_bf == 1 || parent->_bf == -1) { cur = parent; parent = parent->_parent; } // 当平衡因子为2或-2时，平衡被破坏，开始旋转调整平衡 else if (parent->_bf == 2 || parent->_bf == -2) { // 旋转调整平衡 // ... break; } // 多加一个判断，提高程序的健壮性 else { assert(false); } } return true; } private: Node* _root = nullptr; };

四、AVL树的旋转平衡

4.1、右单旋

对于我们上面提到的后两种情况，我们将AVL树的结构抽象为下图所示，当我们插入节点后，在平衡因子向上更新的过程中，parent节点的平衡因子变成了-2，平衡被破坏，此时SubL节点的平衡因子为-1，即最左边一条路径的高度大于右边，对于这种情况就需要右旋。

即我们需要让parent的_left 指向SubLR，SubL的_right 指向parent，SubL成为子树的根结点，注意链接彼此的父亲节点（即 _parent的指向）。

有以下四点需要注意：

• 若parent为根结点，由于旋转后根结点变为SubL，则需要更新_root，且根结点的_parent指针为空。

• parent不是根结点，需要记下parent的父亲节点pParent，防止在SubL链接时找不到对应的父亲节点。且链接时需要注意，原来是pParent 的 _left指向parent，还是_right指向parent。

• SubLR 节点可能为空，若SubLR为空，则不需要SubLR节点链接parent节点，防止对空指针解引用操作。

• 当旋转平衡之后，需要更新parent和SubL 的平衡因子，AVL旋转后平衡则SubL的平衡因子为0，且parent的平衡因子也为0（画图可知）。

代码实现如下：

void RotateR(Node* parent) { Node* SubL = parent->_left; Node* SubLR = SubL->_right; Node* pParent = parent->_parent; // 记下parent的父亲节点 // 旋转（右） parent->_left = SubLR; if (SubLR) // 处理SubLR为空的情况 { SubLR->_parent = parent; // SubLR不为空才链接父亲节点 } SubL->_right = parent; parent->_parent = SubL; // 链接SubL与parent的父亲节点 if (parent == _root) // 处理parent为根结点的情况 { _root = SubL; // 更新根结点的值 SubL->_parent = nullptr; } else { if (parent == pParent->_left) { pParent->_left = SubL; } else { pParent->_right = SubL; } SubL->_parent = pParent; } // 更新平衡因子 SubL->_bf = 0; parent->_bf = 0; }

4.2、左单旋

在平衡因子向上更新的过程中，parent节点的平衡因子变成了 2，平衡被破坏，此时SubR节点的平衡因子为 1，即最右边一条路径的高度大于左边，对于这种情况就需要左旋。

即需要让parent的 _right指向SubRL，让SubR的 _left 指向parent，SubR成为子树的根结点，注意链接彼此的父亲节点（即 _parent的指向）。

代码实现如下（与右单旋完全类似）：

void RotateL(Node* parent) { Node* SubR = parent->_right; Node* SubRL = SubR->_left; Node* pParent = parent->_parent; // 旋转（左） parent->_right = SubRL; if (SubRL) { SubRL->_parent = parent; // SubRL不为空才链接父亲节点 } SubR->_left = parent; parent->_parent = SubR; // 链接SubR与parent的父亲节点 if (parent == _root) // 处理为根结点的情况 { _root = SubR; SubR->_parent = nullptr; } else { if (parent == pParent->_left) { pParent->_left = SubR; } else { pParent->_right = SubR; } SubR->_parent = pParent; } // 更新平衡因子 parent->_bf = SubR->_bf = 0; }

4.3、左右双旋

通过观察，不难发现，上面的单旋无非就是最左边一条路径的高度或最右边一条路径的高度破坏了平衡，即一个方向上插入导致高度不满足平衡。相反，双旋则是在不同方向插入节点导致的高度不平衡，此时，parent的平衡因子为 -2，SubL 的平衡因子为 1

这里比较麻烦的是，更新平衡因子分为三种情况：

情况一：新节点为SubLR的左孩子

💦SubL的平衡因子为 0，SubLR的平衡因子为0，parent的平衡因子为1。

情况二：新节点为SubLR 的右孩子

💦SubL的平衡因子为-1，SubLR的平衡因子为0，parent的平衡因子为0。

情况三：SubLR为新节点

💦SubL的平衡因子为0，SubLR的平衡因子为0，parent的平衡因子为0。

代码实现如下：

void RotateLR(Node* parent) { Node* SubL = parent->_left; Node* SubLR = SubL->_right; // 记下SubLR的平衡因子用来区分更新平衡因子的不同情况 int flag = SubLR->_bf; RotateL(SubL); // 先左旋 RotateR(parent); // 后右旋 // 更新平衡因子 if (flag == -1) { parent->_bf = 1; SubL->_bf = 0; SubLR = 0; } else if (flag == 1) { parent->_bf = 0; SubL->_bf = -1; SubLR = 0; } else { parent->_bf = 0; SubL->_bf = 0; SubLR = 0; } }

4.4、右左双旋

右左双旋不同于左右双旋的就是：parent的平衡因子为 2，SubL 的平衡因子为 -1。

更新平衡因子也分为三种情况：

情况一：新节点为SubRL 的左孩子（即SubRL 的平衡因子为 -1）

parent的平衡因子更新为 0，SubR 的平衡因子更新为1，SubRL 的平衡因子更新为0。

情况二：新节点为SubRL 的右孩子（即SubRL 的平衡因子为 1）

parent的平衡因子更新为 -1，SubR 的平衡因子更新为0，SubRL 的平衡因子更新为0。

情况三：新节点为SubRL（即SubRL 的平衡因子为0）

parent的平衡因子更新为 0，SubR 的平衡因子更新为0，SubRL 的平衡因子更新为0。

代码实现如下：

void RotateRL(Node* parent) { Node* SubR = parent->_right; Node* SubRL = SubR->_left; // 记下SubRL的平衡因子用来区分更新平衡因子的不同情况 int flag = SubRL->_bf; RotateR(SubR); RotateL(parent); // 更新平衡因子 if (flag == -1) { parent->_bf = 0; SubR->_bf = 1; SubRL->_bf = 0; } else if (flag == 1) { parent->_bf = -1; SubR->_bf = 0; SubRL->_bf = 0; } else { parent->_bf = 0; SubR->_bf = 0; SubRL->_bf = 0; } }

五、其他接口实现

5.1、中序遍历

void _InOrder(Node* root) { if (root == nullptr) { return; } _InOrder(root->_left); cout << root->_kv.first << ": " << root->_kv.second << endl; _InOrder(root->_right); }

5.2、AVL树的高度

size_t _Height(Node* root) { if (root == nullptr) { return 0; } int heightleft = _Height(root->_left); int heightright = _Height(root->_right); return heightleft > heightright ? heightleft + 1 : heightright + 1; // 需要加上根结点高度1 }

5.3、判断平衡

bool _IsBalanceTree(Node* root) { if (root == nullptr) { return true; } int leftheight = _Height(root->_left); int rightheight = _Height(root->_right); int bf = rightheight - leftheight; // 右子树高度 - 左子树高度 if (abs(bf) >= 2) { cout << "高度异常" << endl; return false; } if(root->_bf != bf) { cout << "平衡因子异常" << endl; return false; } return _IsBalanceTree(root->_left) && _IsBalanceTree(root->_right); }

5.4、节点个数

size_t _size(Node* root) { if (root == nullptr) { return 0; } return _size(root->_left) + _size(root->_right) + 1; }

5.5、查找

Node* find(const K& key) { Node* cur = _root; while (cur) { if (cur->_kv.first > key) { cur = cur->_left; } else if (cur->_kv.first < key) { cur = cur->_right; } else { return cur; } } return nullptr; }

六、完整代码

头文件：AVLTree.h

#include<iostream> #include<assert.h> #include<vector> using namespace std; template<class K,class V> struct AVLTreeNode { pair<K, V> _kv; // 存储键值与映射值 AVLTreeNode<K, V>* _left; // 指向左孩子节点 AVLTreeNode<K, V>* _right; // 指向右孩子节点 AVLTreeNode<K, V>* _parent; // 指向父亲节点的指针 int _bf; // 记录平衡因子 // 构造 AVLTreeNode(const pair<K, V>& kv) :_kv(kv) ,_left(nullptr) ,_right(nullptr) ,_parent(nullptr) ,_bf(0) {} }; template<class K,class V> class AVLTree { typedef AVLTreeNode<K, V> Node; public: bool Insert(const pair<K, V>& kv) { // 处理空树 if (_root == nullptr) { _root = new Node(kv); return true; } Node* cur = _root; Node* parent = nullptr; // 根据二叉搜索树规则查找新节点插入位置 while (cur) { if (kv.first > cur->_kv.first) { parent = cur; cur = cur->_right; } else if (kv.first < cur->_kv.first) { parent = cur; cur = cur->_left; } else { return false; } } // 插入 cur = new Node(kv); if (kv.first < parent->_kv.first) { parent->_left = cur; } else { parent->_right = cur; } // 链接父亲节点（三叉链） cur->_parent = parent; // 调整平衡因子 while (parent) { if (cur == parent->_left) { parent->_bf--; // 左边插入节点，平衡因子-- } else { parent->_bf++; // 右边插入节点，平衡因子++ } // 父亲节点平衡因子为0，即前两种情况（不需要处理） if (parent->_bf == 0) { break; } // 后两种情况，需要进行向上调整平衡因子 else if (parent->_bf == 1 || parent->_bf == -1) { cur = parent; parent = parent->_parent; } // 当平衡因子为2或-2时，平衡被破坏，开始旋转调整平衡 else if (parent->_bf == 2 || parent->_bf == -2) { // 旋转调整平衡 if (parent->_bf == -2 && cur->_bf == -1) { RotateR(parent); } else if (parent->_bf == 2 && cur->_bf == 1) { RotateL(parent); } else if (parent->_bf == -2 && cur->_bf == 1) { RotateLR(parent); } else if (parent->_bf == 2 && cur->_bf == -1) { RotateRL(parent); } else { assert(false); } break; } // 多加一个判断，提高程序的健壮性 else { assert(false); } } return true; } void RotateR(Node* parent) { Node* SubL = parent->_left; Node* SubLR = SubL->_right; Node* pParent = parent->_parent; parent->_left = SubLR; if (SubLR) // 处理SubLR为空的情况 { SubLR->_parent = parent; } SubL->_right = parent; parent->_parent = SubL; // 处理parent为根结点的情况 if (parent == _root) { _root = SubL; SubL->_parent = nullptr; } else { if (parent == pParent->_left) { pParent->_left = SubL; } else { pParent->_right = SubL; } SubL->_parent = pParent; } // 更新平衡因子 SubL->_bf = 0; parent->_bf = 0; } void RotateL(Node* parent) { Node* SubR = parent->_right; Node* SubRL = SubR->_left; Node* pParent = parent->_parent; parent->_right = SubRL; if (SubRL) { SubRL->_parent = parent; } SubR->_left = parent; parent->_parent = SubR; if (parent == _root) { _root = SubR; SubR->_parent = nullptr; } else { if (parent == pParent->_left) { pParent->_left = SubR; } else { pParent->_right = SubR; } SubR->_parent = pParent; } // 更新平衡因子 parent->_bf = SubR->_bf = 0; } void RotateLR(Node* parent) { Node* SubL = parent->_left; Node* SubLR = SubL->_right; // 记下SubLR的平衡因子用来区分更新平衡因子的不同情况 int flag = SubLR->_bf; RotateL(parent->_left); // 先左旋 RotateR(parent); // 后右旋 // 更新平衡因子 if (flag == -1) { parent->_bf = 1; SubL->_bf = 0; SubLR = 0; } else if (flag == 1) { parent->_bf = 0; SubL->_bf = -1; SubLR = 0; } else { parent->_bf = 0; SubL->_bf = 0; SubLR = 0; } } void RotateRL(Node* parent) { Node* SubR = parent->_right; Node* SubRL = SubR->_left; // 记下SubRL的平衡因子用来区分更新平衡因子的不同情况 int flag = SubRL->_bf; RotateR(SubR); RotateL(parent); // 更新平衡因子 if (flag == -1) { parent->_bf = 0; SubR->_bf = 1; SubRL->_bf = 0; } else if (flag == 1) { parent->_bf = -1; SubR->_bf = 0; SubRL->_bf = 0; } else { parent->_bf = 0; SubR->_bf = 0; SubRL->_bf = 0; } } void InOrder() { _InOrder(_root); } size_t size() { return _size(_root); } size_t Height() { return _Height(_root); } Node* find(const K& key) { Node* cur = _root; while (cur) { if (cur->_kv.first > key) { cur = cur->_left; } else if (cur->_kv.first < key) { cur = cur->_right; } else { return cur; } } return nullptr; } bool IsBalanceTree() { return _IsBalanceTree(_root); } private: void _InOrder(Node* root) { if (root == nullptr) { return; } _InOrder(root->_left); cout << root->_kv.first << ": " << root->_kv.second << endl; _InOrder(root->_right); } size_t _size(Node* root) { if (root == nullptr) { return 0; } return _size(root->_left) + _size(root->_right) + 1; } size_t _Height(Node* root) { if (root == nullptr) { return 0; } int heightleft = _Height(root->_left); int heightright = _Height(root->_right); return heightleft > heightright ? heightleft + 1 : heightright + 1; // 需要加上根结点高度1 } bool _IsBalanceTree(Node* root) { if (root == nullptr) { return true; } int leftheight = _Height(root->_left); int rightheight = _Height(root->_right); int bf = rightheight - leftheight; // 右子树高度 - 左子树高度 if (abs(bf) >= 2) { cout << "高度异常" << endl; return false; } if(root->_bf != bf) { cout << "平衡因子异常" << endl; return false; } return _IsBalanceTree(root->_left) && _IsBalanceTree(root->_right); } private: Node* _root = nullptr; };

测试：test.cpp

#include"AVLTree.h" void test01() { vector<int> R({ 10,12,7,5,8,4,3 }); vector<int> L({ 10,15,6,20,14,25 }); vector<int> vv({ 16, 3, 7, 11, 9, 26, 18, 14, 15 }); AVLTree<int, int> tree; for (auto e : vv) { tree.Insert(make_pair(e, e)); } tree.InOrder(); tree.Height(); if (tree.IsBalanceTree()) { cout << "平衡" << endl; } } int main() { test01(); return 0; }

Read more

GitHub 44K 星！Skills：开源「智能体技能库」+ 手搓创建技能

2026年，AI的战场已从“回答问题”转向“完成任务”。 你是否想过： ✅ 能否让AI自动分析GitHub仓库并提交PR？ ✅ 能否让AI读完一篇论文后，自动生成PPT并邮件发送给团队？ ✅ 能否让AI在发现线上Bug后，自动回滚版本并通知运维？ 这些不再是幻想—— 一个名为 Skills 的开源项目，正在让AI智能体（Agent）真正拥有“做事”的能力 。 此仓库包含Anthropic为Claude实现的技能。 截至2026年1月，该项目已在GitHub收获 44,000+ Stars ，被Hugging Face、LangChain、LlamaIndex等主流框架深度集成，被誉为 “AI智能体的操作系统级技能库” 。 今天，我们就来揭开它的神秘面纱。  什么是Skills？ Skills （全名： ）是一个 开放、模块化、可组合的智能体技能仓库 。 它的核心理念很简单： “不要让AI从零开始学做事，而是给它一套标准化的‘技能工具箱’。” 就像人类通过学习“开车”“做饭”“写代码”来完成复杂任务，

By Ne0inhk

git2.53.0安装步骤

⭐ 一、安装（核心选项直接抄） 安装界面选择建议核心原因组件选择✅ 保留默认勾选，取消 Check daily for updates自动更新没必要，核心功能够用默认编辑器✅ 选 Use Visual Studio Code as Git's default editor避免 Vim 学习成本，和开发工具统一初始分支名✅ 选 Override，分支名填 main适配 GitHub/Gitee 主流规范PATH 配置✅ 选 Git from the command line and also from 3rd-party software多终端可用（Git Bash/CMD/VSCode）SSH 客户端✅

By Ne0inhk
GitHub访问加速全攻略：开发者必备的5种提速方案（亲测有效）!!!

GitHub访问加速全攻略：开发者必备的5种提速方案（亲测有效）!!!

文章目录 * 一、为什么GitHub这么慢？（先搞懂原理） * 1.1 网络延迟的罪魁祸首 * 1.2 DNS污染问题 * 二、5大加速方案实测对比（附详细步骤） * 2.1 镜像站大法（新手首选） * 2.2 修改Hosts文件（永久生效） * 2.3 Git配置代理（程序员必备） * 2.4 使用Gitee中转（适合大项目） * 2.5 终极方案：GitHub加速器（黑科技） * 三、避坑指南（血泪经验） * 3.1 不要用盗版加速器！ * 3.2 SSH连接比HTTPS更快 * 3.3 大文件用Git LFS * 四、速度测试对比（单位：

By Ne0inhk
GitHub介绍指南

GitHub介绍指南

作为程序员，GitHub 绝对是日常开发、技术成长、团队协作的核心工具——它不只是“代码仓库”，更是全球1亿+开发者的技术生态枢纽，从个人项目管理到大型团队协作，从开源学习到职场背书，吃透它能大幅提升开发效率、拓宽技术视野，是程序员不可或缺的“刚需装备”。 一、先厘清关键：GitHub ≠ Git（避免踩坑）        很多开发者初期会混淆两者，用两个通俗比喻就能快速区分，核心关系一句话概括：Git 负责“本地记录”，GitHub 负责“云端共享”： * Git：你本地电脑的“代码版本管理工具”（软件），无需联网，核心作用是记录代码每一次修改、管理分支、一键回退版本，相当于你私人的“代码日记本”，解决“改崩代码回不去”“多个最终版文件夹混乱”的痛点。 * GitHub：基于 Git 搭建的在线平台（网站），需联网使用，核心是将本地

By Ne0inhk