C++数据结构——AVL树

目录

一、引言

1.1 二叉搜索树

1.2 二叉搜索树的缺陷 

1.3 AVL数的引入

二、AVL树结点的定义

三、AVL树的操作

3.1 插入

3.1.1 基本步骤

3.1.2 平衡因子的调整

3.2 旋转操作(重点!)

3.2.1 右单旋

3.2.2 左单旋

3.2.3 左右双旋

3.2.4 右左双旋

3.3 插入

3.4 计算高度

3.5 计算结点数量 

3.6 检查是否平衡 

3.7 树的遍历(中序)

3.8 树的查找

四、树的检验


一、引言

1.1 二叉搜索树

二叉搜索树又称二叉排序树,它或者是一棵空树,或者是具有以下性质的二叉树:
1.若它的左子树不为空,则左子树上所有节点的值都小于根节点的值
2.若它的右子树不为空,则右子树上所有节点的值都大于根节点的值
3.它的左右子树也分别为二叉搜索树

二叉搜索树严格上不可以出现两个或以上相等的数字。
平均来说,二叉搜索树能极大地加速我们的搜索过程,如果需要检索n个数,理论上,二叉搜索树可能只需要检索log(n+1)次,如果 n=1000,二叉搜索树只需要检索9次即可。

1.2 二叉搜索树的缺陷 

当插入数据完美递增或递减时,二叉搜索树会出现其不可避免的问题:

一旦出现这种情况,二叉搜索树能发挥的价值就很小了。

1.3 AVL数的引入

考虑到上述因素,数学家想到了使用平衡因子的做法,当左右子树的高度差超过某个值时,就进行某种操作,使他们重新平衡,这样就出现了AVL树:

在开始写AVL树的代码时,我们要明确一点,平衡因子的值是我们人为规定的,其等于右子树的高度减左子树的高度

二、AVL树结点的定义

template<class T>
struct AVLTreeNode
{
	T val;
	AVLTreeNode<T>* _pRight;//右结点
	AVLTreeNode<T>* _pLeft;//左结点
	AVLTreeNode<T>* _pParent;//父亲结点
	int _bf;//平衡因子
	AVLTreeNode(T data) 
		:val(data), _right(nullptr), 
		_left(nullptr), _parent(nullptr), _bf(0)
	{};
};

三、AVL树的操作

3.1 插入

3.1.1 基本步骤

因为AVL树是BS树的改进,所以插入数据时还是使用二叉搜索树的插入:

template<class T>
struct AVLTreeNode
{
	T val;
	AVLTreeNode<T>* _right;//右结点
	AVLTreeNode<T>* _left;//左结点
	AVLTreeNode<T>* _parent;//父亲结点
	int _bf;//平衡因子
	AVLTreeNode(T data) 
		:val(data), _right(nullptr), 
		_left(nullptr), _parent(nullptr), _bf(0)
	{};
}; 

template<class T>
class AVLTree
{
	typedef AVLTreeNode<T> Node;
public:
	bool Insert(T data)
	{
		if (_root == nullptr)//如果树为空,直接插入
		{
			_root = new Node(data);
			return true;
		}

		Node* parent = nullptr;//记录父结点
		Node* cur = _root;//记录当前结点,该结点要遍历整棵树
		while (cur)
		{
			if (data < cur->val)//如果插入的值小于根结点,向左走
			{
				parent = cur;//更新父结点
				cur = cur->_left;
			}
			else if (data > cur->val)//如果插入的值大于根结点,向右走
			{
				parent = cur;
				cur = cur->_right;
			}
			else return false;//如果走到这里一定出现了相等的数据,不可以插入
		}
		//new新结点插入到树中
		cur = new Node<int>(data);
		if (data < parent->val)
			parent->_left = cur;
		else
			parent->_right = cur;
    }

private:
	Node* _root = nullptr;
};

然后再调整平衡因子。

3.1.2 平衡因子的调整

在每次插入数据时,
if 新结点插入在父结点左侧 ——> _bf--;
if 新结点插入在父结点右侧 ——> _bf++;

又因为插入数据前的树就是一棵AVL树,所以树的平衡因子只能是下述三种情况:

首先要明确插入数据后父结点平衡因子的三种情况:
1. _bf == 0 ——> 父结点左右刚好达到平衡,无需继续向上调整

2. _bf == +-1 ——> 父结点左右高度差为1,需要继续向上调整

3. _bf == +-2 ——> 父结点的左右高度差为2,需要进行旋转(后面会说)

        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// _bf == 2 || _bf == -2
			{

			}
		}

3.2 旋转操作(重点!)

3.2.1 右单旋


此外,需要注意的是,在更新父结点(简称parent)的父结点(简称pparent)时,要特别注意parent在pparent的左结点还是右结点,不要把左孩子结点链接错误:

再次梳理一下需要更新的点:

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

		//subLR
		parent->_left = subLR;//左结点的右变成父结点的左
		if (subLR) // 检查subL的右子节点是否存在
			subLR->_parent = parent;//左结点的右的父结点变为父结点

		//subL
		subL->_right = parent;//父结点变成左结点的右 
		Node* ppNode = parent->_parent;
		parent->_parent = subL;//更新父结点的父结点
	
		if (parent == _root)
		{
			_root = subL;
			_root->_parent = nullptr;
		}
		else
		{	
			subL->_parent = ppNode;//更新左结点的父结点
			if (parent == ppNode->_left)
				ppNode->_left = subL;
			else
				ppNode->_right = subL;
		}
		parent->_bf = 0;//更新父结点的平衡因子
		subL->_bf = 0;//更新左结点的平衡因子
	}

3.2.2 左单旋

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

		//subRL
		parent->_right = subRL;//右结点的左变成父结点的右
		if (subRL) // 检查subR的左子节点是否存在
			subRL->_parent = parent;//右结点的左的父变为父结点

		//subR
		subR->_left = parent;//父结点变成右结点的左 
		Node* ppNode = parent->_parent;
		parent->_parent = subR;//更新父结点的父结点

		if (parent == _root)
		{
			_root = subR;
			_root->_parent = nullptr;
		}
		else
		{
			subR->_parent = ppNode;//更新右结点的父结点
			if (parent == ppNode->_left)
				ppNode->_left = subR;
			else
				ppNode->_right = subR;
		}
		parent->_bf = 0;//更新父结点的平衡因子
		subR->_bf = 0;//更新右结点的平衡因子
	}

3.2.3 左右双旋

把左结点subL当成_root,进行左旋,使得subLR与parent链接并把subLRL旋到subL
把parent当成_root,进行右旋,把新得到的subL变成parent并把自己旋到新parent的subR上。

以下是暂时的简单代码:

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

这样可能认为左右单旋仅仅是代码的复用,但是有至关重要的一步:调节平衡因子!

因为单旋会调节平衡因子,所以在单旋前先要记录一下平衡因子以确定新插入数据的插入位置:

所以对代码进行进一步修正得:

	void RotateLR(Node* parent)
	{
		Node* subL = parent->_left;
		Node* subLR = subL->_right;
		int _bf = subLR->_bf;
		RotateL(subL);
		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);
		}
	}

3.2.4 右左双旋

原理类似于左右双旋,这里不做过多赘述。

	void RotateRL(Node* parent)
	{
		Node* subR = parent->_right;
		Node* subRL = subR->_left;
		int _bf = subRL->_bf;
		RotateR(subR);
		RotateL(parent);
		if (_bf == -1)
		{
			subRL->_bf = 0;
			subR->_bf = -1;
			parent->_bf = 0;
		}
		else if (_bf == 1)
		{
			subRL->_bf = 0;
			subR->_bf = 0;
			parent->_bf = -1;
		}
		else if (_bf == 0)
		{
			subRL->_bf = 0;
			subR->_bf = 0;
			parent->_bf = 0;
		}
		else
		{
			assert(false);
		}
	}

 把旋转的知识都了解完了以后,就可以继续改插入的代码了。

3.3 插入

template<class T>
struct AVLTreeNode
{
	T val;
	AVLTreeNode<T>* _right;//右结点
	AVLTreeNode<T>* _left;//左结点
	AVLTreeNode<T>* _parent;//父亲结点
	int _bf;//平衡因子
	AVLTreeNode(T data) 
		:val(data), _right(nullptr), 
		_left(nullptr), _parent(nullptr), _bf(0)
	{};
}; 

template<class T>
class AVLTree
{
	typedef AVLTreeNode<T> Node;
public:
	bool Insert(T data)
	{
		if (_root == nullptr)//如果树为空,直接插入
		{
			_root = new Node(data);
			return true;
		}

		Node* parent = nullptr;//记录父结点
		Node* cur = _root;//记录当前结点,该结点要遍历整棵树
		while (cur)
		{
			if (data < cur->val)//如果插入的值小于根结点,向左走
			{
				parent = cur;//更新父结点
				cur = cur->_left;
			}
			else if (data > cur->val)//如果插入的值大于根结点,向右走
			{
				parent = cur;
				cur = cur->_right;
			}
			else return false;//如果走到这里一定出现了相等的数据,不可以插入
		}
		//new新结点插入到树中
		cur = new Node<int>(data);
		if (data < parent->val)
			parent->_left = cur;
		else
			parent->_right = cur;

		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)// _bf == 2 || _bf == -2
			{
				if (parent->_bf == -2 && parent->_left->_bf == -1)
					RotateR(parent);
				else if (parent->_bf == 2 && parent->_right->_bf == 1)
					RotateL(parent);
				else if (parent->_bf == -2 && parent->_right->_bf == 1)
					RotateLR(parent);
				else
					RotateLR(parent);
				break;
			}
			else
				assert(false);
			return true;
		}
	}
private:
	void RotateR(Node* parent)
	{
		Node* subL = parent->_left;
		Node* subLR = subL->_right;

		//subLR
		parent->_left = subLR;//左结点的右变成父结点的左
		if (subLR) // 检查subL的右子节点是否存在
			subLR->_parent = parent;//左结点的右的父结点变为父结点

		//subL
		subL->_right = parent;//父结点变成左结点的右 
		Node* ppNode = parent->_parent;
		parent->_parent = subL;//更新父结点的父结点
	
		if (parent == _root)
		{
			_root = subL;
			_root->_parent = nullptr;
		}
		else
		{	
			subL->_parent = ppNode;//更新左结点的父结点
			if (parent == ppNode->_left)
				ppNode->_left = subL;
			else
				ppNode->_right = subL;
		}
		parent->_bf = 0;//更新父结点的平衡因子
		subL->_bf = 0;//更新左结点的平衡因子
	}
	void RotateL(Node* parent)
	{
		Node* subR = parent->_right;
		Node* subRL = subR->_left;

		//subRL
		parent->_right = subRL;//右结点的左变成父结点的右
		if (subRL) // 检查subR的左子节点是否存在
			subRL->_parent = parent;//右结点的左的父变为父结点

		//subR
		subR->_left = parent;//父结点变成右结点的左 
		Node* ppNode = parent->_parent;
		parent->_parent = subR;//更新父结点的父结点

		if (parent == _root)
		{
			_root = subR;
			_root->_parent = nullptr;
		}
		else
		{
			subR->_parent = ppNode;//更新右结点的父结点
			if (parent == ppNode->_left)
				ppNode->_left = subR;
			else
				ppNode->_right = subR;
		}
		parent->_bf = 0;//更新父结点的平衡因子
		subR->_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)
		{
			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(subR);
		RotateL(parent);
		if (_bf == -1)
	 	{
			subRL->_bf = 0;
			subR->_bf = -1;
			parent->_bf = 0;
		}
		else if (_bf == 1)
		{
			subRL->_bf = 0;
			subR->_bf = 0;
			parent->_bf = -1;
		}
		else if (_bf == 0)
		{
			subRL->_bf = 0;
			subR->_bf = 0;
			parent->_bf = 0;
		}
		else
		{
			assert(false);
		}
	}
private:
	Node* _root = nullptr;
};

3.4 计算高度

public:    
    int Height()
	{
		return _Height(_root);
	}
private:
    int _Height(Node* root)
	{
		if (root == nullptr)
			return 0;

		return max(_Height(root->_left), _Height(root->_right)) + 1;
	}

3.5 计算结点数量 

public:
    int Size()
	{
		return _Size(_root);
	}
private:
    int _Size(Node* root)
	{
		return root == nullptr ? 0 : _Size(root->_left) + _Size(root->_right) + 1;
	}

3.6 检查是否平衡 

public:
	bool isBlance()
	{
		return _IsBalance(_root);
	}
private:
    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->val << endl;
			return false;
		}

		// 顺便检查一下平衡因子是否正确
		if (rightHeight - leftHeight != root->_bf)
		{
			cout << root->val << endl;
			return false;
		}

		return _IsBalance(root->_left)
			&& _IsBalance(root->_right);
	}

3.7 树的遍历(中序)

public:
    void InOrder()
    {
        _InOrder(_root);
    }
private:
    void _InOrder(Node* root)
	{
		if (root == nullptr)
		{
			return;
		}

		_InOrder(root->_left);
		cout << root->val << endl;
		_InOrder(root->_right);
	}

3.8 树的查找

public:
    Node* Find(const T x)
	{
		Node* cur = _root;
		while (cur)
		{
			if (cur->_val < x)
				cur = cur->_right;
	
			else if (cur->_val > x)
				cur = cur->_left;
			
			else
				return cur;
		}
		return nullptr;
	}

四、树的检验

void TestAVLTree1()
{
	int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };
	AVLTree<int> t1;
	for (auto e : a)
	{
		t1.Insert({ e });

		cout << "Insert:" << e << "->" << t1.IsBalance() << endl;
	}

	t1.InOrder();

	cout << t1.IsBalance() << endl;
}

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

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

相关文章

【算法】滑动窗口——最小覆盖子串

本节博客是对“最小覆盖子串”题目由暴力求解到滑动窗口的思路解析&#xff0c;有需要借鉴即可。 目录 1.题目2.滑动窗口解法3.总结 1.题目 题目链接&#xff1a;LINK 这个题目是困难难度&#xff0c;感觉是一个中等题目的感觉。 首先我肯定想到的是暴力求解的方法&#xff…

大模型微调方法汇总

微调方法 Freeze方法P-tuning方法 prefix-tuningPrompt TuningP-tuning v1P-tuning v2Lora方法 重要相关参数LoRA 的优势Qlora方法 相关参数微调经验 模型选择模型大小选择数据处理微调方案英文模型需要做词表扩充吗&#xff1f;如何避免灾难遗忘大模型的幻觉问题微调后的输出…

MySQL表的增删查改【基础部分】

数据表的操作 新增 普通插入 insert into 表名 values(值,值...)注意&#xff1a; 此处的值要和表中的列相匹配 使用’‘单引号或者”“双引号来表示字符串 mysql> insert into student values(123,zhangsan); Query OK, 1 row affected (0.02 sec)指定列插入 insert …

搜索引擎的设计与实现(二)

目录 3 搜索引擎的基本原理 3.1搜索引擎的基本组成及其功能 l.搜索器 (Crawler) 2.索引器(Indexer) 3.检索器(Searcher) 4.用户接口(UserInterface) 3.2搜索引擎的详细工作流程 4 系统分析与设计 4.1系统分析 4.2系统概要设计 4.2系统实现目标 前面内容请移步 搜索引…

苍穹外卖Day06笔记(复习了jwt的加密解密和传递)

疯玩了一个月&#xff0c;效率好低&#xff0c;今天开始捡起来苍穹外卖~ 1. 为什么不需要单独引入HttpClient的dependency&#xff1f; 因为我们在sky-common的pom.xml中已经引入了aliyun-sdk-oss的依赖&#xff0c;而这个依赖低层就引入了httpclinet的依赖&#xff0c;根据依…

06、SpringBoot 源码分析 - SpringApplication启动流程六

SpringBoot 源码分析 - SpringApplication启动流程六 初始化基本流程SpringApplication的prepareEnvironment准备环境SpringApplication的getOrCreateEnvironment创建环境configureEnvironment配置环境ApplicationConversionService的getSharedInstance配置转换器 SpringApplic…

LLVM中期报告

1&#xff0e;主要开展的工作 研究对LLVM IR层面进行代码混淆&#xff0c;分析IR的指令 &#xff0c;并且实现混淆 从LLVM代码混淆的角度出发&#xff0c;函数之间的正常调用构成了待混淆程序的原始控制流&#xff0c;不同的基础代码块构成了一个个的函数&#xff0c;每个基础…

PyQt6--Python桌面开发(12.QpushButton按钮控件)

一.按钮类控件 二.QpushButton按钮控件 2.1QAbstractButton类属性 2.2QpushButton类属性

Git系列:Git Stash临时保存与恢复工作进度

&#x1f49d;&#x1f49d;&#x1f49d;欢迎莅临我的博客&#xff0c;很高兴能够在这里和您见面&#xff01;希望您在这里可以感受到一份轻松愉快的氛围&#xff0c;不仅可以获得有趣的内容和知识&#xff0c;也可以畅所欲言、分享您的想法和见解。 推荐:「stormsha的主页」…

ncs sdk nrf5340 运行DFU

nrf5340 运行DFU 1. dfu介绍 Nordic 的 DFU&#xff08;Device Firmware Update&#xff09;是一种用于更新设备固件的技术和协议。Nordic Semiconductor 是一家专门设计和制造无线芯片的公司&#xff0c;他们的产品主要用于物联网&#xff08;IoT&#xff09;和无线连接应用…

无线网卡网络老断网

无线网卡网络老断网 设置 Intel AX210 无线网卡 路由器华为 AX3 问题及解决 问题 无线网卡连接到 wifi &#xff0c;连接不通&#xff0c;或者连接上后网络很慢&#xff0c;延时大&#xff0c;掉包。 解决方案 调整如下界面&#xff0c;调整信道后&#xff0c;连接正常。…

Springboot HelloWorld

新建一个maven工程 引入依赖项 <modelVersion>4.0.0</modelVersion><parent><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-parent</artifactId><version>2.2.11.RELEASE</version><…

armbian 安装libreoffice 转换word为PDF

安装libreoffice sudo apt-get install libreoffice安装JVM sudo apt-get install default-jre #验证 java -version尝试转换&#xff1a; libreoffice --convert-to pdf /root/printFiles/f.docx发现问题乱码 从Windows 拷贝字体到debian上&#xff0c;windows字体路径是&a…

Postman基础功能-断言与日志

若能脱颖而出&#xff0c;何必苦苦融入。大家好&#xff0c;在 API 测试的领域中&#xff0c;Postman 是一款极为强大且广泛使用的工具。其中&#xff0c;断言和日志调试功能扮演着至关重要的角色。 一、介绍 断言允许我们在测试过程中验证 API 的响应是否符合预期。通过设定各…

vue从入门到精通(一):初始Vue

一&#xff0c;Vue是什么 Vue (读音 /vjuː/&#xff0c;类似于 view) 是一套用于构建用户界面的渐进式框架。Vue 被设计为可以自底向上逐层应用。Vue 的核心库只关注视图层&#xff0c;不仅易于上手&#xff0c;还便于与第三方库或既有项目整合。另一方面&#xff0c;当与现代…

基于SpringBoot+Vue的教师个人成果管理系统

初衷 在后台收到很多私信是咨询毕业设计怎么做的&#xff1f;有没有好的毕业设计参考? 能感觉到现在的毕业生和当时的我有着同样的问题&#xff0c;但是当时的我没有被骗&#xff0c; 因为现在很多人是被骗的&#xff0c;还没有出学校还是社会经验少&#xff0c;容易相信别人…

猫头虎分享已解决Error || ERROR: Failed building wheel for XXX

博主猫头虎的技术世界 &#x1f31f; 欢迎来到猫头虎的博客 — 探索技术的无限可能&#xff01; 专栏链接&#xff1a; &#x1f517; 精选专栏&#xff1a; 《面试题大全》 — 面试准备的宝典&#xff01;《IDEA开发秘籍》 — 提升你的IDEA技能&#xff01;《100天精通鸿蒙》 …

物联网设计竞赛_3_Jetson Nano连接摄像头

ls /dev/video* 查看是否有摄像头 camorama 开启摄像头 关闭摄像头用&#xff1a; ctr c结束进程 若有camorama被启动用ps aux 或者 ps aux l grep camorama 找到对应进程用 kill -9 <PID>杀死进程再启动 必要的时候也能重启系统再试试&#xff1a; shutdown -r …

AI试衣IDM-VTON,Windows11本地安装配置记录!

昨天我们已经介绍过IDM-VTON这个开源项目了。 通过这个软件可以轻松实现一键换衣服。 昨天&#xff0c;简单演示了一下在线使用。 今天&#xff0c;来演示如何安装到本地电脑上&#xff01; 本地配置会有一定的专业性&#xff0c;懂的人可以参考下。 不懂得直接拉到最后&am…

【MySQL数据库开发设计规范】之字段设计规范

欢迎点开这篇文章&#xff0c;自我介绍一下哈&#xff0c;本人姑苏老陈 &#xff0c;是一名JAVA开发老兵。 本文收录于 《MySQL数据库开发设计规范》专栏中&#xff0c;该专栏主要分享一些关于MySQL数据库开发设计相关的技术规范文章&#xff0c;定期更新&#xff0c;欢迎关注&…