C++AVL树详解

ops/2024/10/15 12:31:56/

什么是AVL树

AVL树是最先发明的⾃平衡⼆叉查找树，AVL是⼀颗空树，或者具备下列性质的⼆叉搜索树：它的
左右⼦树都是AV树，且左右⼦树的⾼度差的绝对值不超过1。AVL树是⼀颗⾼度平衡搜索⼆叉树，
通过控制⾼度差去控制平衡。
简单的来说AVL树就是可以控制自身高度差的搜索二叉树

AVL树通过什么来控制平衡

AVL树实现平衡这⾥我们引⼊⼀个平衡因⼦(balance factor)的概念，每个结点都有⼀个平衡因⼦，任何
结点的平衡因⼦等于右⼦树的⾼度减去左⼦树的⾼度，也就是说任何结点的平衡因⼦等于0/1/-1，
AVL树并不是必须要平衡因⼦，但是有了平衡因⼦可以更⽅便我们去进⾏观察和控制树是否平衡，
就像⼀个指向标⼀样。通过平衡因子我们可以更加直观的去判断AVL树到底是不是平衡的

为什么要求⾼度差不超过1，⽽不是⾼度差是0呢0不是更好的平衡吗？画画图分析我们发现，不是不想这样设计，⽽是有些情况是做不到⾼度差是0的。⽐如⼀棵树是2个结点，4个结点等情况下，⾼度差最好就是1，⽆法作为⾼度差是0
我们可以来画图看看
在这里插入图片描述

AVL树整体结点数量和分布和完全⼆叉树类似，⾼度可以控制在 ，那么增删查改的效率也可
以控制在 ，相⽐⼆叉搜索树有了本质的提升。避免了像搜索二叉树出现的一些极端情况，比如说一直插入一个比根节点小的树，就一直往左边插入，这样搜索效率就会变得很差

AVL树的插入

AVL树大致可以分为一下插入过程
1.插入和搜索二叉树一样，都是通过插入节点和当前节点进行比较小的往左走，大的往右走。

  1. 新增结点以后，只会影响祖先结点的⾼度，也就是可能会影响部分祖先结点的平衡因⼦，所以更新
    从新增结点->根结点路径上的平衡因⼦，实际中最坏情况下要更新到根，有些情况更新到中间就可
    以停⽌了，具体情况我们下⾯再详细分析。

  2. 更新平衡因⼦过程中没有出现问题，则插⼊结束

  3. 更新平衡因⼦过程中出现不平衡，对不平衡⼦树旋转，旋转后本质调平衡的同时，本质降低了⼦树
    的⾼度，不会再影响上⼀层，所以插⼊结束。

平衡因子的更新

更新规则
平衡因子 = 右子树的高度-左子树的高度

只有⼦树⾼度变化才会影响当前结点平衡因⼦

插⼊结点，会增加⾼度，所以新增结点在parent的右⼦树，parent的平衡因⼦++，新增结点在
parent的左⼦树，parent平衡因⼦–

parent所在⼦树的⾼度是否变化决定了是否会继续往上更新
更新结果
这里要分三种情况
如果更新完成之后parent是0则说明更新前子树的高度是-1或者1，说明原来的子树不平衡，一边高一边低，更新后变成0说明新插入的节点插入在低的那一边，插⼊后parent所在的⼦树⾼度不变，不会
影响parent的⽗亲结点的平衡因⼦，更新结束。
在这里插入图片描述

更新后parent的平衡因⼦等于1 或 -1，更新前更新中parent的平衡因⼦变化为0->1 或者 0->-1，说
明更新前parent⼦树两边⼀样⾼，新增的插⼊结点后，parent所在的⼦树⼀边⾼⼀边低，parent所
在的⼦树符合平衡要求，但是⾼度增加了1，会影响parent的⽗亲结点的平衡因⼦，所以要继续向上
更新
在这里插入图片描述

更新后parent的平衡因⼦等于2 或 -2，更新前更新中parent的平衡因⼦变化为1->2 或者 -1->-2，说
明更新前parent⼦树⼀边⾼⼀边低，新增的插⼊结点在⾼的那边，parent所在的⼦树⾼的那边更⾼
了，破坏了平衡，parent所在的⼦树不符合平衡要求，需要旋转处理，旋转的⽬标有两个：1、把
parent⼦树旋转平衡。2、降低parent⼦树的⾼度，恢复到插⼊结点以前的⾼度。所以旋转后也不
需要继续往上更新，插⼊结束。
在这里插入图片描述
这个旋转等下会详细说明，下面来看看AVL树的插入的实现代码

AVL树的插入

在看插入之前，我们先看看AVL树的每个节点的构造

template<class key,class value>
struct avl_node
{int _bf;pair<key, value>_kv;avl_node<key, value>* _left;avl_node<key, value>* _right;avl_node<key, value>* _pre_node;avl_node(const pair<key,value>& kv):_kv(kv),_left(nullptr),_right(nullptr),_bf(0),_pre_node(nullptr){}
};

这里我们有三个指针，一个指向当前节点的左边，一个指向当前节点的右边，一个指向当前节点的上一个节点（父节点），然后我们用了一个pair键值对来存放key,value的值

template<class key,class value>
class AVLtree
{typedef avl_node<key, value> node;
public:AVLtree():_root(nullptr){}bool insert(const pair<key, value>& kv){if (_root == nullptr){_root = new node(kv);return true;}node* cur = _root;node* parent = nullptr;while (cur != nullptr){if (cur->_kv.first > kv.first){parent = cur;cur = cur->_left;}else if(cur->_kv.first<kv.first){parent = cur;cur = cur->_right;}else{return false;}}cur = new node(kv);if (parent->_kv.first < kv.first){parent->_right = cur;}else{parent->_left = cur;}cur->_pre_node = parent;while (parent != nullptr)//回溯跟新{if (parent->_left == cur){parent->_bf--;//插入在左边--}else{parent->_bf++;//插入在右边++}if (parent->_bf == 0){break;}if (parent->_bf == 1 || parent->_bf == -1)//快不平衡了{cur = parent;parent = parent->_pre_node;}else if (parent->_bf == -2 || parent->_bf == 2)//更新节点{if (parent->_bf == -2 && cur->_bf == -1){rotetR(parent);//这些调整下面会详细说明}else if (parent->_bf == 2 && cur->_bf == 1){rotetL(parent);}else if (parent->_bf == 2 && cur->_bf == -1){rotetRL(parent);}else if (parent->_bf == -2 && cur->_bf == 1){rotetLR(parent);}else{assert(false);}break;}else{assert(false);}}return true;}

这里插入逻辑还是和搜索二叉树一样，我们依次比较大小，当找到位置的时候，就需要向上更新平衡因子
好了接下来来说说旋转

AVL树的旋转

旋转的规则

  1. 保持搜索树的规则**(这是很重要的)**

  2. 让旋转的树从不满⾜变平衡，其次降低旋转树的⾼度
    旋转总共分为四种，左单旋/右单旋/左右双旋/右左双旋。

rotetR右单旋转

首先我们来画图看看，什么情况需要进行右旋转
这里我们用a,b,c来代表一个抽象的子树，这样的好处是可以一张图片概括所有的右单旋转的所有场景

在这里插入图片描述
下面就需要开始旋转了
在这里插入图片描述
具体步骤说明
在b⼦树中插⼊⼀个新结点，导致b⼦树的⾼度从h变成h+1，不断向上更新平衡因⼦，导致10的平
衡因⼦从-1变成-2，10为根的树左右⾼度差超过1，违反平衡规则。10为根的树左边太⾼了，需要
往右边旋转，控制两棵树的平衡。

旋转核⼼步骤，因为5 < c⼦树的值 < 10，将c变成10的左⼦树，10变成5的右⼦树，5变成这棵树新
的根，符合搜索树的规则，控制了平衡，同时这棵的⾼度恢复到了插⼊之前的h+2(加2是把5和10加进去算的），符合旋转原则。如果插⼊之前10整棵树的⼀个局部⼦树，旋转后不会再影响上⼀层，插⼊结束了。
下面来带入具体的数字来说明一下
情况1插入之前 a/b/c的高度是0
在这里插入图片描述
情况2插入之前a/b/c的高度是1
在这里插入图片描述
在这里插入图片描述
好了下面我们来看看代码是怎么实现的

右旋代码

这里面其实有很多的坑，不要看着简单，实际上要注意的点有点多，首先我们需要记录三个节点第一个是subl节点（以不平衡的节点为主的左边节点），然后sublr节点也就是subl的右边节点，pparent也就是（以不平衡节点为主的上一个节点)
其实不难发现旋转时要动的节点就那三个

void rotetR(node* parent)
{node* subl = parent->_left;node* sublr = subl->_right;node* Pparent = parent->_pre_node;首先我们让parent的左边指向sublrparent->_left = sublr;为什么这里需要判断一下sublr是不是为空呢，这是因为有可能出现一种情况一直插入的比根小，一直往左边插入，这时候就会形成一条像”/“形状的二叉树，这时sublr是空的，所以需要判断一下if (sublr != nullptr){不为空就sublr的上一个节点就是parentsublr->_pre_node = parent;}旋转完成之后subl就是新的根了，需要把右边->panrentsubl->_right = parent;parent->_pre_node = subl;同理，向上更新到这里就旋转完成了下面就需要判断旋转的点到底是不是root节点if (parent == _root){_root = subl;subl->_pre_node = nullptr;如果是就把上一个节点置为空}else{这里就体现了我们pparent的用法了if (Pparent->_left == parent){Pparent->_left = subl;}else{Pparent->_right = subl;}subl->_pre_node = Pparent;}更新节点完成之后更新相应改变的平衡因子subl->_bf = 0;parent->_bf = 0;
}

这就是右旋

左旋代码

同理右旋

void rotetL(node* parent)
{node* subr = parent->_right;node* subrl = subr->_left;node* pparent = parent->_pre_node;parent->_right = subrl;if (subrl != nullptr){subrl->_pre_node = parent;}subr->_left = parent;parent->_pre_node = subr;if (parent == _root){_root = subr;subr->_pre_node = nullptr;}else{if (pparent->_left == parent){pparent->_left = subr;}else{pparent->_right = subr;}subr->_pre_node = pparent;}subr->_bf = 0;parent->_bf = 0;
}

左右双旋

通过下面的图可以看到，左边⾼时，如果插⼊位置不是在a⼦树，⽽是插⼊在b⼦树，b⼦树⾼度从h变
成h+1，引发旋转，右单旋⽆法解决问题，右单旋后，我们的树依旧不平衡。右单旋解决的纯粹的左边
⾼，但是插⼊在b⼦树中，10为跟的⼦树不再是单纯的左边⾼，对于10是左边⾼，但是对于5是右边
⾼，需要⽤两次旋转才能解决，以5为旋转点进⾏⼀个左单旋，以10为旋转点进⾏⼀个右单旋，这棵树
这棵树就平衡了。
下面是a/b/c高度是0的情况
在这里插入图片描述
我们来看看旋转的过程
在这里插入图片描述
这样这颗树就平衡了
现在我们来看看a/b/c高度是1的情况
在这里插入图片描述
有了以上详细的例子我们来看看抽象的把a/b/c抽象成一个子树

下⾯我们将a/b/c⼦树抽象为⾼度h的AVL⼦树进⾏分析，另外我们需要把b⼦树的细节进⼀步展开为8和左⼦树⾼度为h-1的e和f⼦树，因为我们要对b的⽗亲5为旋转点进⾏左单旋，左单旋需要动b树中的左⼦树。b⼦树中新增结点的位置不同，平衡因⼦更新的细节也不同，通过观察8的平衡因⼦不同，这⾥我们要分三个场景讨论。

• 场景1：h >= 1时，新增结点插⼊在e⼦树，e⼦树⾼度从h-1变为h并不断更新8->5->10平衡因⼦，
引发旋转，其中8的平衡因⼦为-1，旋转后8和5平衡因⼦为0，10平衡因⼦为1。

• 场景2：h >= 1时，新增结点插⼊在f⼦树，f⼦树⾼度从h-1变为h并不断更新8->5->10平衡因⼦，引
发旋转，其中8的平衡因⼦为1，旋转后8和10平衡因⼦为0，5平衡因⼦为-1。

• 场景3：h == 0时，a/b/c都是空树，b⾃⼰就是⼀个新增结点，不断更新5->10平衡因⼦，引发旋
转，其中8的平衡因⼦为0，旋转后8和10和5平衡因⼦均为0。
像下面这样
在这里插入图片描述
首先我们讨论情况1
在这里插入图片描述
在这里插入图片描述
旋转完成之后，我们发现10的平衡因子是1(左边低右边高)
再来看看情况2
在这里插入图片描述
在这里插入图片描述
这时5的平衡因子是-1（右边低左边高）
最后一种情况类似于上面这种，就不做过多解释了
在这里插入图片描述

下面来看看代码

void rotetLR(node* parent)
{node* subl = parent->_left;node* sublr = subl->_right;int bf = sublr->_bf;rotetL(parent->_left);rotetR(parent);if (bf == 0)//对应第三种{parent->_bf = 0;subl->_bf = 0;sublr->_bf = 0;}else if (bf == 1)//对应第一种{subl->_bf = -1;parent->_bf = 0;sublr->_bf = 0;}else if (bf == -1)//对应第二种{parent->_bf = 1;subl->_bf = 0;sublr->_bf = 0;}else{assert(false);}
}

右左双旋

逻辑和上面一样

void rotetRL(node* parent)
{node* subr = parent->_right;node* subrl = subr->_left;int bf = subrl->_bf;rotetR(parent->_right);rotetL(parent);if (bf == 1){subr->_bf = 0;parent->_bf = -1;subrl->_bf = 0;}else if (bf == -1){parent->_bf = 0;subrl->_bf = 0;subr->_bf = 1;}else if (bf == 0){parent->_bf = 0;subrl->_bf = 0;subr->_bf = 0;}else{assert(false);}
}

AVL树的中序遍历

和普通搜索二叉树一样

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

怎么判断是不是AVL树

这里可以采用递归的方法来判断
先从根节点去递归检查高度，用高度差和平衡因子来检查，以此类推

int heigh(node* root)
{if (root == nullptr){return 0;}int lef = heigh(root->_left);int rig = heigh(root->_right);return lef > rig ? lef + 1 : rig + 1;
}
bool cheak_AVL(node* root)
{if (root == nullptr){return true;}int lef = heigh(root->_left);int rig = heigh(root->_right);int diff =rig-lef;if (abs(diff) >= 2){printf("高度异常");return false;}if (root->_bf != diff){printf("平衡因子异常");return false;}return cheak_AVL(root->_left) && cheak_AVL(root->_right);
}

源码

#pragma once
#include <utility>
#include<assert.h>
# include<iostream>
using namespace std;
template<class key,class value>
struct avl_node
{int _bf;pair<key, value>_kv;avl_node<key, value>* _left;avl_node<key, value>* _right;avl_node<key, value>* _pre_node;avl_node(const pair<key,value>& kv):_kv(kv),_left(nullptr),_right(nullptr),_bf(0),_pre_node(nullptr){}
};
template<class key,class value>
class AVLtree
{typedef avl_node<key, value> node;
public:AVLtree():_root(nullptr){}bool insert(const pair<key, value>& kv){if (_root == nullptr){_root = new node(kv);return true;}node* cur = _root;node* parent = nullptr;while (cur != nullptr){if (cur->_kv.first > kv.first){parent = cur;cur = cur->_left;}else if(cur->_kv.first<kv.first){parent = cur;cur = cur->_right;}else{return false;}}cur = new node(kv);if (parent->_kv.first < kv.first){parent->_right = cur;}else{parent->_left = cur;}cur->_pre_node = parent;while (parent != nullptr)//回溯{if (parent->_left == cur){parent->_bf--;}else{parent->_bf++;}if (parent->_bf == 0){break;}if (parent->_bf == 1 || parent->_bf == -1){cur = parent;parent = parent->_pre_node;}else if (parent->_bf == -2 || parent->_bf == 2)//更新节点{if (parent->_bf == -2 && cur->_bf == -1){rotetR(parent);}else if (parent->_bf == 2 && cur->_bf == 1){rotetL(parent);}else if (parent->_bf == 2 && cur->_bf == -1){rotetRL(parent);}else if (parent->_bf == -2 && cur->_bf == 1){rotetLR(parent);}else{assert(false);}break;}else{assert(false);}}return true;}void rotetR(node* parent){node* subl = parent->_left;node* sublr = subl->_right;node* Pparent = parent->_pre_node;parent->_left = sublr;if (sublr != nullptr){sublr->_pre_node = parent;}subl->_right = parent;parent->_pre_node = subl;if (parent == _root){_root = subl;subl->_pre_node = nullptr;}else{if (Pparent->_left == parent){Pparent->_left = subl;}else{Pparent->_right = subl;}subl->_pre_node = Pparent;}subl->_bf = 0;parent->_bf = 0;}void rotetL(node* parent){node* subr = parent->_right;node* subrl = subr->_left;node* pparent = parent->_pre_node;parent->_right = subrl;if (subrl != nullptr){subrl->_pre_node = parent;}subr->_left = parent;parent->_pre_node = subr;if (parent == _root){_root = subr;subr->_pre_node = nullptr;}else{if (pparent->_left == parent){pparent->_left = subr;}else{pparent->_right = subr;}subr->_pre_node = pparent;}subr->_bf = 0;parent->_bf = 0;}void rotetLR(node* parent){node* subl = parent->_left;node* sublr = subl->_right;int bf = sublr->_bf;rotetL(parent->_left);rotetR(parent);if (bf == 0){parent->_bf = 0;subl->_bf = 0;sublr->_bf = 0;}else if (bf == 1){subl->_bf = -1;parent->_bf = 0;sublr->_bf = 0;}else if (bf == -1){parent->_bf = 1;subl->_bf = 0;sublr->_bf = 0;}else{assert(false);}}void rotetRL(node* parent){node* subr = parent->_right;node* subrl = subr->_left;int bf = subrl->_bf;rotetR(parent->_right);rotetL(parent);if (bf == 1){subr->_bf = 0;parent->_bf = -1;subrl->_bf = 0;}else if (bf == -1){parent->_bf = 0;subrl->_bf = 0;subr->_bf = 1;}else if (bf == 0){parent->_bf = 0;subrl->_bf = 0;subr->_bf = 0;}else{assert(false);}}void inoder(){_InOrder(_root);}bool ck(){return cheak_AVL(_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 heigh(node* root){if (root == nullptr){return 0;}int lef = heigh(root->_left);int rig = heigh(root->_right);return lef > rig ? lef + 1 : rig + 1;}bool cheak_AVL(node* root){if (root == nullptr){return true;}int lef = heigh(root->_left);int rig = heigh(root->_right);int diff =rig-lef;if (abs(diff) >= 2){printf("高度异常");return false;}if (root->_bf != diff){printf("平衡因子异常");return false;}return cheak_AVL(root->_left) && cheak_AVL(root->_right);}node* _root;
};

http://www.ppmy.cn/ops/125941.html

相关文章

SpringBoot+Vue+Uniapp智能社区服务小程序系统(源码+lw+部署文档+讲解等)

SpringBoot+Vue+Uniapp智能社区服务小程序系统(源码+lw+部署文档+讲解等)

项目运行截图 技术框架 后端采用SpringBoot框架 Spring Boot 是一个用于快速开发基于 Spring 框架的应用程序的开源框架。它采用约定大于配置的理念&#xff0c;提供了一套默认的配置&#xff0c;让开发者可以更专注于业务逻辑而不是配置文件。Spring Boot 通过自动化配置和约…
阅读更多...
优化 webpack 的打包速度的优化

优化 webpack 的打包速度的优化

前端面试题包括ECMScript,TypeScript,Nodejs,React,Webgl,Threejs等还在整理中&#xff0c;在线地址前端面试题&#xff0c;源码地址大家多多支持才有动力给大家分享更多好的面试题。 优化 Webpack 的打包速度可以显著提升开发效率&#xff0c;尤其是在大型项目中。以下是一些…
阅读更多...
Go语言--快速入门

Go语言--快速入门

Go语言特点 我们先看一下简单的Go语言程序 package mainimport "fmt"func main() { // 错误&#xff0c;{ 不能在单独的行上fmt.Println("Hello, World!") }我们可以看到外型非常像我们的JAVA&#xff0c;但是不需要&#xff1b;作为结尾&#xff0c;…
阅读更多...
低代码可视化-uniapp商城首页小程序-代码生成器

低代码可视化-uniapp商城首页小程序-代码生成器

在设计一个小程序的首页时&#xff0c;包含轮播图、通知栏和商品列表这三个元素是非常常见且有效的布局方式。这样的设计既能够吸引用户的注意力&#xff0c;又能够高效地展示信息和商品。 轮播组件 小程序首页幻灯片通常位于小程序的顶部或显著位置&#xff0c;通过滑动屏幕可…
阅读更多...
使用tgz包下载安装clickhouse低版本

使用tgz包下载安装clickhouse低版本

1.下载安装包 官方下载地址&#xff1a;https://packages.clickhouse.com/tgz/stable 阿里云下载地址&#xff1a;clickhouse-tgz-stable安装包下载_开源镜像站-阿里云 共需要下载四个文件 clickhouse-common-static-20.3.10.75.tgz clickhouse-common-static-dbg-20.3.10.7…
阅读更多...
Java利用itextpdf实现pdf文件生成

Java利用itextpdf实现pdf文件生成

前言 最近公司让写一个数据页面生成pdf的功能&#xff0c;找了一些市面代码感觉都太麻烦&#xff0c;就自己综合性整合了一个便捷的工具类&#xff0c;开发只需简单组装数据直接调用即可快速生成pdf文件。望大家一起学习&#xff01;&#xff01;&#xff01; 代码获取方式&am…
阅读更多...
3.Linux中安装redis及环境搭建

3.Linux中安装redis及环境搭建

文章目录 1.在Ubuntu中安装redis2.在Centos中安装Redis 5(不建议&#xff0c;现在yum仓库已经停止维护)3.Ubuntu中安装mysql4.Ubuntu中安装java85.Ubuntu中启动Java程序6.环境搭建及介绍 大家好&#xff0c;我是晓星航。今天为大家带来的是 Linux中安装redis 相关的讲解&#x…
阅读更多...
slab 缓存以及slabtop 命令学习

slab 缓存以及slabtop 命令学习

一、slab 缓存介绍 1.1、什么是slab 缓存 SLAB缓存是Linux内核中用于优化内存分配和管理的一种机制&#xff0c;特别针对频繁分配和释放的固定大小的小对象。它是基于 通用内存分配器(如伙伴系统) 之上的一个中间层&#xff0c;旨在通过减少分配和释放小对象的开销、降低内存…
阅读更多...
最新文章

Copyright @ 2022~2023