C++AVL平衡树

1.AVL平衡树节点定义

每一个节点都配左右孩子和父节点，以及平衡因子和其所对应的值。

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

2.AVL树的插入

每次插入新的节点就要更新平衡因子，要看插入的是那一边，左右会对应不同的情况，如果插入位置的父节点平衡因子变为0就说明插入的是低的那一边，说明达到了平衡，不用先上调整。

代码：

	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);}break;}else{assert(false);}}return true;}

3.左单旋

	void RotateL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_right;parent->_right = subRL;if (subRL)subRL->_parent = parent;Node* Parent = parent->_parent;subR->_left = parent;parent->_parent = subR;if (Parent){_root = subR;subR->_parent = nullptr;}else{if (Parent->_left == parent)Parent->_left = subR;elseParent->_right = subR;}subR->_parent = Parent;}

4.右单旋

	void RotateR1(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 (parent == _root){_root = subL;subL->_parent = nullptr;}else{if (pParent->_left == parent){pParent->_left = subL;}else{pParent->_right = subL;}subL->_parent = pParent;}subL->_bf = 0;parent->_bf = 0;}

5.左右双旋

那里插入新节点，那么父节点会成为最后稳定的根(自己总结的)

场景一：h==0，a/b/c都是空树，b自己就是新增节点，但是如果直接按照右旋来处理就会发现还是不可以，所以要先变成单旋情况，也就是一边纯粹高，就是根因子为2，子为1，或者正负全反过来，所以先把以5为根进行左单旋，这样就变成一边高，然后再进行右单旋，这样就平衡了。

场景2：h>=1,新节点插入在f子树，这时要以5为根，进行左旋，变成一边纯粹高，然后再右旋就行。 

场景3：新增节点插入在e子树，也是先左旋再右旋，而向右旋再左旋是在右子树插入时。 

总结：根据前面可以知道，每次新插入节点的父节点最后都会变成根，并且其父节点和父节点的父节点都会在其左右俩边，并且平衡因子也只有三种情况，也就是说可以根据插入节点的父节点的平衡因子判断最后AVL树的形状，平衡因子=1就是在右边插入，-1就是左边插入，0就是场景1。

代码示例：

先右再左，这里else是防止出现意外而设置。

void RotateRL(Node* parent)
{Node* subR = parent->_right;Node* subRL = subR->_left;int bf = subRL->_bf;RotateR(parent->_right);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 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);}
}

6.AVL平衡树的验证

1.验证是否为搜索二叉树

2.每个节点子树高度的绝对值是否超过1

代码示例：

这里用递归去获取子树高度，最后再比较俩颗子树谁大，大的加一结果为树的高度。

	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;}int _Size(Node* root){if (root == nullptr)return 0;return _Size(root->_left) + _Size(root->_right) + 1;}bool _IsBalanceTree(Node* root){// 空树也是AVL树if (nullptr == root)return true;// 计算pRoot结点的平衡因子：即pRoot左右子树的高度差int leftHeight = _Height(root->_left);int rightHeight = _Height(root->_right);int diff = rightHeight - leftHeight;// 如果计算出的平衡因子与pRoot的平衡因子不相等，或者// pRoot平衡因子的绝对值超过1，则一定不是AVL树if (abs(diff) >= 2){cout << root->_kv.first << "高度差异常" << endl;return false;}if (root->_bf != diff){cout << root->_kv.first << "平衡因子异常" << endl;return false;}// pRoot的左和右如果都是AVL树，则该树一定是AVL树return _IsBalanceTree(root->_left) && _IsBalanceTree(root->_right);}

总代码：

#define _CRT_SECURE_NO_WARNINGS 1
#include<vector>
#include"AVLTree.h"void TestAVLTree1()
{AVLTree<int, int> t;// 常规的测试用例int a[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };// 特殊的带有双旋场景的测试用例//int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };for (auto e : a){t.Insert({ e, e });}t.InOrder();cout << t.IsBalanceTree() << endl;
}// 插入一堆随机值，测试平衡，顺便测试一下高度和性能等
void TestAVLTree2()
{const int N = 1000000;vector<int> v;v.reserve(N);srand(time(0));for (size_t i = 0; i < N; i++){v.push_back(rand() + i);}size_t begin2 = clock();AVLTree<int, int> t;for (auto e : v){t.Insert(make_pair(e, e));}size_t end2 = clock();cout << "Insert:" << end2 - begin2 << endl;cout << t.IsBalanceTree() << endl;cout << "Height:" << t.Height() << endl;cout << "Size:" << t.Size() << endl;size_t begin1 = clock();// 确定在的值for (auto e : v){t.Find(e);}// 随机值/*for (size_t i = 0; i < N; i++){t.Find((rand() + i));}*/size_t end1 = clock();cout << "Find:" << end1 - begin1 << endl;
}int main()
{TestAVLTree2();return 0;
}

AVLTree.h

#pragma once#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);}break;}else{assert(false);}}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 (parent == _root){_root = subL;subL->_parent = nullptr;}else{if (pParent->_left == parent){pParent->_left = subL;}else{pParent->_right = subL;}subL->_parent = pParent;}subL->_bf = 0;parent->_bf = 0;}void RotateL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;if (subRL)subRL->_parent = parent;Node* parentParent = parent->_parent;subR->_left = parent;parent->_parent = subR;if (parentParent == nullptr){_root = subR;subR->_parent = nullptr;}else{if (parent == parentParent->_left){parentParent->_left = subR;}else{parentParent->_right = subR;}subR->_parent = parentParent;}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->_right);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;}int Height(){return _Height(_root);}int Size(){return _Size(_root);}bool IsBalanceTree(){return _IsBalanceTree(_root);}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: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 0;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 0;return _Size(root->_left) + _Size(root->_right) + 1;}bool _IsBalanceTree(Node* root){// 空树也是AVL树if (nullptr == root)return true;// 计算pRoot结点的平衡因子：即pRoot左右子树的高度差int leftHeight = _Height(root->_left);int rightHeight = _Height(root->_right);int diff = rightHeight - leftHeight;// 如果计算出的平衡因子与pRoot的平衡因子不相等，或者// pRoot平衡因子的绝对值超过1，则一定不是AVL树if (abs(diff) >= 2){cout << root->_kv.first << "高度差异常" << endl;return false;}if (root->_bf != diff){cout << root->_kv.first << "平衡因子异常" << endl;return false;}// pRoot的左和右如果都是AVL树，则该树一定是AVL树return _IsBalanceTree(root->_left) && _IsBalanceTree(root->_right);}
private:Node* _root = nullptr;
};

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

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

相关文章

Vue3 pinia使用

Vue3 pinia使用

Pinia 是一个现代的状态管理库&#xff0c;专为 Vue 3 设计。它提供了一种简单、直观的方式来管理应用中的全局状态 (就是不同组件都希望去共享的一些变量,函数等)。Pinia 的设计灵感来自于 Vuex&#xff08;Vue 2 的状态管理库&#xff09;&#xff0c;但进行了许多改进&#…
阅读更多...
PHP开发全新UI多语言多商户跨境商城源码、支持一键铺货、一键下单

PHP开发全新UI多语言多商户跨境商城源码、支持一键铺货、一键下单

商家可在平台产品库选品&#xff0c;一键铺货到自己商店&#xff0c;用户下单后&#xff0c;商家提交订单给平台&#xff0c;扣除商家供货价所需余额&#xff0c;提交后由平台发货&#xff0c;收货后订单金额结算给商家. 源码开源完整&#xff0c;一切能跑通的逻辑流程都可以二…
阅读更多...
移动应用开发：使用Android Studio 实现登录页与注册页跳转

移动应用开发：使用Android Studio 实现登录页与注册页跳转

文章目录 前期一&#xff0c;添加UI控件触发跳转二&#xff0c;编写LoginActivity活动代码三&#xff0c;运行程序查看效果 前期 需创建两个活动页面&#xff0c;登录页和注册页&#xff0c;可参考&#xff1a;《Android Studio实现简易登录页》《Android Studio实现简易注册页…
阅读更多...
【东莞石碣】戴尔R740服务器维修raid硬盘问题

【东莞石碣】戴尔R740服务器维修raid硬盘问题

1&#xff1a;石碣某塑料工厂下午报修一台戴尔R740服务器硬盘故障&#xff0c;催的还比较着急。 2&#xff1a;工程师经过跟用户确认故障的问题以及故障服务器型号和故障硬盘型号&#xff0c;产品和配件确认好后&#xff0c;公司仓库确认有该款硬盘现货&#xff0c;DELL 12T S…
阅读更多...
Inpaint-Web：纯浏览器端实现的开源图像处理工具

Inpaint-Web：纯浏览器端实现的开源图像处理工具

之前在刷短视频的时候&#xff0c;经常看到一些情侣在景区拍照&#xff0c;结果被路人“抢镜”。有时男朋友会拿出手机&#xff0c;帮忙把那些路人“P”掉&#xff0c;简直是既贴心又有趣。最近我在逛 GitHub 时&#xff0c;发现了一个可以在浏览器端删除照片中部分内容的纯前端…
阅读更多...
IDEA2023 SpringBoot整合Web开发（二）

IDEA2023 SpringBoot整合Web开发（二）

一、SpringBoot介绍 由Pivotal团队提供的全新框架&#xff0c;其设计目的是用来简化Spring应用的初始搭建以及开发过程。该框架使用了特定的方式来进行配置&#xff0c;从而使开发人员不再需要定义样板化的配置。SpringBoot提供了一种新的编程范式&#xff0c;可以更加快速便捷…
阅读更多...
技术速递｜Microsoft.Extensions.VectorData 预览版简介

技术速递｜Microsoft.Extensions.VectorData 预览版简介

作者&#xff1a;Luis Quintanilla - 项目经理 排版&#xff1a;Alan Wang 我们很高兴推出 Microsoft.Extensions.VectorData.Abstractions 库&#xff0c;该库现已提供预览版。 正如 Microsoft.Extensions.AI 库为使用 AI 服务提供了一个统一层一样&#xff0c;此包为 .NET 生…
阅读更多...
React解决保存less文件后会自动生成css文件的方法

React解决保存less文件后会自动生成css文件的方法

背景&#xff1a;在项目中使用了less&#xff0c;用的是vscode中esay less插件&#xff0c;但在每次保存.less文件时&#xff0c;都会在对应的同级文件夹内生成一个.css文件&#xff0c;如何避免这样的情况呢&#xff1f; 解决办法&#xff1a;在同级目录下的.vscode文件夹&…
阅读更多...
初级数据结构——栈与队列的互相实现

初级数据结构——栈与队列的互相实现

目录 前言一、用栈实现队列操作&#xff1a;c代码模版经典例题 二、用队列实现栈操作&#xff1a;c代码模版经典例题 三、总结四、结语 前言 通过我之前的作品已经初步理解了栈和队列的数据结构&#xff0c;这期我们来学习如何实现这两个数据结构的互相转换。在计算机科学中&a…
阅读更多...
Qt的一个基本用户登录界面编写|| 从0搭建QT的信号与槽的应用案例 ||Qt样式表的应用

Qt的一个基本用户登录界面编写|| 从0搭建QT的信号与槽的应用案例 ||Qt样式表的应用

目录 1.新建1个qt项目&#xff0c;基类选中QWidget 2.ui文件布局 3.头文件 3.1 explicit的作用 具体解释 示例 4.cpp源文件 5.信号与槽的应用 6.qt实现效果 7.qt样式表的应用 1.新建1个qt项目&#xff0c;基类选中QWidget 2.ui文件布局 3.头文件 #ifndef WIDADMINLO…
阅读更多...
【Apache Paimon】-- 2 -- 核心特性 （0.9.0）

【Apache Paimon】-- 2 -- 核心特性 （0.9.0）

目录 1、实时更新 1.1、实时大批量更新 1.2、支持定义合并引擎 1.3、支持定义更新日志生成器 2、海量数据追加处理 2.1、append table 2.2、快速查询 3、数据湖功能&#xff08;类比&#xff1a;hudi、iceberg、delta&#xff09; 3.1、支持 ACID 事务 3.2、支持 Time…
阅读更多...
webpack配置

webpack配置

4-3vue-loader测试_哔哩哔哩_bilibili 一.新建文件夹vue_todo&#xff0c;vscode打开 二.ctrl打开终端&#xff0c;输入npm init -y&#xff0c;快速生成一个默认的package.json文件 之后左边出现项目初始化文件package.json 三.接下来需要webpack完成打包&#xff0c;所以安装…
阅读更多...
5.STM32之通信接口《精讲》之USART通信---实验串口接收程序

5.STM32之通信接口《精讲》之USART通信---实验串口接收程序

根据上节&#xff0c;我们一已经完成了串口发送程序的代码&#xff0c;并且深入的解析探索了串口的原理&#xff0c;接下来&#xff0c;Whappy小编将带领大家进入串口接收程序的探索与实验&#xff0c;并将结合上一节串口发送一起来完成串口的发送和接收实验。 上来两张图 上图…
阅读更多...
leetcode 扫描线专题 06-leetcode.836 rectangle-overlap 力扣.836 矩形重叠

leetcode 扫描线专题 06-leetcode.836 rectangle-overlap 力扣.836 矩形重叠

题目 矩形以列表 [x1, y1, x2, y2] 的形式表示&#xff0c;其中 (x1, y1) 为左下角的坐标&#xff0c;(x2, y2) 是右上角的坐标。 矩形的上下边平行于 x 轴&#xff0c;左右边平行于 y 轴。 如果相交的面积为 正 &#xff0c;则称两矩形重叠。 需要明确的是&#xff0c;只在…
阅读更多...
ASP.NET MVC宠物商城系统

ASP.NET MVC宠物商城系统

该系统采用B/S架构&#xff0c;使用C#编程语言进行开发&#xff0c;以ASP.NET MVC框架为基础&#xff0c;以Visual Studio 2019为开发工具&#xff0c;数据库采用SQL Server进行保存数据。系统主要功能包括登录注册、宠物展示、个人中心、我的订单、购物车、用户管理、宠物类别…
阅读更多...
最优化方法_罚函数法例题

最优化方法_罚函数法例题

1 外点罚函数 算法1 外点罚函数法 给定初点&#xff0c;初始罚因子,放大系数&#xff0c;允许误差&#xff0c;置k1。以为初始点&#xff0c;求解无约束问题得最优解。如果,则停止计算&#xff0c;为约束问题的近似最优解&#xff1b;否 则&#xff0c;增大罚因子&#xff0c;令…
阅读更多...
python调用MySql保姆级教程（包会的）

python调用MySql保姆级教程（包会的）

目录 一、下载MySql 二、安装MySql 三、验证MySql是否OK 1、MySQL控制台验证 2、命令提示符cmd窗口验证 四、Python调用MySql 4.1 安装pysql 4.2 使用pysql 4.2.1、连接数据库服务器并且创建数据库和表 4.2.2 、将人脸识别考勤系统识别到的数据自动填入到数据库的表单中…
阅读更多...
【鸿蒙生态崛起，开发者有哪些机遇与挑战？】HarmonyOS NEXT 引领数字化未来

【鸿蒙生态崛起，开发者有哪些机遇与挑战？】HarmonyOS NEXT 引领数字化未来

文章目录 前言一、HarmonyOS NEXT 特点与升级二、全面突破操作系统核心技术三、鸿蒙生态全面守护用户隐私四、鸿蒙生态的崛起与开发者机遇五、全新鸿蒙生态引领数字化未来小结 前言 鸿蒙系统不断发展&#xff0c;有与安卓、iOS 形成三足鼎立之势&#xff0c;且其在智能手机、智…
阅读更多...
ssh无法连接Ubuntu

ssh无法连接Ubuntu

试了多次ssh都无法连接&#xff0c;明明可以上网 网卡、防火墙、端口都没有问题&#xff0c;就是连接不上 结果是这个版本Ubuntu镜像默认没有安装ssh服务 安装SSH服务&#xff1a;apt-get install openssh-server 开启SSH服务&#xff1a;/etc/init.d/ssh start 就可以连接…
阅读更多...
基于Java Springboot外卖平台系统

基于Java Springboot外卖平台系统

一、作品包含 源码数据库设计文档万字PPT全套环境和工具资源部署教程 二、项目技术 前端技术&#xff1a;Html、Css、Js、Vue、Element-ui 数据库&#xff1a;MySQL 后端技术&#xff1a;Java、Spring Boot、MyBatis 三、运行环境 开发工具&#xff1a;IDEA/eclipse 数…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023