【C++】AVL树的底层以及实现

Ne0inhk

— 12 min read
【C++】AVL树的底层以及实现


个人主页

在这里插入图片描述

文章目录

⭐一、AVL树的概念

AVL树是一种高度平衡的平衡二叉树，相比于搜索二叉树，它的特点在于左右子树都为AVL树且树的高度差的绝对值不超过1。
这里我们会引入一个新的概念叫做平衡因子。平衡因子也就是左右子树的高度差，我们可以通过平衡因子方便我们后续去观察和控制树是否平衡。

在这里插入图片描述

🎉二、AVL树的性质

AVL树主要有三大性质：
1.每棵树的左右子树都是AVL树。
2.左子树和右子树的高度之差的绝对值不超过1。
3.每个节点都会有一个平衡因子，且任何一个节点的平衡因子都为1、0、-1。

🏝️三、AVL树的实现

1. 树的基本结构

AVL树的结点包含了左右节点的指针以及父亲节点的指针，同时还有有key、value以及代表树平衡的平衡因子。

template<classK,classV>structAVLTreeNode{ 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){}};

2. 树的插入

树的插入按照搜索二叉树的规则进行插入。插入节点后更新平衡因子，如果没有违反规则(即没有导致节点的平衡因子变成2/-2)，则插入结束；如果违反规则，则树会不平衡，需要进行旋转操作。

平衡因子的更新规则：
1.平衡因子 = 右子树高度 - 左子树高度。
2.只有子树高度的变化才会影响当前节点的平衡因子。
3.插入节点后会增加数的高度，若新增节点在parent的右子树，则parent的平衡因子++，相反在parent的左子树时，则平衡因子- -。

每更新完一个节点的平衡因子都需要进行以下判断：
1.如果parent的平衡因子等于1/-1时，说明parent原先的平衡因子为0，插入节点后左子树或右子树的高度增加了，说明还需要向上更新平衡因子。
2.如果parent的平衡因子等于0，说明parent原先的平衡因子为1/-1，插入节点后左右两棵子树从不平衡变平衡了，说明无需更新平衡因子。
3.如果parent的平衡因子等于2/-2时，说明parent原先的平衡因子等于1/-1，插入节点后插入到了较高的那一棵子树，说明此时以parent为根节点的子树已经不平衡了，需要进行旋转处理。

在这里插入图片描述
boolInsert(const pair<K, V>& kv){//如果树为空，则插入的节点就是根节点if(_root ==nullptr){ _root =newNode(kv);returntrue;} Node* parent =nullptr; Node* cur = _root;while(cur){if(cur->_kv.first < kv.first){ parent = cur; cur = cur->_right;}elseif(cur->_kv.first > kv.first){ parent = cur; cur = cur->_left;}else{returnfalse;}} cur =newNode(kv);if(parent->_kv.first < kv.first){ parent->_right = cur;}else{ parent->_left = cur;} cur->_parent = parent;//更新平衡因子while(parent){if(cur == parent->_left){ parent->_bf--;}else parent->_bf++;if(parent->_bf ==0){break;}elseif(parent->_bf ==1|| parent->_bf ==-1){//继续往上进行更新 cur = parent; parent = parent->_parent;}elseif(parent->_bf ==2|| parent->_bf ==-2){//不平衡，旋转处理if(parent->_bf ==-2&& cur->_bf ==-1){RotateR(parent);}elseif(parent->_bf ==2&& cur->_bf ==1){RotateL(parent);}elseif(parent->_bf ==-2&& cur->_bf ==1){RotateLR(parent);}elseif(parent->_bf ==2&& cur->_bf ==-1){RotateRL(parent);}else{assert(false);}}else{assert(false);}break;}returntrue;}

3. 树的旋转

旋转的目的就是让树从失衡到平衡，降低树的高度。
旋转主要分为四种，分别为左单旋、右单旋、左右双旋和右左双旋。下面我们具体讲讲每一种旋转的内部逻辑。

• 左单旋

条件：新节点插入到子树较高的右侧。
我们用图来感受一下其旋转的过程：

1.先将15的左子树的节点12变成10的右子树。
2.再将10变成15的左子树，15成为新树的根节点。
3.更新平衡因子

由于左单旋的情况很多，我们也可以用一张抽象图来表示：

在这里插入图片描述


代码所示：

//左单旋voidRotateL(Node* parent){ Node* subR = parent->_right; Node* subRL = subR->_left; parent->_right = subR;if(subRL) subRL->_parent = parent; Node* pparent = parent->_parent;if(pparent ==nullptr){ _root = subR; subR->_parent =nullptr;}else{if(pparent == parent->_right){ parent->_right = subR;}else{ parent->_left = subR;} subR->_parent = pparent;} parent->_bf = subR->_bf =0;}

• 右单旋

条件：新节点插入到子树较高的左侧
用图来感受旋转的过程：

在这里插入图片描述


我们会发现和左单旋和相似
1.先将5的右子树的值b变成10的左子树。
2.再将10变成5的右子树，旋转完后5成为整棵树的根节点。
3.更新平衡因子。
代码所示：

//右单旋voidRotateR(Node* parent){ Node* subL = parent->_left; Node* subLR = subL->_right; parent->_left = subLR;if(subLR) subLR->_parent = parent; Node* pparent = parent->_parent; subL->_right = parent; parent->_parent = subL;if(pparent ==nullptr){ _root = subL; subL->_parent =nullptr;}else{if(pparent == parent->_left){ parent->_left = subL;}else{ parent->_right = subL;} subL->_parent = pparent;} parent->_bf = subL->_bf =0;}

• 左右双旋

条件：新节点插入到较高左子树的右侧。
下面我们用图来演示一下其旋转过程：
1.插入新节点

在这里插入图片描述


2.以节点5为旋转点进行左单旋

在这里插入图片描述


3.以节点为10进行右单旋

在这里插入图片描述


4.旋转完后更新平衡因子。
平衡因子又分为三种情况：
1.当subLR的平衡因子为-1时，左右双旋后parent、subL,subLR的平衡因子分别为1、0、0。
2.当subLR的平衡因子为1时，左右双旋后parent、subL,subLR的平衡因子分别为0、-1、0。
3.当subLR的平衡因子为0时，左右双旋后parent、subL,subLR的平衡因子分别为0、0、0。

代码所示：

//左右双旋voidRotateLR(Node* parent){ Node* subL = parent->_left; Node* subLR = subL->_right;int bf = subLR->_bf;RotateL(parent->_left);RotateR(parent);if(bf ==-1){ subLR->_bf =0; subL->_bf =0; parent->_bf =1;}elseif(bf ==1){ subLR->_bf =0; subL->_bf =-1; parent->_bf =0;}elseif(bf ==0){ subLR->_bf =0; subL->_bf =0; parent->_bf =0;}else{assert(false);}}

• 右左双旋

条件：插入到较高右子树的左侧
其旋转过程和左右双旋类似，这就不一一列举了。
旋转完过后也是需要更新平衡因子，平衡因子也是跟左右双旋一样有三种情况。
代码所示：

//右左双旋voidRotateRL(Node* parent){ Node* subR = parent->_right; Node* subRL = subR->_left;int bf = subRL->_bf;RotateR(parent);RotateL(parent);if(bf ==0){ subR->_bf =0; subRL->_bf =0; parent->_bf =0;}elseif(bf ==1){ subR->_bf =0; subRL->_bf =0; parent->_bf =-1;}elseif(bf ==-1){ subR->_bf =1; subRL->_bf =0; parent->_bf =0;}else{assert(false);}}

🎡四、AVL树的其它功能

1. 树的查找

定义一个cur指针从树的根节点开始查找，按一下规则进行查找：
1.当key的值小于当前节点的值时，则在该节点的左边进行查找。
2.当key的值大于当前节点的值时，则在该节点的右边进行查找。
3.若key的值等于当前节点的值时，则说明查找成功，返回true。
4.若遍历完还没查找到该节点的值，则说明没有此节点，返回false。
代码所示：

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

2. 树的遍历

我们遍历方式有前序、中序、后序、层序等方式，我们在这就采用中序遍历的方式来遍历树的每一节点。
代码所示：

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

3. 树的高度

int_Height(Node* root){if(root ==nullptr){return;}int leftHeight =_Height(root->_left);int rightHeight =_Height(root->_right);return leftHeight > rightHeight ? leftHeight +1: rightHeight +1;}

4. 树的大小

返回左子树+右子树再加上根节点即可。

int_Size(Node* root){if(root ==nullptr){return;}return_Size(root->_left)+_Size(root->_right)+1;}

🚀五、总结

1. AVL树的优缺点

优点：
**1.查找效率高：**由于AVL树总是保持平衡，其高度相对较低，因此查找操作的时间复杂度为O(log2N)，效率较高。
2.结构稳定： AVL树的平衡性使得其结构相对稳定，不会出现极端不平衡的情况，从而保证了操作的稳定性和可靠性。

缺点：
1.插入和删除复杂： AVL树在插入和删除节点时，可能需要通过旋转操作来保持树的平衡，比较复杂。
2.可能导致性能下降： 在频繁插入和删除的场景下，AVL树需要不断地进行旋转操作来保持平衡，这就有可能导致性能降低。

2. 完整代码

#include<iostream>#include<assert.h>usingnamespace std;template<classK,classV>structAVLTreeNode{// 需要parent指针，后续更新平衡因子可以看到 pair<K, V> _kv; AVLTreeNode<K, V>* _left; AVLTreeNode<K, V>* _right; AVLTreeNode<K, V>* _parent;//平衡因子int _bf;// balance factorAVLTreeNode(const pair<K, V>& kv):_kv(kv),_left(nullptr),_right(nullptr),_parent(nullptr),_bf(0){}};template<classK,classV>classAVLTree{typedef AVLTreeNode<K, V> Node;public:boolInsert(const pair<K, V>& kv){if(_root ==nullptr){ _root =newNode(kv);returntrue;} Node* parent =nullptr; Node* cur = _root;while(cur){if(cur->_kv.first < kv.first){ parent = cur; cur = cur->_right;}elseif(cur->_kv.first > kv.first){ parent = cur; cur = cur->_left;}else{returnfalse;}} cur =newNode(kv);if(parent->_kv.first < kv.first){ parent->_right = cur;}else{ parent->_left = cur;} cur->_parent = parent;//更新平衡因子while(parent){if(cur == parent->_left){ parent->_bf--;}else parent->_bf++;if(parent->_bf ==0){break;}elseif(parent->_bf ==1|| parent->_bf ==-1){//继续往上进行更新 cur = parent; parent = parent->_parent;}elseif(parent->_bf ==2|| parent->_bf ==-2){//不平衡，旋转处理if(parent->_bf ==-2&& cur->_bf ==-1){RotateR(parent);}elseif(parent->_bf ==2&& cur->_bf ==1){RotateL(parent);}elseif(parent->_bf ==-2&& cur->_bf ==1){RotateLR(parent);}elseif(parent->_bf ==2&& cur->_bf ==-1){RotateRL(parent);}else{assert(false);}}else{assert(false);}break;}returntrue;}//右单旋voidRotateR(Node* parent){ Node* subL = parent->_left; Node* subLR = subL->_right; parent->_left = subLR;if(subLR) subLR->_parent = parent; Node* pparent = parent->_parent; subL->_right = parent; parent->_parent = subL;if(pparent ==nullptr){ _root = subL; subL->_parent =nullptr;}else{if(pparent == parent->_left){ parent->_left = subL;}else{ parent->_right = subL;} subL->_parent = pparent;} parent->_bf = subL->_bf =0;}//左单旋voidRotateL(Node* parent){ Node* subR = parent->_right; Node* subRL = subR->_left; parent->_right = subR;if(subRL) subRL->_parent = parent; Node* pparent = parent->_parent;if(pparent ==nullptr){ _root = subR; subR->_parent =nullptr;}else{if(pparent == parent->_right){ parent->_right = subR;}else{ parent->_left = subR;} subR->_parent = pparent;} parent->_bf = subR->_bf =0;}//左右双旋voidRotateLR(Node* parent){ Node* subL = parent->_left; Node* subLR = subL->_right;int bf = subLR->_bf;RotateL(parent->_left);RotateR(parent);if(bf ==-1){ subLR->_bf =0; subL->_bf =0; parent->_bf =1;}elseif(bf ==1){ subLR->_bf =0; subL->_bf =-1; parent->_bf =0;}elseif(bf ==0){ subLR->_bf =0; subL->_bf =0; parent->_bf =0;}else{assert(false);}}//右左双旋voidRotateRL(Node* parent){ Node* subR = parent->_right; Node* subRL = subR->_left;int bf = subRL->_bf;RotateR(parent);RotateL(parent);if(bf ==0){ subR->_bf =0; subRL->_bf =0; parent->_bf =0;}elseif(bf ==1){ subR->_bf =0; subRL->_bf =0; parent->_bf =-1;}elseif(bf ==-1){ subR->_bf =1; subRL->_bf =0; parent->_bf =0;}else{assert(false);}}voidInorder(){_Inorder(_root); cout << endl;}voidHight(){return_Hight(_root);}voidSize(){return_Size(_root);}private:void_Inorder(Node* root){if(root ==nullptr){return;}_Inorder(root->_left); cout << root->_kv.first <<":"<< root->_kv.second << endl;_Inorder(root->_right);}int_Height(Node* root){if(root ==nullptr){return;}int leftHeight =_Height(root->_left);int rightHeight =_Height(root->_right);return leftHeight > rightHeight ? leftHeight +1: rightHeight +1;}int_Size(Node* root){if(root ==nullptr){return;}return_Size(root->_left)+_Size(root->_right)+1;} Node*Find(const K& key){ Node* cur = _root;while(cur){if(cur->_kv.first < key){ cur = cur->_right;}elseif(cur->_kv.first > key){ cur = cur->_left;}else{return cur;}}returnnullptr;}private: Node* _root =nullptr;};

Read more

【Python基础】（五）Python 库使用全攻略：从标准库到第三方库，让开发效率翻倍

【Python基础】（五）Python 库使用全攻略：从标准库到第三方库，让开发效率翻倍

目录 编辑 前言 一、Python 库的核心认知：什么是库？为什么要用库？ 1.1 库的本质：现成的 "代码工具箱" 1.2 库的分类：标准库 vs 第三方库 （1）标准库：Python 自带的 "基础工具箱" （2）第三方库：全球开发者共建的 "扩展工具箱" 1.3 使用库的核心优势：效率翻倍的关键 二、标准库实战：内置工具的高效用法 2.1 日期时间处理：datetime库（计算日期差、格式转换） 实战需求：计算你和心爱的人认识多少天 扩展用法：

By Ne0inhk
Python 基础与环境配置

Python 基础与环境配置

第一篇：Python 基础与环境配置 学习目标 💡 掌握 Python 语言的基本语法和编程思想 💡 学会安装和配置 Python 开发环境 💡 理解并熟练运用 Python 的数据类型、变量和运算符 💡 掌握 Python 的流程控制语句（条件判断、循环） 💡 学会使用 Python 的函数和模块 💡 了解 Python 的常用开发工具和集成开发环境（IDE） 💡 具备编写简单 Python 程序的能力 重点内容 * Python 语言的发展历程与特点 * Python 开发环境的安装与配置 * Python 的基本语法（变量、数据类型、运算符） * 流程控制语句（if 语句、for 循环、while 循环） * 函数的定义、调用和参数传递 * 模块和包的使用 * 常用开发工具和

By Ne0inhk
在 macOS 下升级 Python 几种常见的方法

在 macOS 下升级 Python 几种常见的方法

在 macOS 下升级 Python 有几种常见的方法，具体取决于你最初是如何安装 Python 的。了解你的安装方式是关键。 首先，你需要知道你当前 Python 版本以及它的安装路径。 1. 检查 Python 版本： python --version# 可能指向 Python 2.x python3 --version# 通常指向 Python 3.x 2. 检查 Python 路径： which python which python3 根据你 which 命令的输出，我们可以推断出安装方式。常见的安装方式有： * macOS 系统自带 Python： 通常在 /usr/bin/python。不建议直接修改或升级系统自带的

By Ne0inhk
Python智慧农业信息化服务平台农产品商城系统 小程序

Python智慧农业信息化服务平台农产品商城系统 小程序

文章目录 * 技术架构设计 * 核心功能模块 * 物联网数据整合 * 性能优化策略 * 安全防护措施 * 部署与监控 * 系统设计与实现的思路 * 主要技术与实现手段 * 源码lw获取/同行可拿货,招校园代理 ：文章底部获取博主联系方式！ 技术架构设计 * 前端框架：采用微信小程序原生框架+WXML/WXSS，结合Vant Weapp组件库快速搭建UI界面。 * 后端服务：基于Django REST Framework构建API，支持JWT身份认证与RBAC权限控制。 * 数据库：MySQL存储业务数据，Redis缓存高频访问数据（如商品详情、用户会话）。 * 消息队列：使用RabbitMQ处理异步任务（如订单状态更新、消息推送）。 核心功能模块 * 用户系统：OpenID自动注册/登录，农户与消费者角色分离，个人中心集成实名认证模块。 * 商品管理：支持多级分类、动态SKU、溯源信息（区块链哈希值存储）。 * 订单系统：微信支付接口对接，物流状态实时同步（调用快递鸟API）。 智能推荐：

By Ne0inhk