C++实现AVL树

文章目录

    • 一、平衡树的优势
    • 二、二叉平衡搜索树的节点定义
    • 三、二叉搜索树的插入
      • 3.1 寻找插入位置
      • 3.2 开始判定平衡因子，平衡因子有变就开始旋转
        • 3.2.1 左旋的情况
        • 3.2.2 左旋代码（一定要考虑平衡因子为2或者-2的节点是否有父节点）
        • 3.2.2 右旋的情况
        • 3.2.3 左右双旋的情况（细分为3种情况）
          • 3.2.3.1 以下为例3的左子树为h时
          • 3.2.3.2 以下为例3的右子树为h时
          • 3.2.3.3 如果3的右子树为空时
          • 3.2.3.4 代码演示
        • 3.2.4 右左双旋的情况（一样细分三种情况）
    • 四、平衡树的检验（是否平衡）
      • 4.1 先从高度方面检验
      • 4.2 再看树的节点个树
      • 4.3 最后看树的平衡因子
    • 五、全部源码

在这里插入图片描述


先赞后看，养成习惯！！！^ _ ^<3 ❤️ ❤️ ❤️
码字不易，大家的支持就是我坚持下去的动力。点赞后不要忘了关注我哦！
所属专栏:C++进阶

在这里插入图片描述

一、平衡树的优势

经过了解二叉搜索树的性质之后，我们也发现了它极大的缺陷，如果数字基本上都是趋于有序的情况下，那么查找效率非常低下，时间复杂度为O（n），与顺序表的查找一样，因此我们引出了二叉平衡搜索树（AVL树），该树的优势在于能够保证根节点左右子树的高度差的绝对值小于等于1，这就很好保证了查找效率O（logn），如下图就是二叉平衡搜索树的样子。
在这里插入图片描述

二、二叉平衡搜索树的节点定义

由于二叉平衡搜索树需要对节点进行旋转，我们这里引入了父节点的指针，还有平衡因子（保证节点处于平衡状态）
在这里插入图片描述

三、二叉搜索树的插入

3.1 寻找插入位置

首先插入顺序还是和二叉搜索树大差不差，有区别的位置是需要判断平衡因子是否大于1，大于1就要开始旋转了（这里就略过，需要看具体操作可以看二叉搜索树那一章）
在这里插入图片描述

3.2 开始判定平衡因子，平衡因子有变就开始旋转

3.2.1 左旋的情况

在这里插入图片描述

在这里插入图片描述

3.2.2 左旋代码（一定要考虑平衡因子为2或者-2的节点是否有父节点）

在这里插入图片描述

3.2.2 右旋的情况

在这里插入图片描述
在这里插入图片描述

3.2.3 左右双旋的情况（细分为3种情况）
3.2.3.1 以下为例3的左子树为h时

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
一定要注意平衡因子的变化

3.2.3.2 以下为例3的右子树为h时

在这里插入图片描述
在这里插入图片描述

3.2.3.3 如果3的右子树为空时

那么平衡因子都为0，其他变化都是一样的

3.2.3.4 代码演示

在这里插入图片描述

3.2.4 右左双旋的情况（一样细分三种情况）

下面只讲解一种情况其他都是一样的就是平衡因子发生改变

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

四、平衡树的检验（是否平衡）

4.1 先从高度方面检验

在这里插入图片描述

4.2 再看树的节点个树

在这里插入图片描述

4.3 最后看树的平衡因子

在这里插入图片描述

五、全部源码

#pragma once
#include<iostream>
#include<vector>
#include<assert.h>
//#include <utility> 
using namespace std;
template<class K,class V>
struct AVLTreeNode
{
	AVLTreeNode<K,V>* _left;
	AVLTreeNode<K, V>* _right;
	AVLTreeNode<K, V>* _parent;
	int _bf;
	pair<K, V> _kv;

	//构造函数初始化列表
	AVLTreeNode(const pair<K, V> kv)
		:_left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _bf(0)
		, _kv(kv)
	{}
};

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->_left = cur;
		else
			parent->_right = cur;

		cur->_parent = parent;

		while (parent)
		{
			if (cur == parent->_left)
			{
				parent->_bf--;//左为减
			}
			else
			{
				parent->_bf++;
			}

			if (parent->_bf == 1 || parent->_bf == -1)
			{
				cur = cur->_parent;
				parent = parent->_parent;
			}
			else if (parent->_bf == 2 || parent->_bf == -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)
				{
					RotateLR(parent);
				}
				else
				{
					RotateRL(parent);
				}
				break;
			}
		}
		return true;
	}

	void RotateL(Node* parent)
	{
		Node* subR = parent->_right;
		Node* subRL = subR->_left;

		if (subRL)
			subRL->_parent = parent;

		parent->_right = subRL;
		Node* pp = parent->_parent;
		subR->_left = parent;

		if (pp == nullptr)
		{
			parent->_parent = subR;
			_root = subR;
			subR->_parent = nullptr;
		}
		else
		{
			if (pp->_left == parent)
			{
				parent->_parent = subR;
				subR->_parent = pp;
				pp->_left = subR;
			}
			else if (pp->_right == parent)
			{
				parent->_parent = subR;
				pp->_right = subR;
				subR->_parent = pp;
			}
			else
			{
				assert(false);
			}
		}
		parent->_bf = subR->_bf = 0;
	}

	void RotateR(Node* parent)
	{
		Node* subL = parent->_left;
		Node* subLR = subL->_right;

		if (subLR)
			subLR->_parent = parent;

		parent->_left = subLR;
		Node* pp = parent->_parent;
		subL->_right = parent;

		if (pp == nullptr)
		{
			_root = subL;
			subL->_parent = nullptr;
		}
		else
		{
			if (pp->_left == parent)
			{
				parent->_parent = subL;
				subL->_parent = pp->_left;
			}
			else if (pp->_right = parent)
			{
				parent->_parent = subL;
				subL->_parent = pp->_right;
			}
			else
			{
				assert(false);
			}
		}
		parent->_bf = subL->_bf = 0;
	}

	void RotateLR(Node* parent)
	{
		Node* subL = parent->_left;
		Node* subLR = subL->_right;

		int bf = subLR->_bf;
		RotateL(subL);
		RotateR(parent);

		if (bf == -1)
		{
			parent->_bf = -1;
			subLR->_bf = 0;
			subL->_bf = 0;
		}
		else if (bf == 1)
		{
			parent->_bf = 0;
			subLR->_bf = 0;
			subL->_bf = 1;
		}
		else if (bf == 0)
		{
			parent->_bf = subLR->_bf = subL->_bf = 0;
		}
		else
		{
			assert(false);
		}
	}

	void RotateRL(Node* parent)
	{
		Node* subR = parent->_right;
		Node* subRL = subR->_left;

		int bf = subRL->_bf;

		RotateR(subR);
		RotateL(parent);

		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 if (bf == 0)
		{
			parent->_bf = subRL->_bf = subR->_bf = 0;
		}
		else
		{
			assert(false);
		}
	}

	void _Inorder()
	{
		Inorder(_root);
	}

	void Inorder(Node* root)
	{
		if (root == nullptr)
			return;

		Inorder(root->_left);
		cout << root->_kv.first << endl;
		Inorder(root->_right);
	}

	Node* Find(const pair<K,V> kv)
	{
		Node* cur = _root;
		while (cur)
		{
			if (cur->_kv.first > kv.first)
			{
				cur = cur->_left;
			}
			else if (cur->_kv.first < kv.first)
			{
				cur = cur->_right;
			}
			else
			{
				return cur;
			}
		}
		return nullptr;
	}

	size_t _Height()//树的高度
	{
		return Height(_root);
	}

	size_t 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;
	}

	//数的节点个树
	size_t _Size()
	{
		return Size(_root);
	}

	size_t Size(Node* root)
	{
		if (root == nullptr)
			return 0;

		return Size(root->left) + Size(root->right) + 1;
	}

	//判断树是否平衡
	bool _Isbalance()
	{
		return Isbalance(_root);
	}



	bool Isbalance(Node* root)
	{
		if (root == nullptr)
			return false;

		int leftHeight = Height(root->_left);
		int rightHeight = Height(root->_right);
		return abs(leftHeight - rightHeight) < 2
			&& Isbalance(root->_left) && Isbalance(root->_right);//检查完当前树的高度
		//然后就检查当前树的左子树和右子树是否符合要求
	}

private:
	Node* _root = nullptr;

};

在这里插入图片描述

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

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

mmdetection模型使用mmdeploy部署在windows上的c++部署流程【详细全面版】

mmdetection模型使用mmdeploy部署在windows上的c++部署流程【详细全面版】

0. 前置说明： 该文档适用于：已经使用mmdetection训练好了模型，并且完成了模型转换。要进行模型部署了。 1. 概述 MMDeploy 定义的模型部署流程，如下图所示： 模型转换【待撰写，敬请期待…】 主要功能是：把输入的模型格式，转换为目标设备的推理引擎所要求的模型格式…
阅读更多...
2440LED点灯、K1~K6按键、24401中断、2440时钟

2440LED点灯、K1~K6按键、24401中断、2440时钟

我要成为嵌入式高手之4月12日ARM第七天&#xff01;&#xff01; ———————————————————————————— 2440GPIO GPIO&#xff1a;通用目的输入输出 LED 要把GPBCON初始化 地址是固定的&#xff0c;可以当做无符号int型 控制所有灯就需要初始化GPBCO…
阅读更多...
还原matlab编辑器窗口和主窗口分开的问题

还原matlab编辑器窗口和主窗口分开的问题

问题 matlab不知道早点的&#xff0c;点击运行后会弹出新的窗口&#xff0c;咋整都恢复不了 解决方案 首先&#xff0c;在编辑器窗口下&#xff0c;按ctrlshiftD&#xff0c;此时编辑器窗口和主窗口就合并了&#xff0c;问题解决。
阅读更多...
Andriod设置背景颜色简单教学

Andriod设置背景颜色简单教学

首先&#xff0c;打开Android studio的程序应用&#xff0c;找到File&#xff0c;然后点击Settings. 第二步&#xff0c;弹出窗口,点击Appearance,进入Background image... 第三步&#xff0c;选择本地文件夹的图片 选择一张自己合适的图片设为该界面的背景图&#xff0c;完成…
阅读更多...
PyQt5结合Yolo框架打包python为exe文件完整流程

PyQt5结合Yolo框架打包python为exe文件完整流程

一、准备 1.安装 pyinstaller pip install pyinstaller 更新&#xff08;初次安装忽略&#xff09; pip install --upgrade pyinstaller 2.安装 auto-py-to-exe 安装 pip install auto-py-to-exe 打开工具 auto-py-to-exe.exe auto-py-to-exe 可视化转换工具&#xff1…
阅读更多...
LeetCode 2924.找到冠军 II：脑筋急转弯——只关心入度

LeetCode 2924.找到冠军 II：脑筋急转弯——只关心入度

【LetMeFly】2924.找到冠军 II&#xff1a;脑筋急转弯——只关心入度 力扣题目链接&#xff1a;https://leetcode.cn/problems/find-champion-ii/ 一场比赛中共有 n 支队伍&#xff0c;按从 0 到 n - 1 编号。每支队伍也是 有向无环图&#xff08;DAG&#xff09; 上的一个节…
阅读更多...
QT助手翻译【QT 5.14】 -----QPushButton

QT助手翻译【QT 5.14】 -----QPushButton

目录 1 属性 2 公共职能 3 重新实现的公共功能 4 公用插槽 5 受保护的功能 6 保护方法 7 详细说明 1 属性 自动默认值&#xff1a;bool 此属性保存按钮是否为自动默认按钮 如果此属性设置为true&#xff0c;则该按钮为自动默认按钮。 在某些GUI样式中&a…
阅读更多...
std::stringstream

std::stringstream

std::stringstream 是 C 标准库中的一个类&#xff0c;用于对字符串进行输入输出操作&#xff0c;类似于文件流&#xff08;std::ifstream 和 std::ofstream&#xff09;。它允许你像使用 std::cin 和 std::cout 一样使用字符串。 std::stringstream 可以将字符串作为输入源&am…
阅读更多...
基于8B/10BGT收发器的PHY层设计（1）

基于8B/10BGT收发器的PHY层设计（1）

一、PHY层简介 PHY层&#xff08;Physical Layer&#xff09;是OSI模型中最低的一层&#xff0c;也是最基本的一层&#xff0c;PHY是物理接口收发器&#xff0c;它实现物理层。包括MII/GMII&#xff08;介质独立接口&#xff09;子层、PCS&#xff08;物理编码子层&#xff09…
阅读更多...
N皇后问题（DFS解决）

N皇后问题（DFS解决）

文章目录 一、题目分析二、对角线判断&#xff08;分两种&#xff09;三、代码演示 先赞后看&#xff0c;养成习惯&#xff01;&#xff01;&#xff01;^ _ ^<3 ❤️ ❤️ ❤️ 码字不易&#xff0c;大家的支持就是我坚持下去的动力。点赞后不要忘了关注我哦&#xff01; 一…
阅读更多...
4.14学习总结

4.14学习总结

java网络编程 一.网络编程的概念和原理 概念: 网络编程是指通过计算机网络进行数据传输和通信的编程技术。在网络编程中&#xff0c;可以实现不同计算机之间的数据交互和通信&#xff0c;从而实现分布式系统、客户端-服务器应用等。 Java网络编程基于TCP/IP协议栈进行通信&…
阅读更多...
软件测试基础知识点汇总

软件测试基础知识点汇总

1、衡量一个优秀软件的维度 质量模型&#xff1a;功能性、性能、兼容性、易用性、可靠性、安全、可维护性、可移植性。 2、软件测试流程 需求评审、计划编写、用例设计、用例执行、缺陷管理、测试报告 3、用例设计编写格式 用例编号、用例标题、项目/模块、优先级、前置条…
阅读更多...
数学公式编辑器mathtype2024特别版含激活序列

数学公式编辑器mathtype2024特别版含激活序列

MathType 7是一款专业的数学公式编辑工具&#xff0c;广泛应用于教育教学、科研机构、工程学、物理学、化学等多个领域。它支持各种数学符号、公式、方程式、矩阵、分数、上下标等&#xff0c;几乎涵盖了所有的数学元素&#xff0c;可以帮助用户快速、方便地创建高质量的数学公…
阅读更多...
[图像处理] MFC OnMouseMove()绘制ROI矩形时的闪烁问题

[图像处理] MFC OnMouseMove()绘制ROI矩形时的闪烁问题

文章目录 问题对策代码完整工程 结果使用Picture控件的RedrawWindow()的效果使用Dialog的RedrawWindow()的效果使用Picture控件的RedrawWindow()&#xff0c;ROI绘制到图像外的效果 结论 问题 最近想通过业余时间&#xff0c;写一个简单的图像处理软件&#xff0c;一点点学习图…
阅读更多...
WEB前端-笔记

WEB前端-笔记

目录 一、字体 二、背景图片 三、显示方式 四、类型转换 五、相对定位 六、绝对定位 七、固定定位 八、Index 九、粘性定位 十、内边距 十一、外边距 十二、边框 十三、盒子尺寸计算问题 十四、清楚默认样式 十五、内容溢出 十六、外边距的尺寸与坍塌 十七、行…
阅读更多...
YOLOv8 测试 5：Linux 中 Docker 部署 YOLOv8，Python 封装 API 接口，base64 图片处理

YOLOv8 测试 5：Linux 中 Docker 部署 YOLOv8，Python 封装 API 接口，base64 图片处理

一、前言 记录时间 [2024-4-14] 系列文章简摘&#xff1a; Docker 学习笔记&#xff08;二&#xff09;&#xff1a;在 Linux 中部署 Docker&#xff08;Centos7 下安装 docker、环境配置&#xff0c;以及镜像简单使用&#xff09; API 接口简单使用&#xff08;二&#xff09;…
阅读更多...
树莓集团构建特色化3+3+1数字产业园运营体系

树莓集团构建特色化3+3+1数字产业园运营体系

树莓集团构建的331数字产业园运营体系&#xff0c;是以三大服务体系、三大服务平台以及智慧园区服务为核心&#xff0c;为企业提供全生命周期服务&#xff0c;实现第五代数字化产业园区&#xff08;基地、中心&#xff09;的并网化运营。 这一运营体系的构建&#xff0c;标志着…
阅读更多...
【MATLAB源码-第50期】基于simulink的BPSK调制解调仿真，输出误码率。

【MATLAB源码-第50期】基于simulink的BPSK调制解调仿真，输出误码率。

操作环境&#xff1a; MATLAB 2022a 1、算法描述 1. Bernoulli Binary: 这个模块生成伯努利二进制随机数&#xff0c;即0或1。这些数字表示要传输的原始数字信息。 2. Unipolar to Bipolar Converter: 此模块将伯努利二进制数据从0和1转换为-1和1&#xff0c;这是BPSK调制的…
阅读更多...
硬件开发相关的流程文件介绍

硬件开发相关的流程文件介绍

学习目的&#xff1a;前面文章有简要介绍硬件开发的基本过程&#xff0c;本文会细分硬件开发的流程&#xff0c;然后分作5个步骤&#xff0c;详细介绍开发全过程&#xff0c;包括立项-实施项目-软件开发-测试-验收 这几个过程&#xff0c;然后&#xff0c;再分解对每一个步骤进…
阅读更多...
poi-tl的使用（通俗易懂，全面，内含动态表格实现 包会！！）

poi-tl的使用（通俗易懂，全面，内含动态表格实现 包会！！）

最近在做项目时候有一个关于解析Html文件&#xff0c;然后将解析的数据转化成word的需求&#xff0c;经过调研&#xff0c;使用poi-tl来实现这个需求&#xff0c;自己学习花费了一些时间&#xff0c;现在将这期间的经验总结起来&#xff0c;让大家可以快速入门 poi-tl的介绍 …
阅读更多...
最新文章

Copyright @ 2022~2023