【C++进阶】AVL树

0.前言

前面我们已经学习过二叉搜索树了,但如果我们是用二叉搜索树来封装map和set等关联式容器是有缺陷的,很可能会退化为单分支的情况,那样效率就极低了,那么有没有方法来弥补二叉搜索树的缺陷呢?

那么AVL树就出现了,通过AVL树的右单旋、左单旋、左右单旋,右左单旋等操作来防止二叉搜索树退化为单分支的情况出现。

因此,两位俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis在1962年发明了一种解决上述问题的方法:当向二叉搜索树中插入新结点后,如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整),即可降低树的高度,从而减少平均搜索长度。
AVL树也是以这两位大佬名字的首字母来命名的。

1.AVL树的概念

一棵AVL树或者是空树,或者是具有以下性质的二叉搜索树是AVL树:

  • 它的左右子树都是AVL树
  • 左右子树高度之差(简称平衡因子)的绝对值不超过1(-1/0/1)
     

我们这里使用的平衡因子是右子树高度 - 左子树高度。 

 

2.AVL树节点的定义

代码如下:

template<class K, class V>
struct AVLTreeNode
{AVLTreeNode<K, V>* _left;	//该节点的左孩子AVLTreeNode<K, V>* _right;	//该节点的右孩子AVLTreeNode<K, V>* _parent;	//该节点的双亲pair<K, V>  _kv;	//该节点的key和valueint _bf; //balance factor 平衡因子AVLTreeNode(const pair<K, V>& kv)	//该节点初始化:_left(nullptr)  , _right(nullptr), _parent(nullptr), _kv(kv)  , _bf(0){}
};

3.AVL树的插入

AVL树就是在二叉搜索树的基础上引入了平衡因子,因此AVL树也可以看成是二叉搜索树。那么
AVL树的插入过程可以分为两步:

  1. 按照二叉搜索树的方式插入新节点
  2. 调整节点的平衡因子
     

插入思路

 1.按照搜索树规则插入

2.更新插入节点的祖先节点的平衡因子

        a.插入父亲的右边,父亲的平衡因子--

        b.插入父亲的左边,父亲的平衡因子++

        c.父亲平衡因子 == 0, 父亲所在子树高度不变,不再继续往上更新。插入结束

        d.父亲平衡因子 == 1 or -1, 父亲所在子树高度变了,继续往上更新。

        e.父亲平衡因子 == 2 or -2, 父亲所在子树已经不平衡了,需要旋转处理。

更新中不可能出现其他值,插入之前树是AVL树,平衡因子要么是1 -1 0, ++ --

最多就是c/d/e三种情况。

 代码如下

	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--;}else{parent->_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);}break;}else{//理论上不会出现这种情况,但仍要判断,大佬都不能保证自己的代码没有bugassert(false);}}return true;}

4.AVL树的旋转

4.1 右单旋

插入新节点要插入较高左子树的左侧(左左)-》右单旋

图形解析:

 实现代码如下:

	void RotateR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;parent->_left = subLR;if (subLR)	//subLR有可能为空,不为空时才能调整subLR的父节点subLR->_parent = parent;subL->_right = parent;//parent不一定就是根节点,也可能是子树,所以要设置一个ppNode来标记parent的父节点Node* ppNode = parent->_parent;parent->_parent = subL;if (parent == _root){_root = subL;_root->_parent = nullptr;}else{if (ppNode->_left == parent){ppNode->_left = subL;}else{ppNode->_right = subL;}subL->_parent = ppNode;}subL->_bf = parent->_bf = 0;}

4.2 左单旋

插入新节点要插入较高右子树的右侧(右右)-》左单旋

图形解析:

 代码如下:

	void RotateL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;if (subRL)	//subRL有可能为空,不为空时才能调整subRL的父节点subRL->_parent = parent;subR->_left = parent;//parent不一定就是根节点,也可能是子树,所以要设置一个ppNode来标记parent的父节点Node* ppNode = parent->_parent;parent->_parent = subR;if (parent == _root){_root = subR;_root->_parent = nullptr;}else{if (ppNode->_left == parent){ppNode->_left = subR;}else{ppNode->_right = subR;}subR->_parent = ppNode;}subR->_bf = parent->_bf = 0;}

4.3 左右双旋

插入新节点要插入较高左子树的右侧(左右)-》左右双旋

图形解析:

对于插入的位置根据h的高度和插入的位置时的平衡因子出现的最终的结果可分为三种情况:

1.h == 0

        60自己就是新增节点。bf == 0

此时的平衡因子为,30 60 90节点都为0。

2.h > 0

        a.新增节点插入的是60的左子树中 bf == -1

此时的平衡因子为,30节点为0,90为0,60为1

        b.新增节点插入的是60的右子树中bf == 1

此时的平衡因子为,30节点为-1,90为0,60为0

代码如下:

 

	void RotateLR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;int bf = subLR->_bf;RotateL(parent->_left);RotateR(parent);if (bf == 0){subL->_bf = 0;subLR->_bf = 0;parent->_bf = 0;}else if (bf == -1){subL->_bf = 0;subLR->_bf = 0;parent->_bf = 1;}else if (bf == 1){subL->_bf = -1;subLR->_bf = 0;parent->_bf = 0;}else{//理论上不会出现的情况assert(false);}}

4.4 右左双旋

插入新节点要插入较高右子树的左侧(右左)-》右左双旋

与左右双旋类似

代码如下:

	void RotateRL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;int bf = subRL->_bf;RotateR(parent->_right);RotateL(parent);if (bf == 0){parent->_bf = 0;subRL->_bf = 0;subR->_bf = 0;}else if (bf == -1){parent->_bf = 0;subRL->_bf = 0;subR->_bf = 1;}else if (bf == 1){parent->_bf = -1;subRL->_bf = 0;subR->_bf = 0;}else{//理论上不会出现的情况assert(false);}}


总结
假如以pParent为根的子树不平衡,即pParent的平衡因子为2或者-2,分以下情况考虑
1. pParent的平衡因子为2,说明pParent的右子树高,设pParent的右子树的根为pSubR
当pSubR的平衡因子为1时,执行左单旋
当pSubR的平衡因子为-1时,执行右左双旋
2. pParent的平衡因子为-2,说明pParent的左子树高,设pParent的左子树的根为pSubL
当pSubL的平衡因子为-1是,执行右单旋
当pSubL的平衡因子为1时,执行左右双旋
旋转完成后,原pParent为根的子树个高度降低,已经平衡,不需要再向上更新。

 

5.AVL树的验证

5.1 验证其是否为二叉搜索树

给一个序列进行一次中序遍历,看是否有序,有序即为二叉搜索树。

void TestAVLTree1()
{int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };AVLTree<int, int> t1;for (auto e : a){t1.Insert({ e,e });}t1.InOrder();
}

5.2 验证其是否为平衡树

	bool _IsBalance(Node* root){if (root == nullptr){return true;}int leftHeight = _Height(root->_left);int rightHeight = _Height(root->_right);//不平衡if (abs(leftHeight - rightHeight) >= 2){cout << root->_kv.first << endl;return false;}//顺便检查一下平衡因子是否正确if (rightHeight - leftHeight != root->_bf){cout << root->_kv.first << endl;return false;}return _IsBalance(root->_left)&& _IsBalance(root->right);}

6.AVL树的删除(了解)

因为AVL树也是二叉搜索树,可按照二叉搜索树的方式将节点删除,然后再更新平衡因子,只不错与删除不同的时,删除节点后的平衡因子更新,最差情况下一直要调整到根节点的位置。

7.AVL树的性能

AVL树是一棵绝对平衡的二叉搜索树,其要求每个节点的左右子树高度差的绝对值都不超过1,这样可以保证查询时高效的时间复杂度,即logN。但是如果要对AVL树做一些结构修改的操作,性能非常低下,比如:插入时要维护其绝对平衡,旋转的次数比较多,更差的是在删除时,有可能一直要让旋转持续到根的位置。因此:如果需要一种查询高效且有序的数据结构,而且数据的个数为静态的(即不会改变),可以考虑AVL树,但一个结构经常修改,就不太适合。

 8.AVL树的整体模拟代码实现

#pragma once
#include<iostream>
using namespace std;
#include<assert.h>template<class K, class V>
struct AVLTreeNode
{AVLTreeNode<K, V>* _left;	//该节点的左孩子AVLTreeNode<K, V>* _right;	//该节点的右孩子AVLTreeNode<K, V>* _parent;	//该节点的双亲pair<K, V>  _kv;	//该节点的key和valueint _bf; //balance factor 平衡因子AVLTreeNode(const pair<K, V>& kv)	//该节点初始化:_left(nullptr)  , _right(nullptr), _parent(nullptr), _kv(kv)  , _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--;}else{parent->_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);}break;}else{//理论上不会出现这种情况,但仍要判断,大佬都不能保证自己的代码没有bugassert(false);}}return true;}void RotateR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;parent->_left = subLR;if (subLR)	//subLR有可能为空,不为空时才能调整subLR的父节点subLR->_parent = parent;subL->_right = parent;//parent不一定就是根节点,也可能是子树,所以要设置一个ppNode来标记parent的父节点Node* ppNode = parent->_parent;parent->_parent = subL;if (parent == _root){_root = subL;_root->_parent = nullptr;}else{if (ppNode->_left == parent){ppNode->_left = subL;}else{ppNode->_right = subL;}subL->_parent = ppNode;}subL->_bf = parent->_bf = 0;}void RotateL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;if (subRL)	//subRL有可能为空,不为空时才能调整subRL的父节点subRL->_parent = parent;subR->_left = parent;//parent不一定就是根节点,也可能是子树,所以要设置一个ppNode来标记parent的父节点Node* ppNode = parent->_parent;parent->_parent = subR;if (parent == _root){_root = subR;_root->_parent = nullptr;}else{if (ppNode->_left == parent){ppNode->_left = subR;}else{ppNode->_right = subR;}subR->_parent = ppNode;}subR->_bf = parent->_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 == 0){subL->_bf = 0;subLR->_bf = 0;parent->_bf = 0;}else if (bf == -1){subL->_bf = 0;subLR->_bf = 0;parent->_bf = 1;}else if (bf == 1){subL->_bf = -1;subLR->_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->_right);RotateL(parent);if (bf == 0){parent->_bf = 0;subRL->_bf = 0;subR->_bf = 0;}else if (bf == -1){parent->_bf = 0;subRL->_bf = 0;subR->_bf = 1;}else if (bf == 1){parent->_bf = -1;subRL->_bf = 0;subR->_bf = 0;}else{//理论上不会出现的情况assert(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;}void InOrder(){_InOrder(_root);cout << endl;}bool IsBalance(){return _IsBalance(_root);}int Height(){return _Height(_root);}int Size(){return _Size(_root);}
private:int _Size(Node* root){return root == nullptr ? 0 : _Size(root->_left) + _Size(root->_right) + 1;}int _Height(Node* root){if (root == nullptr){return 0;}return max(_Height(root->_left), _Height(root->_right)) + 1;}bool _IsBalance(Node* root){if (root == nullptr){return true;}int leftHeight = _Height(root->_left);int rightHeight = _Height(root->_right);//不平衡if (abs(leftHeight - rightHeight) >= 2){cout << root->_kv.first << endl;return false;}//顺便检查一下平衡因子是否正确if (rightHeight - leftHeight != root->_bf){cout << root->_kv.first << endl;return false;}return _IsBalance(root->_left)&& _IsBalance(root->_right);}void _InOrder(Node* root){if (root == nullptr){return;}_InOrder(root->_left);cout << root->_kv.first << ":" << root->_kv.second << endl;_InOrder(root->_right);}Node* _root = nullptr;
};void TestAVLTree1()
{int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };AVLTree<int, int> t1;for (auto e : a){t1.Insert({ e,e });}t1.InOrder();
}
void TestAVLTree2()
{int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };AVLTree<int, int> t1;for (auto e : a){t1.Insert({ e,e });}t1.InOrder();cout << t1.IsBalance() << endl;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/331458.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

【开源】多语言大型语言模型的革新:百亿参数模型超越千亿参数性能

大型人工智能模型&#xff0c;尤其是那些拥有千亿参数的模型&#xff0c;因其出色的商业应用表现而受到市场的青睐。但是&#xff0c;直接通过API使用这些模型可能会带来数据泄露的风险&#xff0c;尤其是当模型提供商如OpenAI等可能涉及数据隐私问题时。私有部署虽然是一个解决…

5.18 TCP机械臂模拟

#include <netinet/tcp.h>//包含TCP选项的头文件 #include <arpa/inet.h> #include <stdio.h> #include <stdlib.h> #include <unistd.h> #include <linux/input.h>//读取输入事件 #include <sys/types.h> #include <sys/stat.h&…

LeetCode700二叉搜索树中的搜索

题目描述 给定二叉搜索树&#xff08;BST&#xff09;的根节点 root 和一个整数值 val。你需要在 BST 中找到节点值等于 val 的节点。 返回以该节点为根的子树。 如果节点不存在&#xff0c;则返回 null 。 解析 最基本的二叉搜索树的应用&#xff0c;递归或者while循环都可以…

【FPGA】VGA显示文字、彩条、图片——基于DE2-115

文章目录 前言一、VGA概述1.1 简述1.2 管脚定义1.3 VGA显示原理1.4 VGA时序标准1.5 VGA 显示模式及相关参数 二、VGA显示自定义的汉字字符2.1 点阵汉字生成2.2 生成BMP文件2.3 生成txt文件2.4 实现效果 三、VGA显示条纹3.1 实现流程3.2 实现效果 四、VGA输出一幅彩色图像4.1 bm…

算法金 | Dask,一个超强的 python 库

本文来源公众号“算法金”&#xff0c;仅用于学术分享&#xff0c;侵权删&#xff0c;干货满满。 原文链接&#xff1a;Dask&#xff0c;一个超强的 python 库 1 Dask 概览 在数据科学和大数据处理的领域&#xff0c;高效处理海量数据一直是一项挑战。 为了应对这一挑战&am…

2024年5月26日 十二生肖 今日运势

小运播报&#xff1a;2024年5月26日&#xff0c;星期日&#xff0c;农历四月十九 &#xff08;甲辰年己巳月庚寅日&#xff09;&#xff0c;法定节假日。 红榜生肖&#xff1a;马、猪、狗 需要注意&#xff1a;牛、蛇、猴 喜神方位&#xff1a;西北方 财神方位&#xff1a;…

多线程事务

一、业务场景 我们在工作中经常会到往数据库里插入大量数据的工作&#xff0c;但是既需要保证数据的一致性&#xff0c;又要保证程序执行的效率。因此需要在多线程中使用事务&#xff0c;这样既可以保证数据的一致性&#xff0c;又能保证程序的执行效率。但是spring自带的Trans…

开关电源AC-DC(15W 3-18V可调)

简介: 该模块使用PI的TNY268PN电源芯片制作的开关电源,实现最大功率15W 3-18V可调输出(更改反馈电阻)隔离式反激电源; 简介:该模块使用PI的TNY268PN电源芯片制作的开关电源,实现最大功率15W 3-18V可调输出(更改反馈电阻,现电路图输出5V)隔离式反激电源; 一、产品简…

论文阅读--CLIPasso

让计算机把真实图片抽象成简笔画&#xff0c;这个任务很有挑战性&#xff0c;需要模型捕获最本质的特征 以往的工作是找了素描的数据集&#xff0c;而且抽象程度不够高&#xff0c;笔画是固定好的&#xff0c;素描对象的种类不多&#xff0c;使得最后模型的效果十分受限 之所以…

云计算和大数据处理

文章目录 1.云计算基础知识1.1 基本概念1.2 云计算分类 2.大数据处理基础知识2.1 基础知识2.3 大数据处理技术 1.云计算基础知识 1.1 基本概念 云计算是一种提供资源的网络&#xff0c;使用者可以随时获取“云”上的资源&#xff0c;按需求量使用&#xff0c;并且可以看成是无…

面试八股之JVM篇3.5——垃圾回收——G1垃圾回收器

&#x1f308;hello&#xff0c;你好鸭&#xff0c;我是Ethan&#xff0c;一名不断学习的码农&#xff0c;很高兴你能来阅读。 ✔️目前博客主要更新Java系列、项目案例、计算机必学四件套等。 &#x1f3c3;人生之义&#xff0c;在于追求&#xff0c;不在成败&#xff0c;勤通…

优先级队列(堆)的实现

1.什么是优先级队列 队列是一种先进先出(FIFO)的数据结构&#xff0c;但有些情况下&#xff0c;操作的数据可能带有优先级&#xff0c;一般出队 列时&#xff0c;可能需要优先级高的元素先出队列&#xff0c;该中场景下&#xff0c;使用队列显然不合适&#xff0c;比如&#x…

Python线程

Python线程 1. 进程和线程 先来了解下进程和线程。 类比&#xff1a; 一个工厂&#xff0c;至少有一个车间&#xff0c;一个车间中至少有一个工人&#xff0c;最终是工人在工作。 一个程序&#xff0c;至少有一个进程&#xff0c;一个进程中至少有一个线程&#xff0c;最终…

不靠后端,前端也能搞定接口!

嘿&#xff0c;前端开发达人们&#xff01;有个超酷的消息要告诉你们&#xff1a;MemFire Cloud来袭啦&#xff01;这个神奇的东东让你们不用依赖后端小伙伴们&#xff0c;也能妥妥地搞定 API 接口。是不是觉得有点不可思议&#xff1f;但是事实就是这样&#xff0c;让我们一起…

141.字符串:重复的字符串(力扣)

题目描述 代码解决 class Solution { public:// 计算字符串s的next数组&#xff0c;用于KMP算法void getNext(int *next, const string& s){int j 0; // j是前缀的长度next[0] 0; // 初始化next数组&#xff0c;第一个字符的next值为0for (int i 1; i < s.size(); …

OpenHarmony 实战开发——一文总结ACE代码框架

一、前言 ACE_Engine框架是OpenAtom OpenHarmony&#xff08;简称“OpenHarmony”&#xff09;的UI开发框架&#xff0c;为开发者提供在进行应用UI开发时所必需的各种组件&#xff0c;以及定义这些组件的属性、样式、事件及方法&#xff0c;通过这些组件可以方便进行OpenHarmo…

AUTOMATIC1111/stable-diffusion-webui/stable-diffusion-webui-v1.9.3

配置环境介绍 目前平台集成了 Stable Diffusion WebUI 的官方镜像&#xff0c;该镜像中整合如下资源&#xff1a; GpuMall智算云 | 省钱、好用、弹性。租GPU就上GpuMall,面向AI开发者的GPU云平台 Stable Diffusion WebUI版本&#xff1a;v1.9.3 Python版本&#xff1a;3.10.…

插件:NGUI

一、版本 安装完毕后重启一下即可&#xff0c;否则可能创建的UI元素不生效 二、使用 Label文字 1、创建Canvs 2、只有根节点的这些脚本全部展开才能鼠标右键创建UI元素 3、选择字体 Sprite图片 1、选择图集 2、选择图集中的精灵 Panel容器 用来装UI的容器&#xff0c;一般UI…

从 0 实现一个文件搜索工具 (Java 项目)

背景 各文件系统下, 都有提供文件查找的功能, 但是一般而言搜索速度很慢 本项目仿照 everything 工具, 实现本地文件的快速搜索 实现功能 选择指定本地目录, 根据输入的信息, 进行搜索, 显示指定目录下的匹配文件信息文件夹包含中文时, 支持汉语拼音搜索 (全拼 / 首字母匹配…

Boss说,搞个深色B端系统。敢要就敢搞,宁被累死,不被吓死。

老规矩&#xff0c;先上文字说服&#xff08;洗脑&#xff09;自己&#xff0c;再附案例。 深色系B端系统是指在企业级应用中&#xff0c;使用深色主题的后台管理系统。这种设计风格主要以暗色调为主&#xff0c;如黑色、深灰色等&#xff0c;与传统的亮色主题相比&#xff0c…