【高阶数据结构】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

Neo4j 知识讲解与在线工具使用教程

图数据库领域的核心工具 ——Neo4j，同时详细拆解其在线预览控制台（https://console-preview.neo4j.io/）的使用方法，以及查询工具（https://console-preview.neo4j.io/tools/query）的模块功能。 一、Neo4j 核心知识铺垫 在使用工具前，我们需要先理解 Neo4j 的本质和核心概念，这是后续操作的基础。 1. 什么是 Neo4j？ Neo4j 是世界上最流行的原生图数据库（Native Graph Database），专门用于存储、查询和分析 “实体之间的关联关系”。它与我们熟悉的 MySQL 等关系型数据库的核心差异的是： * 关系型数据库（MySQL）：用 “表 + 行 + 外键” 间接表示关联，查询多表关联时需频繁 JOIN，效率低； * 图数据库（Neo4j）

By Ne0inhk
【无人机】无人机路径规划算法

【无人机】无人机路径规划算法

目录 一、引言：无人机与路径规划算法 二、路径规划算法基础 （一）定义与重要性 （二）规划目标与约束条件 三、常见路径规划算法详解 （一）A * 算法 （二）Dijkstra 算法 （三）RRT（快速扩展随机树）算法 （四）蚁群算法 四、算法应用实例与效果展示 （一）不同场景下的算法应用 （二）算法性能对比数据 五、算法的优化与发展趋势 （一）现有算法的优化策略 （二）结合新技术的发展方向 六、挑战与展望 （一）面临的技术挑战 （二）未来应用前景 七、结论 一、引言：无人机与路径规划算法 在科技飞速发展的今天，无人机作为一种极具创新性的技术产物，已深度融入我们生活的方方面面，

By Ne0inhk

简单理解：单片机怎么和FPGA通信

了解单片机与 FPGA 之间的通信方式，这是嵌入式系统中非常常见的硬件交互场景，核心是要根据传输速率、硬件资源、开发复杂度选择合适的通信协议。 一、主流通信方式及实现方案 单片机和 FPGA 通信主要分为并行通信和串行通信两大类，下面按从易到难、从低速到高速的顺序介绍： 1. 通用 IO 口（GPIO）自定义协议（最简单） 适合低速、短距离、数据量小的场景（如按键、状态交互），完全自定义通信规则，开发灵活。 * 硬件连接： * 单片机：1 个输出引脚（发送） + 1 个输入引脚（接收） * FPGA：1 个输入引脚（接收） + 1 个输出引脚（发送） * 需共地，建议加 10K 上拉电阻提高稳定性。 * 单片机端（C 语言，

By Ne0inhk