当前位置： 首页 > news >正文

《AVL树的原理与C++实现：详解平衡二叉搜索树的高效构建与操作》

news 2025/8/14 12:01:26

前引： 二叉搜索树（BST）在理想情况下能实现O(log n)时间复杂度的操作，但极端情况下可能退化为链表，导致效率骤降至O(n)。为解决这一问题，两位苏联数学家Adelson-Velsky和Landis于1962年提出AVL树，通过动态平衡机制维持树的高度平衡。本文将从理论到实践，逐步拆解AVL树的平衡逻辑，并给出模块化的C++实现，为后续的红黑树等高级数据结构打下基础！

目录

【一】AVL树的介绍

【二】AVL树的特点

【三】AVL树的节点结构

【四】insert（插入） 

（1）插入操作

（2）更新平衡因子

（3）旋转调整

（1）单左旋转

（2）单右旋转

（3）右左双旋

（4）左右双旋

（5）旋转总结

（4）总代码参考

【五】测试

测试结果

【一】AVL树的介绍

在之前我们学习过了搜索二叉树，虽然对于查找有高效作用，但是可能出现极端的情况，如右图：

于是两位苏联数学家Adelson-Velsky和Landis于1962年提出AVL树，永远保持左右子树的平衡因子的绝对值在【0,1】，通过动态平衡机制维持树的高度平衡！例如：

【二】AVL树的特点

（1）严格的平衡特性：保证该节点的左右子树平衡因子绝对值控制在【0,1】，避免极端情况

（2）旋转平衡机制：如果出现极端情况，会通过旋转来恢复平衡（后面会细说）

（3）高效操作复杂度：查找、插入、删除操作均保持O(log n)时间复杂度

                                      平衡因子维护使旋转操作最多影响O(log n)个节点

（4）性能趋势：适用于频繁查询，查询效率比红黑树更加的稳定

【三】AVL树的节点结构

每个树节点需要涉及到下面几个变量：

数据存储（pair< >）

左右指针（left，right）

父节点指针（parent）

平衡因子（banance）（左右子树的高度差值）

AVL树我们可以通过一个 key 实现，也可以通过（key，value）实现，这里我们来通过后者完成

每个节点在刚创建时它的三个节点指针应该都为空，平衡因子也应该为0，如下参考：

//节点
template<class K,class V>
struct AVL_TreeNode
{AVL_TreeNode(const pair<K, V>& _date):date(_date),parent(nullptr),left(nullptr),right(nullptr),balance(0){ }//数据pair<K, V> date;//节点指针AVL_TreeNode<K, V>* parent;AVL_TreeNode<K, V>* left;AVL_TreeNode<K, V>* right;//平衡因子int balance;
};

【四】insert（插入） 

插入的整个流程应该是这样的：

插入节点 -> 更新平衡因子 -> 调整

（1）插入操作

（1）我们首先需要判断这棵树是否为空，空则直接创建一个根节点即可

if (root == nullptr)
{root = new Node(date);return true;
}

（2）AVL树的插入需要满足搜索二叉树的节点插入性质：大的在右边，小的在左边

         找到插入位置之后，我们开始创建节点，完成连接

         注意：这里是三叉链（left、right、parent）的连接

//找插入位置
Node* parent = nullptr;
Node* cur = root;
while (cur)
{//如果date>cur->date,右子树parent = cur;if (date.first > cur->date.first){cur = cur->right;}else if (date.first < cur->date.first){cur = cur->left;}else{//如果值相等，不符合key唯一条件return false;}
}
//插入连接节点
cur = new Node(date);
if (parent->date.first > date.first)
{parent->left = cur;
}
else
{parent->right = cur;
}
//连接父节点（重点）
cur->parent = parent;
（2）更新平衡因子

平衡因子的更新有以下几种情况（我们统一用右子树的高度差减去左子树的高度差）：

（1）如果新节点插在父节点右边，平衡因子加加，因为右边子树高度+1；反之减减

（2）节点的插入对于平衡条件有影响的情况只可能是父节点的平衡因子不为0的情况下

         例如：此时父节点1的平衡因子因为左右子树完全平衡，父节点平衡因子为0

但是此时我们不管是在右边还是左边去插入节点，插入节点的祖先节点都会受到影响，例如：

但此时如果让父节点2完全平衡，那么不会对父节点的祖先造成影响，例如：

（3）如果更新完父节点的平衡因子之后依然为1/-1，那么说明造成影响，需要向上更新平衡

（4）如果更新完父节点的平衡因子之后为2/-2，说明这棵树不符合平衡性质，例如：

此时我们就需要调整（旋转）来让这棵树重新保证平衡！

	//更新平衡因子while (parent){//当前节点if (parent->left == cur){parent->balance--;}else{parent->balance++;}if (parent->balance == 0){return true;}//如果更新完根节点if (parent->balance == 0){return true;}else if (parent->balance == 1 || parent->balance == -1){//继续向上更新cur = parent;parent = parent->parent;}else if (parent->balance == 2 || parent->balance == -2){//旋转调整}else{assert(false);}}
（3）旋转调整

旋转一共有四种情况，下面我分开来讲解！

（1）单左旋转

单左旋转：仅仅树的右边不平衡，那么想要右边平衡，只能向左调整

调整方法：将右子树往左边调，可以发现，中间节点是处于临界状态，那么可以如下调整：

注意：观察下面的旋转哪些节点是不需要动的！同时更新调整之后的平衡因子

一棵树的情况是无限的，以下是 h为0 和 h为1 的情况：

h为0:       将parent当做cur的左孩子，这样就完成了旋转，但是如果cur本身就有左孩子呢？

h为1：    如果cur本身就有左孩子，那么我们可以将cur的左孩子当为parent的右孩子例如：

//单左旋转
void Whirl_L(Node* parent)
{//标记节点Node* cur = parent->right;Node* curleft = cur->left;Node* pphead = parent->parent;//连接parent和curcur->left = parent;parent->parent = cur;//连接curright和parentparent->right = curleft;if (curleft){curleft->parent = parent;}//如果pphead为空，说明pphead是root的根节点if (pphead){//确定cur和pphead链接位置cur->parent = pphead;if (pphead->left == parent){pphead->left = cur;}else{pphead->right = cur;}}else{root = cur;cur->parent = nullptr;}//更新cur和parent的平衡因子cur->balance = 0;parent->balance = 0;
}
（2）单右旋转

单右旋转：单右旋转就是只有左边的子树不平衡，需要向右调整

调整方法：将parent作为cur的右子树，cur本身的右子树作为parent的左子树

注意：观察下面的旋转哪些节点是不需要动的！同时更新调整之后的平衡因子

我依然先推导 h为0 和 h为1 的情况：

h为0：

h为1：

//单右旋转
void Whirl_R(Node* parent)
{//标记节点Node* cur = parent->left;Node* curright = cur->right;Node* pphead = parent->parent;//连接parent和curcur->right = parent;parent->parent = cur;//连接curright和parentparent->left = curright;if (curright){curright->parent = parent;}//连接cur和pphead（注意：pphead可能是root->parent是空if (pphead){//判断cur的连接位置cur->parent = pphead;if (pphead->left == parent){pphead->left = cur;}else{pphead->right = cur;}}else{root = cur;cur->parent = nullptr;}//更新平衡因子cur->balance = 0;parent->balance = 0;
}
（3）右左双旋

如果不是单边很高，那么我们就不能调用单左/右旋转，例如下面这种情况：

此时看到它很像“单左旋转”这种情况，但是它的节点却不是“一条直线”，很明显“左边多了一节”！

解决方案：先以cur（90）为旋转点进行右旋，再以parent（30）为旋转点进行左旋，例如：

旋转本质：将curlef作为三个节点的父节点，瓜分curleft的左右节点给其它两个节点 

平衡因子的更新：

如果curleft没有新节点，那么不需要瓜分它的左右节点，即三个节点的平衡因子都为0

如果插在curleft的左或者右边，那么需要瓜分curleft的左右节点，此时三个节点不平衡，需要调整

//右左双旋
void Whirl_R_L(Node* parent)
{//记录节点Node* cur = parent->right;Node* curleft = cur->left;int bf = curleft->banance;//右旋Whirl_R(parent->right);//左旋Whirl_L(parent);//如果在curleft的左右插入节点if (bf != 0){if (bf == -1){parent->balance = 1;}else{cur->balance = -1;}}
}
（4）左右双旋

同理左右双旋的情况如图，原理我就不说了，和右左双旋类似：

 //左右双旋void Whirl_L_R(Node* parent){//标记Node* cur = parent->right;Node* curright = cur->right;int bf = curright->banance;//左旋Whirl_L(parent->left);//右旋Whirl_R(parent);//如果在curleft的左右插入节点if (bf != 0){if (bf == -1){cur->balance = 1;}else{parent->balance = -1;}}}
（5）旋转总结

如何理解向哪边调整？

答：左边高->向右调整（单右旋转）；右边高->向左调整（单左旋转）

单左旋转：只有右边子树较高，那么需要向左调整

平衡因子更新：最后调整为完全平衡

单右旋转：只有左边子树较高，那么需要向右调整

平衡因子更新：最后调整为完全平衡

右左双旋：先向右调整->再向左调整

抽象理解：它本来很像“单左调整，但左边多了一小节”，导致需要先调整多的这一节，再单左调整。实质是将curleft的左右子树瓜分给cur和parent两个节点

平衡因子更新：需要考虑curleft的情况（0/1/-1），看是都不瓜分还是给parent还是cur

左右双旋：先向左调整->再向右调整

抽象理解：它本来很像“单右调整，但右边多了一小节”，导致需要先调整多的这一节，再单右调整。实质是将curleft的左右子树瓜分给cur和parent两个节点

平衡因子更新：需要考虑curleft的情况（0/1/-1），看是都不瓜分还是给parent还是cur

（4）总代码参考
//节点
template<class K,class V>
struct AVL_TreeNode
{AVL_TreeNode(const pair<K, V>& _date):date(_date),parent(nullptr),left(nullptr),right(nullptr),balance(0){ }//数据pair<K, V> date;//节点指针AVL_TreeNode<K, V>* parent;AVL_TreeNode<K, V>* left;AVL_TreeNode<K, V>* right;//平衡因子int balance;
};template<class K,class V>
class AVL_Tree
{typedef AVL_TreeNode<K, V> Node;public:bool insert(const pair<K, V>& date){if (root == nullptr){root = new Node(date);return true;}//找插入位置Node* parent = nullptr;Node* cur = root;while (cur){//如果date>cur->date,右子树parent = cur;if (date.first > cur->date.first){cur = cur->right;}else if (date.first < cur->date.first){cur = cur->left;}else{//如果值相等，不符合key唯一条件return false;}}//插入连接节点cur = new Node(date);if (parent->date.first > date.first){parent->left = cur;}else{parent->right = cur;}cur->parent = parent;//更新平衡因子while (parent){//当前节点if (parent->left == cur){parent->balance--;}else{parent->balance++;}if (parent->balance == 0){return true;}//如果更新完根节点if (parent->balance == 0){return true;}else if (parent->balance == 1 || parent->balance == -1){//继续向上更新cur = parent;parent = parent->parent;}else if (parent->balance == 2 || parent->balance == -2){if (parent->balance == 2 && cur->balance == 1){//单左旋转Whirl_L(parent);}else if (parent->balance == -2 && cur->balance == -1){//单右旋转Whirl_R(parent);}else if (parent->balance == 2 && cur->balance == -1){//右左双旋Whirl_R_L(parent);}else if (parent->balance == -2 && cur->balance == 1){//左右双旋Whirl_L_R(parent);}break;}else{assert(false);}}return true;}//单左旋转void Whirl_L(Node* parent){//标记节点Node* cur = parent->right;Node* curleft = cur->left;Node* pphead = parent->parent;//连接parent和curcur->left = parent;parent->parent = cur;//连接curright和parentparent->right = curleft;if (curleft){curleft->parent = parent;}//如果pphead为空，说明pphead是root的根节点if (pphead){//确定cur和pphead链接位置cur->parent = pphead;if (pphead->left == parent){pphead->left = cur;}else{pphead->right = cur;}}else{root = cur;cur->parent = nullptr;}//更新cur和parent的平衡因子cur->balance = 0;parent->balance = 0;}//单右旋转void Whirl_R(Node* parent){//标记节点Node* cur = parent->left;Node* curright = cur->right;Node* pphead = parent->parent;//连接parent和curcur->right = parent;parent->parent = cur;//连接curright和parentparent->left = curright;if (curright){curright->parent = parent;}//连接cur和pphead（注意：pphead可能是root->parent是空if (pphead){//判断cur的连接位置cur->parent = pphead;if (pphead->left == parent){pphead->left = cur;}else{pphead->right = cur;}}else{root = cur;cur->parent = nullptr;}//更新平衡因子cur->balance = 0;parent->balance = 0;}//右左双旋void Whirl_R_L(Node* parent){//记录节点Node* cur = parent->right;Node* curleft = cur->left;int bf = curleft->balance;//右旋Whirl_R(parent->right);//左旋Whirl_L(parent);//如果在curleft的左右插入节点if (bf != 0){if (bf == -1){parent->balance = 1;}else{cur->balance = -1;}}/*if (bf == 0){cur->balance = 0;parent->balance = 0;curleft->balance = 0;}else{if (bf == -1){cur->balance = 0;parent->balance = 1;curleft->balance = 0;}else{cur->balance = 0;parent->balance = -1;curleft->balance = 0;}}*/}//左右双旋void Whirl_L_R(Node* parent){//标记Node* cur = parent->left;Node* curright = cur->right;int bf = curright->balance;//左旋Whirl_L(parent->left);//右旋Whirl_R(parent);//如果在curleft的左右插入节点if (bf != 0){if (bf == -1){cur->balance = 1;}else{parent->balance = -1;}}/*if (bf == 0){cur->balance = 0;parent->balance = 0;curright->balance = 0;}else{if (bf == -1){cur->balance = 1;parent->balance = 0;curright->balance = 0;}else{cur->balance = 0;parent->balance = -1;curright->balance = 0;}}*/}

【五】测试

我们来一个高度检测函数来测试一下：

//测试
int Height()
{return Height(root);
}//求高度
int Height(Node* root)
{if (root == nullptr)return 0;int leftHeight = Height(root->left);int rightHeight = Height(root->right);return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
}bool IsBalance()
{return IsBalance(root);
}//高度判断
bool IsBalance(Node* root)
{if (root == nullptr)return true;int leftHight = Height(root->left);int rightHight = Height(root->right);if (rightHight - leftHight != root->balance){cout << "平衡因子异常:" << root->date.first << "->" << root->balance << endl;return false;}return true;
}
测试结果

http://www.lryc.cn/news/620022.html

相关文章：

  • 【自动化运维神器Ansible】playbook主机清单变量深度解析：主机变量与组变量的实战应用
  • JavaWeb-Servlet基础
  • CodeBuddy在AI开发方面的一些特色
  • 1.Cursor快速入门与配置
  • PyTorch Tensor完全指南：深度学习数据操作的核心艺术
  • Matlab（4）
  • C++ stack and queue
  • 【OSPP 开源之夏】Good First issue 第一步—— openEuler Embedded 计划
  • 机器视觉的零件误差检测系统：基于多角度点云融合的圆柱体零件尺寸测量
  • 5. synchronized 关键字 - 监视器锁 monitor lock
  • InnoDB如何解决脏读、不可重复读和幻读的？
  • mysql - 查询重复数据，不区分大小重复问题解决
  • 服务器查看 GPU 占用情况的方法
  • 安全点（Safepoint）完成后唤醒暂停线程的过程
  • 响应式对象的类型及其使用场景
  • 量子安全新纪元：F5发布全新AI驱动的全栈式后量子加密AI安全方案
  • 破解测试数据困境：5招兼顾安全与真实性
  • 全球AI安全防护迈入新阶段：F5推出全新AI驱动型应用AI安全解决方案
  • 【前端Vue】使用ElementUI实现表单中可选择可编辑的下拉框
  • 仓库无人叉车的安全功能有哪些？如何在提升效率时保障安全？
  • k8s中的控制器的使用
  • 汽车高位制动灯难达 CIE 标准？OAS 光学软件高效优化破局
  • 中科米堆CASAIM汽车零部件三维扫描检测解决方案
  • 服务器通过生成公钥和私钥安全登录
  • 单例模式的理解
  • Spring Security 前后端分离场景下的会话并发管理
  • C语言：指针（4）
  • 【2025】Datawhale AI夏令营-多模态RAG-Task3笔记-解决方案进阶
  • 蓝蜂网关在雄安新区物联网建设中的关键应用
  • 补环境基础(四) Hook插件