【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

别再乱用 ArrayList 了！这 4 个隐藏坑，90% 的 Java 开发者都踩过

别再乱用 ArrayList 了！这 4 个隐藏坑，90% 的 Java 开发者都踩过

🎁个人主页：User_芊芊君子 🎉欢迎大家点赞👍评论📝收藏⭐文章 🔍系列专栏：AI 文章目录： * 【前言】 * 坑 1：遍历删除元素，触发 ConcurrentModificationException * 坑的表现 * 踩坑场景 * 底层原因（通俗解释） * 错误/正确代码对比 * 错误代码 * 正确代码（3 种方案） * 坑 2：初始容量设置不当，导致频繁扩容，性能损耗 * 坑的表现 * 踩坑场景 * 底层原因（通俗解释） * 错误/正确代码对比 * 错误代码 * 正确代码 * 扩展建议 * 坑 3：空指针/索引越界，忽略索引范围或元素为空 * 坑的表现 * 踩坑场景 * 底层原因（通俗解释） * 错误/

By Ne0inhk
【Java 开发日记】我们来说一说 Redis 主从复制的原理及作用

【Java 开发日记】我们来说一说 Redis 主从复制的原理及作用

目录 概述 一、核心作用 二、详细工作原理 阶段 1：连接建立与配置 阶段 2：数据同步（全量/部分同步） 阶段 3：命令传播（增量同步） 三、重要特性与配置 四、总结与形象比喻 面试回答 概述 Redis 主从复制是一种数据同步机制，它允许一个 Redis 服务器（称为 主服务器/Master）将其数据复制到一个或多个 Redis 服务器（称为 从服务器/Slave/Replica）。这是 Redis 实现高可用性、可扩展性和数据冗余的核心技术之一。 一、核心作用 1. 数据冗余与备份： * 核心作用：从服务器是主服务器数据的实时热备份。当主服务器数据丢失或损坏时，

By Ne0inhk
【JAVA 进阶】SpringMVC全面解析：从入门到实战的核心知识点梳理

【JAVA 进阶】SpringMVC全面解析：从入门到实战的核心知识点梳理

文章目录 * 前言 * 一、SpringMVC概述 * 1.1 MVC设计模式简介 * 1.2 SpringMVC的定义与核心优势 * 1.3 SpringMVC的应用场景 * 二、SpringMVC核心原理与执行流程 * 2.1 SpringMVC核心组件 * 2.1.1 前端控制器（DispatcherServlet） * 2.1.2 处理器映射器（HandlerMapping） * 2.1.3 处理器适配器（HandlerAdapter） * 2.1.4 处理器（Handler） * 2.1.5 视图解析器（ViewResolver） * 2.1.6 视图（View） * 2.1.

By Ne0inhk
Gemini永久会员 Shiro是一个功能强大且易于使用的Java安全框架，提供了认证、授权、加密和会话管理等功能

Gemini永久会员 Shiro是一个功能强大且易于使用的Java安全框架，提供了认证、授权、加密和会话管理等功能

Shiro是一个功能强大且易于使用的Java安全框架，提供了认证、授权、加密和会话管理等功能，以下是对其核心用法及关键组件的详细介绍： 一、核心组件 1. Subject（主体）：代表当前操作的“用户”，可能是实际用户、程序或定时任务等。通过SecurityUtils.getSubject()获取当前Subject，所有安全操作（如登录、权限校验）都通过Subject触发。 2. SecurityManager（安全管理器）：Shiro的“大脑”，负责协调所有安全组件（认证、授权、会话等），是Shiro的核心调度中心。开发者无需直接操作SecurityManager，只需通过Subject间接调用其功能。 3. Realm（领域）：Shiro的“数据源接口”，负责从数据库、缓存、配置文件等地方获取用户信息（如账号密码、权限列表）。认证时，Realm提供用户的真实凭证；授权时，Realm提供用户的权限集合。自定义Realm是Shiro灵活适配业务的关键。 4. Authenticator（

By Ne0inhk