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.xdnf.cn/news/20466.html

如若内容造成侵权/违法违规/事实不符，请联系一条长河网进行投诉反馈，一经查实，立即删除！

相关文章

Java进阶四-异常,File

Java进阶四-异常,File

异常 概念&#xff1a;代表程序出现的问题。 目的&#xff1a;程序出现了异常我们应该如何处理。 最高父类&#xff1a;Exception 异常分为两类 编译时异常&#xff1a;没有继承RuntimeException的异常,直接继承与Exception,编译阶段就会错误提示。运行时异常:RuntimeExc…
阅读更多...
向量数据库FAISS之四：向量检索和 FAISS

向量数据库FAISS之四：向量检索和 FAISS

来自 YouTube 1.相似度搜索的传统方法(Jaccard, w-shingling, Levenshtein) 1.Jaccard 距离 公式 Jaccard ( A , B ) 1 − ∣ A ∩ B ∣ ∣ A ∪ B ∣ \text{Jaccard}(A, B) 1 - \frac{|A \cap B|}{|A \cup B|} Jaccard(A,B)1−∣A∪B∣∣A∩B∣​ 其中&#xff0c; A 和 …
阅读更多...
Stata17最新保姆级安装教程【附安装包】

Stata17最新保姆级安装教程【附安装包】

文章目录 Stata介绍 Stata下载 Stata安装步骤 Stata介绍 Stata 是一套提供其使用者数据分析、数据管理以及绘制专业图表的完整及整合性统计软件。它提供许许多多功能&#xff0c;包含线性混合模型、均衡重复反复及多项式普罗比模式等。 Stata下载 Stata 64位下载链接&…
阅读更多...
jenkins离线安装插件

jenkins离线安装插件

Jenkins 在线安装插件失败 报错&#xff1a; Caused: java.io.IOException: Failed to load https://updates.jenkins.io/download/plugins/login-theme/244.vd67c77f0c4c8/login-theme.hpi to /var/jenkins_home/plugins/login-theme.jpi.tmpat hudson.model.UpdateCenter$Up…
阅读更多...
人工智能学习——前言

人工智能学习——前言

一、概论理解 首先何为人工智能&#xff1f;简单一句人话就是&#xff1a;人工操纵搭建出来的智能学习模型 那我们要用它干什么&#xff1f;简单一句话就是&#xff1a;我们给出指令 ——> 得到想要的结果 最简单的生活例子来看&#xff1a;就好比小狗&#xff0c;我们让它…
阅读更多...
C++11——异常

C++11——异常

1.异常概念 异常是一种处理错误的方式&#xff0c;当一个函数发现自己无法处理的错误时就会抛出异常&#xff0c;让函数的调用者处理这个错误 throw&#xff1a;当出现问题时&#xff0c;程序会抛出一个异常&#xff0c;通过 throw 来完成catch&#xff1a;catch 关键字捕获异…
阅读更多...
腾讯：将LLM排序能力迁移至BERT

腾讯：将LLM排序能力迁移至BERT

&#x1f4d6;标题&#xff1a;Best Practices for Distilling Large Language Models into BERT for Web Search Ranking &#x1f310;来源&#xff1a;arXiv, 2411.04539 &#x1f31f;摘要 &#x1f538;最近的研究强调了大型语言模型&#xff08;LLM&#xff09;作为零样…
阅读更多...
unity 打包WebGL打开后Input无法输入中文，在手机端无法调用输入法（使用WebGLInput）

unity 打包WebGL打开后Input无法输入中文，在手机端无法调用输入法（使用WebGLInput）

成果展示 1、只是在电脑上运行时 使用TexMeshPro-InputField组件就可以输入中文了 2.不仅在电脑上运行&#xff0c;还需要在移动端运行 这个时候就需要使用WebGLInput插件&#xff0c;连接里有测试demo 1、下载后把WebGLSupport.unitypackage 导入到工程里 2、给input添加两…
阅读更多...
服务器上部署并启动 Go 语言框架 **GoZero** 的项目

服务器上部署并启动 Go 语言框架 **GoZero** 的项目

要在服务器上部署并启动 Go 语言框架 **GoZero** 的项目&#xff0c;下面是一步步的操作指南&#xff1a; ### 1. 安装 Go 语言环境 首先&#xff0c;确保你的服务器上已安装 Go 语言。如果还没有安装&#xff0c;可以通过以下步骤进行安装&#xff1a; #### 1.1 安装 Go 语…
阅读更多...
如何通过统一权限管理打破异构系统的安全屏障

如何通过统一权限管理打破异构系统的安全屏障

企业在运营过程中面临着众多异构系统的整合挑战&#xff0c;这些异构系统由于其不同的技术架构、数据格式和安全机制等&#xff0c;给信息管理带来了诸多挑战。其中&#xff0c;“信息孤岛”问题尤为突出&#xff0c;而异构环境下的统一授权管理系统则成为解决这一问题的关键。…
阅读更多...
【IDEA】插件篇（JClassLib）

【IDEA】插件篇（JClassLib）

一、JClassLib 1、概述 jclasslib 字节码编辑器是一个可视化已编译Java类文件和包含的字节码的工具。 项目地址&#xff1a;https://github.com/ingokegel/jclasslib 其他反编译工具&#xff1a;javap、arthas 2、安装 IntelliJ IDEA -> Preferences -> Plugins&am…
阅读更多...
机器学习阶段学习Day31

机器学习阶段学习Day31

KNN分类算法 KNN算法原理 根据K个邻居样本来判断当前样本属于哪个类别&#xff1a;K个最相似邻居中大多数所属类别即为当前样本的类别。但是对于数据量巨大或者高纬度的数据样本不太合适&#xff0c;数据量大的数据样本需要进行大量计算&#xff0c;而高纬度数据计算距离不具…
阅读更多...
深入理解前端路由

深入理解前端路由

目录 前言1. 什么是路由2. Vue Router 的基础2.1 安装 Vue Router2.2 创建路由器2.3 在应用中使用 Vue Router 3. 路由切换与编程式导航3.1 声明式导航3.2 编程式导航 4. 子路由&#xff1a;结构化的路由管理4.1 子路由的定义4.2 子路由的渲染 5. 高级用法&#xff1a;路由守卫…
阅读更多...
【UGUI】Unity 游戏开发：背包系统初始化克隆道具

【UGUI】Unity 游戏开发：背包系统初始化克隆道具

在游戏开发中&#xff0c;背包系统是一个非常常见的功能模块。它允许玩家收集、管理和使用各种道具。今天&#xff0c;我们将通过一个简单的示例来学习如何在 Unity 中初始化一个背包系统。我们将使用 Unity 2021.3.7 版本&#xff0c;并结合 C# 脚本来实现这一功能。 1. 场景…
阅读更多...
grafana+prometheus+windows_exporter实现windows进程资源占用的监控

grafana+prometheus+windows_exporter实现windows进程资源占用的监控

grafanaprometheuswindows_exporter实现windows进程资源占用的监控TOC 一、 管理端搭建&#xff0c;采用windows版本的grafanaprometheus 管理端安装部署不做本文终端&#xff0c;简单讲解一下&#xff0c;此处采用msi的grafana安装包&#xff0c;和免安装版本的prometheus 1…
阅读更多...
ElementUI之给el-table实现搜索功能

ElementUI之给el-table实现搜索功能

1&#xff0c;有一个表格 <el-table:data"tableData"borderstyle"width: 100%"><el-table-columnprop"date"label"日期"width"180"></el-table-column><el-table-columnprop"name"label&quo…
阅读更多...
Chrome 浏览器 131 版本开发者工具（DevTools）更新内容

Chrome 浏览器 131 版本开发者工具（DevTools）更新内容

Chrome 浏览器 131 版本开发者工具&#xff08;DevTools&#xff09;更新内容 一、使用 Gemini 调试 CSS Chrome DevTools 现在推出了一个新的实验性 AI 辅助面板&#xff0c;可以与 Gemini 聊天并获得帮助来调试 CSS。 在 Elements 面板中&#xff0c;右键点击一个元素并选…
阅读更多...
Ubuntu20.04 Rk3588 交叉编译ffmpeg7.0

Ubuntu20.04 Rk3588 交叉编译ffmpeg7.0

firefly 公司出的rk3588的设备&#xff0c;其中已经安装了gcc 交叉编译工具&#xff0c;系统版本是Ubuntu20.04。 使用Ubuntu20.04 交叉编译ffmpeg_ubuntu下配置ffmpeg交叉编译器为arm-linux-gnueabihf-gcc-CSDN博客文章浏览阅读541次。ubuntu20.04 交叉编译ffmpeg_ubuntu下配…
阅读更多...
蓝桥杯第22场小白入门赛2~5题

蓝桥杯第22场小白入门赛2~5题

这场比赛开打第二题就理解错意思了&#xff0c;还以为只能用3个消除和5个消除其中一种呢&#xff0c;结果就是死活a不过去&#xff0c;第三题根本读不懂题意&#xff0c;这蓝桥杯的题面我只能说出的是一言难尽啊。。第四题写出来一点但是后来知道是错了&#xff0c;不会正解&am…
阅读更多...
sagemaker中使用pytorch框架的DLC训练和部署cifar图像分类任务

sagemaker中使用pytorch框架的DLC训练和部署cifar图像分类任务

参考资料 https://github.com/aws/amazon-sagemaker-examples/blob/main/sagemaker-python-sdk/pytorch_cnn_cifar10/pytorch_local_mode_cifar10.ipynbhttps://sagemaker.readthedocs.io/en/stable/frameworks/pytorch/using_pytorch.html 获取训练数据 # s3://zhaojiew-sa…
阅读更多...
最新文章

Copyright @ 2022~2023