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

news/2024/10/9 6:33:32/

在这里插入图片描述
个人主页
在这里插入图片描述

文章目录

  • ⭐一、AVL树的概念
  • 🎉二、AVL树的性质
  • 🏝️三、AVL树的实现
    • 1. 树的基本结构
    • 2. 树的插入
    • 3. 树的旋转
      • • 左单旋
      • • 右单旋
      • • 左右双旋
      • • 右左双旋
  • 🎡四、AVL树的其它功能
    • 1. 树的查找
    • 2. 树的遍历
    • 3. 树的高度
    • 4. 树的大小
  • 🚀五、总结
    • 1. AVL树的优缺点
    • 2. 完整代码

⭐一、AVL树的概念

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

🎉二、AVL树的性质

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

🏝️三、AVL树的实现

1. 树的基本结构

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

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){}
};

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为根节点的子树已经不平衡了，需要进行旋转处理。
在这里插入图片描述

bool Insert(const pair<K, V>& kv)
{//如果树为空，则插入的节点就是根节点if (_root == nullptr){_root = new Node(kv);return true;}Node* parent = nullptr;Node* cur = _root;while (cur){if (cur->_kv.first < kv.first){parent = cur;cur = cur->_right;}else if (cur->_kv.first > kv.first){parent = cur;cur = cur->_left;}else{return false;}}cur = new Node(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--;}elseparent->_bf++;if (parent->_bf == 0){break;}else if (parent->_bf == 1 || parent->_bf == -1){//继续往上进行更新cur = parent;parent = parent->_parent;}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);}}else{assert(false);}break;}return true;
}

3. 树的旋转

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

• 左单旋

条件：新节点插入到子树较高的右侧。
我们用图来感受一下其旋转的过程：
在这里插入图片描述
1.先将15的左子树的节点12变成10的右子树。
2.再将10变成15的左子树，15成为新树的根节点。
3.更新平衡因子

由于左单旋的情况很多，我们也可以用一张抽象图来表示：
在这里插入图片描述
代码所示：

//左单旋
void RotateL(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.更新平衡因子。
代码所示：

//右单旋
void RotateR(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。

代码所示：

	//左右双旋void RotateLR(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;}else if (bf == 1){subLR->_bf = 0;subL->_bf = -1;parent->_bf = 0;}else if (bf == 0){subLR->_bf = 0;subL->_bf = 0;parent->_bf = 0;}else{assert(false);}}

• 右左双旋

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

//右左双旋
void RotateRL(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;}else if (bf == 1){subR->_bf = 0;subRL->_bf = 0;parent->_bf = -1;}else if (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;}else if (cur->_kv.first > key){cur = cur->_left;}else{return cur;}}return nullptr;}

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>
using namespace std;template<class K, class V>
struct AVLTreeNode
{// 需要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<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* parent = nullptr;Node* cur = _root;while (cur){if (cur->_kv.first < kv.first){parent = cur;cur = cur->_right;}else if (cur->_kv.first > kv.first){parent = cur;cur = cur->_left;}else{return false;}}cur = new Node(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--;}elseparent->_bf++;if (parent->_bf == 0){break;}else if (parent->_bf == 1 || parent->_bf == -1){//继续往上进行更新cur = parent;parent = parent->_parent;}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);}}else{assert(false);}break;}return true;}//右单旋void RotateR(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;}//左单旋void RotateL(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;}//左右双旋void RotateLR(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;}else if (bf == 1){subLR->_bf = 0;subL->_bf = -1;parent->_bf = 0;}else if (bf == 0){subLR->_bf = 0;subL->_bf = 0;parent->_bf = 0;}else{assert(false);}}//右左双旋void RotateRL(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;}else if (bf == 1){subR->_bf = 0;subRL->_bf = 0;parent->_bf = -1;}else if (bf == -1){subR->_bf = 1;subRL->_bf = 0;parent->_bf = 0;}else{assert(false);}}void Inorder(){_Inorder(_root);cout << endl;}void Hight(){return _Hight(_root);}void Size(){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;}else if (cur->_kv.first > key){cur = cur->_left;}else{return cur;}}return nullptr;}
private:Node* _root = nullptr;
};

http://www.ppmy.cn/news/1536510.html

相关文章

【AIGC】2022-NIPS-视频扩散模型

【AIGC】2022-NIPS-视频扩散模型

2022-NIPS-Video Diffusion Models 视频扩散模型摘要1. 引言2. 背景3. 视频扩散模型3.1. 重建引导采样以改进条件生成 4. 实验4.1. 无条件视频建模4.2. 视频预测4.3. 文本条件视频生成4.3.1 视频与图像建模的联合训练4.3.2 无分类器指导的效果4.3.3 更长序列的自回归视频扩展 5…
阅读更多...
【环境配置】科研小白Windows下安装Git

【环境配置】科研小白Windows下安装Git

2024年小白使用Win10安装Git 2.46.2教程&#xff1a; 1 下载安装包 访问下载地址 Git - Downloading Package (git-scm.com) 下载之后打开文件 2 安装过程 点击Next 2.1 选择安装路径 2.2 选择勾选必要组件 2.3 一路Next 这一步直接Next即可 继续点击Next 继续点击Ne…
阅读更多...
【目标检测】工程机械车辆数据集2690张4类VOC+YOLO格式

【目标检测】工程机械车辆数据集2690张4类VOC+YOLO格式

数据集格式&#xff1a;Pascal VOC格式YOLO格式(不包含分割路径的txt文件&#xff0c;仅仅包含jpg图片以及对应的VOC格式xml文件和yolo格式txt文件) 图片数量(jpg文件个数)&#xff1a;2694 标注数量(xml文件个数)&#xff1a;2694 标注数量(txt文件个数)&#xff1a;2694 标注…
阅读更多...
vue-scrollto实现页面组件锚点定位

vue-scrollto实现页面组件锚点定位

文章目录 前言背景操作指南安装及配置步骤vue组件中使用 参考文章 前言 博主介绍&#xff1a;✌目前全网粉丝3W&#xff0c;csdn博客专家、Java领域优质创作者&#xff0c;博客之星、阿里云平台优质作者、专注于Java后端技术领域。 涵盖技术内容&#xff1a;Java后端、大数据…
阅读更多...
【devops】devops-ansible之剧本变量使用

【devops】devops-ansible之剧本变量使用

本站以分享各种运维经验和运维所需要的技能为主 《python零基础入门》：python零基础入门学习 《python运维脚本》： python运维脚本实践 《shell》：shell学习 《terraform》持续更新中：terraform_Aws学习零基础入门到最佳实战 《k8》从问题中去学习k8s 《docker学习》暂未更…
阅读更多...
【线性代数】【第三章】n维向量习题

【线性代数】【第三章】n维向量习题

文章目录 一. 基本内容与重要结论1. 基础知识2. 重要定理2.1. 线性表示与秩2.2. 整体组与部分组&#xff0c;延伸组与缩短组 一. 典型例题1. 线性相关性题型一&#xff1a;利用向量组性质判断相关性题型二&#xff1a;利用定义&#xff08;进行线性表示&#xff09;判断线性相关…
阅读更多...
Web安全 - 阶段性总结回顾_风险评估

Web安全 - 阶段性总结回顾_风险评估

文章目录 OWASP 2023 TOP 10用户数据的威胁评估密码盗窃XSS 漏洞SQL 注入CSRF 漏洞 资产数据的威胁评估SSRF 漏洞反序列化漏洞插件漏洞后门 认证和授权的安全防护检测与过滤加强认证补丁管理 进一步防护手段最小权限原则WAFIDS 小结 OWASP 2023 TOP 10 OWASP Top 10 概述 OWASP…
阅读更多...
k8s 之安装metrics-server

k8s 之安装metrics-server

作者&#xff1a;程序那点事儿 日期&#xff1a;2024/01/29 18:25 metrics-server可帮助我们查看pod的cpu和内存占用情况 kubectl top po nginx-deploy-56696fbb5-mzsgg # 报错&#xff0c;需要Metrics API 下载 Metrics 解决 wget https://github.com/kubernetes-sigs/metri…
阅读更多...
最新文章

Copyright @ 2022~2023