C++ AVL树

devtools/2024/10/22 8:36:49/

一.概念

        二叉搜索树在左右子树较为平衡的情况下搜索效率为O(log n)，但是如果数据是接近有序插入二叉树中的结构就会是一颗左斜树或者右斜树的状态。

为了提升效率俄罗斯数学家 G. M. Adelson-Velsky和E. M. Landis在1962年共同发明的。其思想为当二叉树中插入新节点后，如果每个节点的左右子树高度之差的绝对值超过1，那就会对此树进行调整（左旋、右旋、右左旋、左右旋），降低树的高度，从而减少平均搜索的长度。

二. AVL树的实现

2.1 AVL的节点定义

template<class K,class V>
struct AVLTreeNode
{AVLTreeNode<K, V>* _left;AVLTreeNode<K, V>* _right;AVLTreeNode<K, V>* _parent;pair<K, V> _kv;int _bf;//平衡因子AVLTreeNode(const pair<K, V>& kv):_left(nullptr), _right(nullptr), _parent(nullptr), _kv(kv),_bf(0){}
};

AVL树采用了key/value的模型而且采用了三叉结构，不仅有左右节点的指针，还有一个指向父节点的指针，其中_bf是平衡因子用来记录自己右子树高度减去左子树高度的差值。

当平衡因子为0时，左树和右树完全平衡

当平衡因子为1时，右树高度 - 左树高度 = 1  右树高

当平衡因子为1时，右树高度 - 左树高度 = -1 左树高

2.2 节点的插入

（1）将新节点插入到树中
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;/*cur从根节点开始向下遍历，比较键值对中的key值，如果插入节点的key值大于当前遍历的节点，那么就往左走，否则往右走*/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;cur->_parent = parent;//节点插入完毕后将新插入的节点的父指针指向它的父节点}else{parent->_left = cur;cur->_parent = parent;}//搜索树的插入，下面的代码需要管控树的平衡}

（2）AVL树的调整

        以上的操作和普通的二叉搜索树的插入操作是基本一致的，但是AVL树就特殊在可以自动调整二叉树，将二叉树变成一个左右树的高度差不超过1的状态。

        这里是平衡因子从当前节点的父节点开始逐个向上更新。跟新平衡因子后会出现三种不同的情况：

1. 平衡因子等于0，插入该节点后左树和右树处于一个平衡状态。

2. 平衡因子等于 1 或者 -1 ，插入该节点后，左右两树的高度差为1（问题不大）

3. 平衡因子等于2 或者 -2，插入该节点，左右两树的高度差为2（需要调整）

对于平衡因子为2或-2时，一共有四种情况需要我们去探究

（1）AVL的左旋

        当右边插入一个节点后，使得自己的祖父节点的祖父节点的平衡因子变成了2，这时就需要进行左旋，左旋的思想是将根节点往左子树的左边摁。如图所示，因为30的右子树所有的节点都是大于30的，包括subRL，现在将subRL变成30的右子树，然后将30连接为60左树的根节点。以上操作位左旋，这样的操作即将低了子树的高度又没有破坏二叉树的规则。代码如下所示

	void RotateL(Node* parent)//左单旋{Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;subR->_left = parent;//基础逻辑Node* PPNode = parent->_parent;//记录父节点parent->_parent = subR;if (subRL){subRL->_left = parent;}//处理父节点_parentif (_root == parent)//如果_root就是整棵树的根节点只需要把新节点的父节点置空即可{_root = subR;subR->_parent = nullptr;}else//如果_root只是一个子树的根，那么还需要将新节点链接上_root的父节点，在这里在旋转之前就要记录好根节点的父节点 (PPNode){if (PPNode->_left == parent){PPNode->_left = subR;}else{PPNode->_right = subR;}subR->_parent = PPNode;}//更新平衡因子parent->_bf = subR->_bf = 0;}

（2）AVL的右旋

当左树的左子树插入一个节点时，将祖先节点的平衡因子变成了-2，这时需要进行右旋的操作（将祖父节点30，往左子树20的右边摁）。如图所示， 因为左子树的所有元素都是比30小的，所以将subLR连接到30的左节点，最后将20的右指针连接到祖父节点30上，就完成了右旋的操作。

void RotateR(Node* parent)//右单旋 
{Node* subL = parent->_left;Node* subLR = subL->_right;//Node* PPNode = parent->_parent;不要在这里记录祖父节点，放置祖父节点为空parent->_left = subLR;if(subLR)subLR->_parent = parent;Node* PPNode = parent->_parent;subL->_right = parent;parent->_parent = subL;if (_root == parent)//根节点为parent{_root = subL;subL->_parent = nullptr;}else//修改的只是子树的根{if (parent == PPNode->_left){PPNode->_left = subL;}else{PPNode->_right = subL;}subL->_parent = PPNode;}subL->_bf = parent->_bf = 0;
}

（3）AVL的右左旋

假设 在60的右边 插入一个节点，这时我们是无法单靠左旋或者右旋来平衡树的，我们需要先把90右旋到60 的右边，将30左旋到60的左边这样就可以完成平衡树中元素的操作。如上图所示

 假设 在60的左边 插入一个节点，我们需要先把90右旋到60 的右边，将30左旋到60的左边这样就可以完成平衡树中元素的操作。如上图所示

其中在右左旋转完成后，我们需要更新平衡因子，那么新节点插入到到60的左边和右边会产生平衡因子不同的情况，所以我们需要提前存储30平衡因子的值，在旋转完毕后进行针对性的更新平衡因子。

右左单旋的代码如下所示

void RotateRL(Node* parent)//右左双旋
{Node* subR = parent->_right;Node* subRL = subR->_left;int bf = subRL->_bf;//记录60的平衡因子，不然会被单旋修改RotateR(parent->_right);RotateL(parent);if (bf == 0)//subrl自己就是新增{parent->_bf = subR->_bf = subRL->_bf = 0;}else if (bf == -1){//在subrl的左子树插入新节点parent->_bf = subRL->_bf = 0;subR->_bf = 1;}else if (bf == 1){//在subrl的右子树插入新节点subR->_bf = subRL->_bf = 0;parent->_bf = -1;}else{assert(false);}
}

（3）AVL的左右旋

 

假设在90子节点的右边插入节点，那么 先对60进行左旋，再对30进行右旋，完事了更新平衡因子。平衡因子和右左旋后一样有三种情况需要进行分类讨论，代码如下所示

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 = subL->_bf = 0;parent->_bf = 1;}else if (bf == 1){subLR->_bf = parent->_bf = 0;subL->_bf = -1;}else if (bf == 0){subL->_bf = subLR->_bf = parent->_bf = 0;}
}

三.整体代码

#pragma once
#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;int _bf;//平衡因子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;cur->_parent = parent;//节点插入完毕后将新插入的节点的父指针指向它的父节点}else{parent->_left = cur;cur->_parent = parent;}//搜索树的插入，下面的代码需要管控树的平衡//平衡因子的计算方式是 右树的高度减去左树的高度//新增节点只会影响到自己的祖先节点，但是不一定会影响到自己的全部祖先节点//子树的高度不变就不会向上影响到祖先，反之亦然//新增节点在左子树。父亲平衡因子需要自减，在右数父亲的平衡因子自加/*对于平衡因子的变化总结	1 更新后父亲的平衡因子为0证明父亲所在子树的高度不变，不需要再向上更新，插入结束。ps:在插入节点前，父亲的平衡因子等于1或者-1，节点是一边高一边低的，新插入的节点填上了低的那一边2 父亲的平衡因子更新以后等于1 或者 -1 证明父亲所在的子树高度变化了，需要向上更新ps:在插入节点前，父亲的平衡因子等于0，父亲两边的节点是一样高的，新插入的节点改变了父节点平衡因子的高度3 父亲平衡因子更新后等于2 或者 -2，父亲所在的子树违反了规则，需要旋转调整 */while (parent){if (cur == parent->_left){parent->_bf--;}else{parent->_bf++;}if (parent->_bf == 0){break;}//AVL树插入最简单的情况else if (parent->_bf == 1 || parent->_bf == -1){cur = parent;parent = parent->_parent;}else if (parent->_bf == 2 || parent->_bf == -2)//旋转调整{/*旋转调整的原则1. 左右均衡一些2. 保持搜索树的规则*/if (parent->_bf == 2 && cur->_bf == 1)//单纯是右边高所以是左单旋{RotateL(parent);}else if (parent->_bf == -2 && cur->_bf == -1)//单纯是左边高所以是右单旋{RotateR(parent);}else if (parent->_bf == 2 && cur->_bf == -1)//双旋情况下的父节点的右边高，子树的左边高，需要先右旋再左旋{RotateRL(parent);}break;}else{assert(false);}}return true;}void RotateR(Node* parent)//右单旋 {Node* subL = parent->_left;Node* subLR = subL->_right;//Node* PPNode = parent->_parent;不要在这里记录祖父节点，放置祖父节点为空parent->_left = subLR;if(subLR)subLR->_parent = parent;Node* PPNode = parent->_parent;subL->_right = parent;parent->_parent = subL;if (_root == parent)//根节点为parent{_root = subL;subL->_parent = nullptr;}else//修改的只是子树的根{if (parent == PPNode->_left){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;subR->_left = parent;//基础逻辑Node* PPNode = parent->_parent;//记录父节点parent->_parent = subR;if (subRL){subRL->_left = parent;}//处理父节点_parentif (_root == parent)//如果_root就是整棵树的根节点只需要把新节点的父节点置空即可{_root = subR;subR->_parent = nullptr;}else//如果_root只是一个子树的根，那么还需要将新节点链接上_root的父节点，在这里在旋转之前就要记录好根节点的父节点 (PPNode){if (PPNode->_left == parent){PPNode->_left = subR;}else{PPNode->_right = subR;}subR->_parent = PPNode;}//更新平衡因子parent->_bf = subR->_bf = 0;}void RotateRL(Node* parent)//右左双旋{Node* subR = parent->_right;Node* subRL = subR->_left;int bf = subRL->_bf;RotateR(parent->_right);RotateL(parent);if (bf == 0)//subrl自己就是新增{parent->_bf = subR->_bf = subRL->_bf = 0;}else if (bf == -1){//在subrl的左子树插入新节点parent->_bf = subRL->_bf = 0;subR->_bf = 1;}else if (bf == 1){//在subrl的右子树插入新节点subR->_bf = subRL->_bf = 0;parent->_bf = -1;}else{assert(false);}}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 = subL->_bf = 0;parent->_bf = 1;}else if (bf == 1){subLR->_bf = parent->_bf = 0;subL->_bf = -1;}else if (bf == 0){subL->_bf = subLR->_bf = parent->_bf = 0;}}void _InOrder(Node* root){if (root == nullptr){return;}_InOrder(root->_left);cout << root->_kv.first << " ";_InOrder(root->_right);}void InOrder(){_InOrder(_root);cout << endl;}int _Height(Node* root){if (root == nullptr)return 0;int leftHeight = _Height(root->_left);int rightHeight = _Height(root->_right);return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;}bool IsBalance(Node* root){return _IsBalance(_root);}bool _IsBalance(Node* root){if (root == nullptr)return true;int leftHeight = _Height(root->_lefft);int rightHeight = _Height(root->_right);if (rightHeight - leftHeight!=root->_bf){cout << root->_kv.first << "异常" << endl;return false;}return abs(rightHeight - leftHeight) < 2&& _IsBalance(root->_left)&& _IsBalance(root->_right);}
private:Node* _root=nullptr;
};


http://www.ppmy.cn/devtools/87657.html

相关文章

netstat 详解

netstat 详解

优质博文&#xff1a;IT-BLOG-CN 一、netstat参数 参数说明-a 或–all显示所有连线中的Socket-A <网络类型>或–<网络类型> 列出该网络类型连线中的相关地址-c或–continuous持续列出网络状态-C或–cache显示路由器配置的快取信息-e或–extend显示网络其他相关信…
阅读更多...
Python爬虫入门02：Fiddler下载使用教程

Python爬虫入门02：Fiddler下载使用教程

文章目录 手机抓包全攻略&#xff1a;Fiddler 工具深度解析引言Fiddler 工具简介为什么选择 Fiddler&#xff1f; 安装与配置 Fiddler步骤一&#xff1a;下载与安装步骤二&#xff1a;配置浏览器代理步骤三&#xff1a;安装 HTTPS 证书 配置手机以使用 Fiddler步骤一&#xff1…
阅读更多...
Mybatis与Mybatis-plus配置控制台打印完整带参数SQL语句

Mybatis与Mybatis-plus配置控制台打印完整带参数SQL语句

Mybatis-plus的sql打印 application.yaml中。Mybatis把第一行换成mybatis mybatis-plus:configuration:log-impl: org.apache.ibatis.logging.stdout.StdOutImpl Mybatis的SQL打印亦或者是 application中增加 logging:level:com:sky:mapper: debugservice: infocontroller…
阅读更多...
Mybatis注解

Mybatis注解

目录 1. Select 2. Insert 3. Update 4. Delete 5. Results 6. Param 7. One和 Many MyBatis 是一个持久层框架&#xff0c;支持通过 XML 或注解的方式来配置 SQL 映射。使用 MyBatis 注解可以更简洁地配置 SQL 语句&#xff0c;使代码更加清晰。以下是一些常用的 MyBatis 注解…
阅读更多...
pip日常使用指南（windows版）

pip日常使用指南（windows版）

一、官方途径 参考资源 pip 官方文档Python 包索引 (PyPI) 二、pip常用命令 pip安装包&#xff1a; pip install package_name #例如 pip install requests #安装特定版本 pip install requests2.25.1pip升级包: 可以使用 --upgrade 选项&#xff1a; pip install --upg…
阅读更多...
C语言 数组

C语言 数组

目录 数组初始化 数组越界 数组作为函数参数 数组初始化 数组的初始化&#xff1a;数组分一维二维等都需要对相应的数组进行初始化&#xff0c;在创建数组的同时给数组的内容一些合理初始值&#xff08;初始化&#xff09;。 数组在创建的时候如果想不指定数组的确定的大小就得…
阅读更多...
Windows图形界面(GUI)-MFC-C/C++ - Dialog

Windows图形界面(GUI)-MFC-C/C++ - Dialog

公开视频 -> 链接点击跳转公开课程博客首页 -> ​​​链接点击跳转博客主页 目录 Dialog 创建对话框模板 设置对话框属性 创建对话框对象 对话框生命周期 示例代码 Dialog 创建对话框模板 流程 打开资源视图&#xff1a;在Visual Studio中&#xff0c;右键点击资…
阅读更多...
【前端 11】初探DOM

【前端 11】初探DOM

JavaScript 对象 - DOM 初探 在Web开发中&#xff0c;DOM&#xff08;Document Object Model&#xff0c;文档对象模型&#xff09;是一个至关重要的概念。它不仅仅是一个API&#xff0c;更是Web页面与JavaScript代码之间的桥梁&#xff0c;允许开发者通过编程的方式动态地访问…
阅读更多...
最新文章

Copyright @ 2022~2023