C++学习笔记:AVL树

AVL树

  • 什么是AVL树?
  • AVL树节点的定义
  • AVL树的插入
    • 平衡因子调整
    • 旋转调整
    • 左旋转
    • 右旋转
    • 左右双旋
    • 右左双旋
  • AVL树完整代码实现

什么是AVL树?

AVL是1962年,两位俄罗斯数学家G.M.Adelson-Velskii和E.M.Landis 为了解决如果数据有序或接近有序二叉搜索树将退化为单支树，查找元素相当于在顺序表中搜索元素，效率低下的问题 ,因此发明了一种特殊的二叉搜索树,并以他们的名字命名为AVL树.
相比于普通的二叉树来说,AVL树的节点定义多了一个平衡因子:
平衡因子 = 右子树的高度 - 左子树的高度
因为AVL树需要通过平衡因子来确保它的特性,而AVL树的特性有以下几点:

  • 它的左右子树都是AVL树
  • 左右子树高度之差(简称平衡因子)的绝对值不超过1(-1/0/1)
    在这里插入图片描述

因为有上面两点的限制,当向二叉搜索树中插入新结点后，如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整)，即可降低树的高度，从而减少平均搜索长度。

如果一棵二叉搜索树是高度平衡的，它就是AVL树。如果它有n个结点，其高度可保持在 O ( l o g 2 n ) O(log_2 n) O(log2​n)，搜索时间复杂度O( l o g 2 n log_2 n log2​n)

AVL树节点的定义

因为在AVL树中,若插入一些节点需要对AVL树的节点进行旋转调整等,在进行旋转调整的时候需要记录当前节点父节点的位置,因此在AVL树的节点定义如下:

template<class T>
struct AVLTreeNode
{
	AVLTreeNode(const T& data = T())
		: _left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _data(data)
		, _bf(0)
	{}
		
	AVLTreeNode<T>* _left;  
	AVLTreeNode<T>* _right;
	AVLTreeNode<T>* _parent;
	T _data;
	int _bf;   // 节点的平衡因子
};

平衡因子_bf应初始化为0

AVL树的插入

AVL树就是在二叉搜索树的基础上引入了平衡因子，因此AVL树也可以看成是二叉搜索树。
但是AVL树插入值的时候会有平衡因子的改变,那么AVL树的插入过程可以分为两步：

  1. 按照二叉搜索树的方式插入新节点
  2. 调整节点的平衡因子

平衡因子调整

  • 新增节点在父节点的左边 bf–

  • 新增节点在父节点的右边 bf++
    在更新后:

  • 插入节点之前,父亲的bf 为 1 或者 -1 ,插入节点在低的子树那边,那么更新后父亲的 bf == 0 ,左右子树高度不变,插入结束
    在这里插入图片描述

  • 插入前父节点的bf = 0,更新后父亲的 bf == 1 || bf == -1 ,父亲所在子树高度变了,需要继续往上更新
    在这里插入图片描述

  • 父亲节点bf更新后为 2 或者 -2,则说明需要进行调整
    在这里插入图片描述

新增节点可能会影响祖先,因此插入节点后,需要查看子树的高度是否变化:

  • 若子树高度不变,就不会影响祖先
  • 若子树高度改变,就会影响祖先

如下图,虽然增加了一个节点,但是并不影响节点 7 这颗子树的高度,因此祖先节点5就不会改变
在这里插入图片描述
但是出现下面这种情况,就需要进行调整了
在这里插入图片描述
因为新插入的节点影响了父节点 9 的高度,进而影响了 8 节点的平衡因子变成了2
这种时候就需要进行调整了

旋转调整

AVL树正式因为有旋转调整这一必杀利器，因此才能保证它一直是AVL树，而旋转调整又分为：左旋转，右旋转，左右旋转，右左旋转
四种旋转分别对应４种不同的情况接下来看看这些旋转的条件及思想
而旋转的必要条件就是父亲节点的bf == -2 || bf == 2:parent->_bf == -2 || parent->_bf == 2

左旋转

左旋转的条件: parent->_bf == 2 && cur->_bf == 1
如图:
简易版:
在这里插入图片描述

综合版
在这里插入图片描述

代码实现:

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

		parent->_right = subRL;
		subR->_left = parent;

		Node* pparent = parent->_parent;

		parent->_parent = subR;
		if (subRL)
		{
			subRL->_parent = parent;
		}

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

	}

右旋转

右旋转的条件:parent->_bf == -2 && cur->_bf == -1
思想:
简易版:
在这里插入图片描述
综合版
在这里插入图片描述

左右双旋

左右双旋的条件:parent->_bf == -2 && cur->_bf == 1
思想:
在这里插入图片描述
将双旋变成单旋后再旋转，即：先对30进行左单旋，然后再对90进行右单旋，旋转完成后再考虑平衡因子的更新。
代码实现

// 左右双旋
	void RotateLR(Node* parent)
	{
		Node* subL = parent->_left;
		Node* subLR = subL->_right;
		int bf = subLR->_bf;

		RotateL(parent->_left);
		RotateR(parent);
		//此节点本身就是插入节点
		if (bf == 0)
		{
			parent->_bf = subL->_bf = subLR->_bf = 0;
		}
		else if (bf == 1) //右子树的高度较高
		{
			parent->_bf = 0;
			subL->_bf = -1;
			subLR->_bf = 0;
		}
		else if (bf == -1) //左子树的高度较高
		{
			parent->_bf = 1;
			subL->_bf = 0;
			subLR->_bf = 0;
		}
		else
		{
			assert(false);
		}
	}

右左双旋

右左双旋的条件:parent->_bf == 2 && cur->_bf == -1
思想:
在这里插入图片描述
右左双旋代码实现:

// 右左双旋
	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 = 0;
			subR->_bf = 0;
			subRL->_bf = 1;
		}
		else if (bf == 1)
		{
			//subRL 的右子树新增节点 
			parent->_bf = -1;
			subR->_bf = 0;
			subRL->_bf = 0;
		}
		else
		{
			assert(false);
		}
	}

AVL树完整代码实现

此代码种包含了AVL树平衡的判断和中序遍历

#pragma once
#include<iostream>
#include<assert.h>

using namespace std;

template<class T>
struct AVLTreeNode
{
	AVLTreeNode(const T& data = T())
		: _left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _data(data)
		, _bf(0)
	{}
		
	AVLTreeNode<T>* _left;
	AVLTreeNode<T>* _right;
	AVLTreeNode<T>* _parent;
	T _data;
	int _bf;   // 节点的平衡因子
};


// AVL: 二叉搜索树 + 平衡因子的限制
template<class T>
class AVLTree
{
	typedef AVLTreeNode<T> Node;
public:

	// 在AVL树中插入值为data的节点
	bool Insert(const T& data)
	{
		if (_root == nullptr)
		{
			_root = new Node(data);
			return true;
		}
		Node* parent = nullptr;
		Node* cur = _root;
		while (cur)
		{
			if (cur->_data > data)
			{
				parent = cur;
				cur = cur->_left;
			}
			else if (cur->_data < data)
			{
				parent = cur;
				cur = cur->_right;
			}
			else
			{
				return false;
			}
		}
		cur = new Node(data);
		if (parent->_data > data)
		{
			parent->_left = cur;
		}
		else
		{
			parent->_right = cur;
		}
		cur->_parent = parent;

		//判断平衡因子
		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)  //该调整了
			{
				//单纯的右边高 左旋
				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);
				}
				//左边的右子树高  左右双旋
				else if (parent->_bf == -2 && cur->_bf == 1)
				{
					RotateLR(parent);
				}
				//旋转完成后不再需要更新
				break;
			}
			else
			{
				assert(false);
			}
			
		}
		return true;
	}

	bool Isbalance()
	{
		return _Isbalance(_root);
	}

	void InOrder()
	{
		_InOrder(_root);
		cout << endl;
	}

private:

	// 右单旋
	void RotateR(Node* parent)
	{
		Node* pparent = parent->_parent;
		Node* subL = parent->_left;
		Node* subLR = subL->_right;

		parent->_left = subLR;
		parent->_parent = subL;
		subL->_right = parent;

		if (subLR)
		{
			subLR->_parent = parent;
		}

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

	}
	// 左单旋
	void RotateL(Node* parent)
	{
		Node* subR = parent->_right;
		Node* subRL = subR->_left;

		parent->_right = subRL;
		subR->_left = parent;

		Node* pparent = parent->_parent;

		parent->_parent = subR;
		if (subRL)
		{
			subRL->_parent = parent;
		}

		if (parent == _root)
		{
			_root = subR;
			subR->_parent = nullptr;
		}
		else
		{
			if (pparent->_left == parent)
			{
				pparent->_left = subR;
			}
			else
			{
				pparent->_right = subR;
			}
			subR->_parent = pparent;
		}
		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 = 0;
			subR->_bf = 0;
			subRL->_bf = 1;
		}
		else if (bf == 1)
		{
			//subRL 的右子树新增节点 
			parent->_bf = -1;
			subR->_bf = 0;
			subRL->_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 == 0)
		{
			parent->_bf = subL->_bf = subLR->_bf = 0;
		}
		else if (bf == 1) //右子树的高度较高
		{
			parent->_bf = 0;
			subL->_bf = -1;
			subLR->_bf = 0;
		}
		else if (bf == -1) //左子树的高度较高
		{
			parent->_bf = 1;
			subL->_bf = 0;
			subLR->_bf = 0;
		}
		else
		{
			assert(false);
		}
	}

	//AVL树的高度
	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)
	{
		if (root == nullptr)
		{
			return true;
		}

		int leftHeight = _height(root->left);
		int rightHeight = _height(root->right);

		if (root->_bf != rightHeight - leftHeight)
		{
			cout << root->_data << "节点bf异常" << endl;
		}

		return abs(leftHeight - rightHeight) < 2
			&& _Isbalance(root->_left)
			&& _Isbalance(root->_right);

	}

	

	void _InOrder(Node* root)
	{
		if (root == nullptr)
		{
			return;
		}
		_InOrder(root->_left);
		cout << root->_data << " ";
		_InOrder(root->_right);
	}

private:
	Node* _root = nullptr;
};

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

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

相关文章

Mac M1：通过docker安装RocketMQ、RocketMQ-Dashboard

Mac M1：通过docker安装RocketMQ、RocketMQ-Dashboard

0. 引言 最近本地启动以前docker安装的rocketmq发现报错了&#xff0c;因为是从老mac迁移过来的&#xff0c;发现支持的芯片还是amd的&#xff0c;于是重新在docker下安装rocketmq&#xff0c;并记录下步骤&#xff0c;方便大家后续参考。 1. 步骤 1、先下载项目源码 git c…
阅读更多...
景联文科技：专业提供高质量大语言模型训练数据

景联文科技：专业提供高质量大语言模型训练数据

2024年&#xff0c;数字经济被再次写入政府工作报告中&#xff0c;报告指出要深化大数据、人工智能等研发应用&#xff0c;打造具有国际竞争力的数字产业集群。 大模型作为生成式人工智能的基础&#xff0c;日益成为国际科技竞争的焦点。人大代表杨剑宇指出&#xff0c;尽管我国…
阅读更多...
货运物流小程序开发功能 发货运输更简单

货运物流小程序开发功能 发货运输更简单

随着互联网的快速发展&#xff0c;线上接单已经成为物流行业的主流趋势。货运物流接单小程序作为物流企业的得力助手&#xff0c;能够提高运输效率、降低成本、提升服务质量&#xff0c;成为物流行业的发展新方向。 1. 用户注册与登录功能&#xff1a;用户可以通过手机号、邮箱…
阅读更多...
nodejs web服务器 -- 搭建开发环境

nodejs web服务器 -- 搭建开发环境

一、配置目录结构 1、使用npm生成package.json&#xff0c;我创建了一个nodejs_network 文件夹&#xff0c;cd到这个文件夹下&#xff0c;执行&#xff1a; npm init -y 其中-y的含义是yes的意思&#xff0c;在init的时候省去了敲回车的步骤&#xff0c;如此就生成了默认的pac…
阅读更多...
基于Leatlet标注Geojson下载器实现

基于Leatlet标注Geojson下载器实现

在上一篇文章中&#xff0c;我们学习了Leaflet的基础知识&#xff0c;包括如何创建地图、添加图层等。在本文中&#xff0c;我们将深入学习Leaflet中标注的创建和管理&#xff0c;包括如何添加标注、自定义标注图标、创建图层组、批量添加和删除标注、为标注添加属性和弹出框等…
阅读更多...
二、TensorFlow结构分析（4）

二、TensorFlow结构分析（4）

TF数据流图图与TensorBoard会话张量Tensor变量OP高级API 目录 1、变量 2、高级API 1、变量 2、高级API
阅读更多...
[嵌入式系统-37]：龙芯1B 开发学习套件 -6-协处理器CP0之CPU异常处理与外部中断控制器的中断处理

[嵌入式系统-37]：龙芯1B 开发学习套件 -6-协处理器CP0之CPU异常处理与外部中断控制器的中断处理

目录 一、MPIS CPU Core与32个异常exception 1.1 龙芯1B的MIPS CPU IP Core 1.2 MIP32指令系统 1.3 MIPS CPU寄存器 1.4 MIPS CPU的异常向量与异常向量号 1.5 龙芯异常exception与中断interrupt的区别 二、协议处理器CP0的中断控制与8个中断 2.1 CP0概述 2.2 协处理器…
阅读更多...
Word文档一键转换成电子书，告别繁琐操作！

Word文档一键转换成电子书，告别繁琐操作！

你是否曾经为了将Word文档转换为电子书而苦恼&#xff1f;手动复制粘贴、调整格式、排版等等繁琐的操作&#xff0c;不仅耗时费力&#xff0c;还容易出错。现在我教你只需轻轻一点&#xff0c;即可将Word文档轻松转换为电子书&#xff0c;无需任何手动操作 一、Word转换电子书步…
阅读更多...
基于React低代码平台开发：直击最新应用构建

基于React低代码平台开发：直击最新应用构建

文章目录 前言一、React与低代码平台的结合优势二、基于React的低代码平台开发挑战三、基于React的低代码平台开发实践四、未来展望《低代码平台开发实践&#xff1a;基于React》编辑推荐内容简介作者简介目录前言为什么要写这本书读者对象如何阅读本书 前言 随着数字化转型的…
阅读更多...
Word论文格式怎么设置 Word论文查重功能在哪里 论文格式要求及字体大小 论文查重怎么查 WPS论文查重准确吗

Word论文格式怎么设置 Word论文查重功能在哪里 论文格式要求及字体大小 论文查重怎么查 WPS论文查重准确吗

Word文档是由Microsoft Word处理软件创建和编辑的文档。Word文档通常用于创建各种类型的文档&#xff0c;如信函、报告、简历、论文等。本篇文章将为大家介绍Word论文格式怎么设置以及Word论文查重功能在哪里。 一、Word论文格式怎么设置 一个好的论文格式&#xff0c;是论文…
阅读更多...
【框架设计】MVC、MVP、MVVM对比图

【框架设计】MVC、MVP、MVVM对比图

1. MVC&#xff08;Model-View-Controller&#xff09; 2. MVP&#xff08;Model-View-Presenter&#xff09; 3. MVVM&#xff08;Model-View-ViewModel&#xff09;
阅读更多...
ai数字人虚拟直播：AI大模型带给你不一样的体验

ai数字人虚拟直播：AI大模型带给你不一样的体验

AI数字人虚拟直播&#xff0c;这一新兴的科技形式&#xff0c;正逐渐融入人们的生活之中。通过AI大模型的技术支持&#xff0c;数字人可以实现高度仿真的互动体验&#xff0c;让观众感受到前所未有的沉浸式乐趣。 数字人虚拟直播的魅力在于其超越了传统直播形式的局限性&#…
阅读更多...
Python爬虫——Scrapy-1

Python爬虫——Scrapy-1

目录 简介 安装 基本使用 1. 创建爬虫的项目 2. 创建爬虫文件 3. 运行爬虫代码 scrapy项目组成 scrapy工作原理 ​编辑 58同城 scrapy架构组成 汽车之家 总结 简介 Scrapy 是一个基于 Python 的开源网络爬虫框架&#xff0c;它可以帮助开发者快速、高效地构…
阅读更多...
数据结构从入门到精通——栈

数据结构从入门到精通——栈

栈 前言一、栈1.1栈的概念及结构1.2栈的实现1.3栈的面试题 二、栈的具体实现代码栈的初始化栈的销毁入栈出栈返回栈顶元素返回栈中的元素个数检测是否为空Stack.hStack.ctest.c 前言 栈&#xff0c;作为一种后进先出&#xff08;LIFO&#xff09;的数据结构&#xff0c;在计算…
阅读更多...
Windows系统搭建it-tools工具箱并结合内网穿透实现公网远程访问

Windows系统搭建it-tools工具箱并结合内网穿透实现公网远程访问

文章目录 1. 使用Docker本地部署it-tools2. 本地访问it-tools3. 安装cpolar内网穿透4. 固定it-tools公网地址 本篇文章将介绍如何在Windows上使用Docker本地部署IT- Tools&#xff0c;并且同样可以结合cpolar实现公网访问。 在前一篇文章中我们讲解了如何在Linux中使用Docker搭…
阅读更多...
FPGA FIFO 读取模式

FPGA FIFO 读取模式

FPGA FIFO 读取模式分两种&#xff1a; Normal Mode: In normal mode, the “rdreq” signal serves as the read request or read enable. When this signal goes high, the data output provides the first data from the FIFO.Essentially, in normal mode, data is availa…
阅读更多...
pytest测试框架使用基础07 fixture—parametrize获取参数的几种常用形式

pytest测试框架使用基础07 fixture—parametrize获取参数的几种常用形式

【pytest】parametrize获取参数的几种常用形式: a.数据结构 b.文件 c.数据库 d.conftest.py配置一、直接在标签上传参 1.1 一个参数多个值 pytest.mark.parametrize("参数", (参数值1, 参数值2, 参数值3))示例&#xff1a; import pytest # 单个参数的情况 pytest.…
阅读更多...
如何向各大媒体网站投稿 海外媒体发稿平台有哪些

如何向各大媒体网站投稿 海外媒体发稿平台有哪些

在数字化时代&#xff0c;各大媒体网站是企业推广和个人展示的重要平台。通过在媒体网站上发布文章&#xff0c;可以有效地扩大影响力和提升知名度。但是&#xff0c;如何投稿到各大媒体网站呢&#xff1f;以下是一些常用的方法和步骤。 1. 研究目标媒体 在投稿之前&#xff0…
阅读更多...
宠物空气净化器值得入手吗？选购宠物空气净化器关注哪些方面？

宠物空气净化器值得入手吗？选购宠物空气净化器关注哪些方面？

一开始养猫时&#xff0c;每天看着可爱的猫咪在家里快乐奔跑&#xff0c;让人心情愉悦。然而&#xff0c;作为铲屎官都知道&#xff0c;猫咪会掉毛&#xff0c;特别是在换毛期间&#xff0c;地板、沙发上都会有一大堆猫毛&#xff0c;甚至衣服也可能沾满猫毛。养猫家庭中&#…
阅读更多...
安装邮件服务器postfix、mail客户端发送邮件

安装邮件服务器postfix、mail客户端发送邮件

安装邮件服务器postfix、mail客户端发送邮件 1 安装postfix sudo apt-get update sudo apt-get install postfix -y安装过程中会让你选择一种Postfix配置类型&#xff0c;直接选择默认的第二种配置Internet Site就可以了。 选择ok之后会让你填入域名&#xff0c;一般会自动填…
阅读更多...
最新文章

Copyright @ 2022~2023