【数据结构】深入理解AVL树：实现和应用

AVL树是一种自平衡的二叉搜索树，它能够保持良好的平衡性质，使得在最坏情况下的时间复杂度也能保持在对数级别。本文将深入介绍AVL树的原理、实现和应用，并通过示例代码演示其基本操作。

文章目录

  • 什么是AVL树？
  • AVL树的实现
    • 在AVL树中插入值为data的节点实现：
    • AVL树的旋转
      • 右单旋
      • 左单旋
      • 左右双旋
      • 右左双旋
  • AVL树的应用
  • 完整代码
  • 总结

什么是AVL树？

AVL树是由两位苏联数学家Adelson-Velsky和Landis于1962年发明的，它的特点是能够在插入和删除节点时自动调整树的结构，以保持树的平衡性。在AVL树中，任意节点的左右子树高度差不超过1，这就保证了整棵树的高度始终保持在对数级别，从而保证了插入、删除和查找等操作的高效性。

AVL树的实现

以下是一个C++实现的AVL树的基本结构和操作示例：

template<class T>
struct AVLTreeNode
{
	AVLTreeNode(const T& data = T())
	: _pLeft(nullptr)
	, _pRight(nullptr)
	, _pParent(nullptr)
	, _data(data)
	, _bf(0)
	{}

	AVLTreeNode<T>* _pLeft;
	AVLTreeNode<T>* _pRight;
	AVLTreeNode<T>* _pParent;
	T _data;
	int _bf;   // 节点的平衡因子
};


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

    // 在AVL树中插入值为data的节点
	bool Insert(const T& data);
    
    // AVL树的验证
	bool IsAVLTree()
	{
		return _IsAVLTree(_pRoot);
	}

private:
    // 根据AVL树的概念验证pRoot是否为有效的AVL树
	bool _IsAVLTree(Node* pRoot);
	size_t _Height(Node* pRoot);
    // 右单旋
	void RotateR(Node* pParent);
    // 左单旋
	void RotateL(Node* pParent);
    // 右左双旋
	void RotateRL(Node* pParent);
    // 左右双旋
	void RotateLR(Node* pParent);

private:
	Node* _pRoot;
};

在AVL树中插入值为data的节点实现：

// 在AVL树中插入值为data的节点
bool Insert(const T& data) {
	// 插入节点
	if (_pRoot == nullptr) {
		_pRoot = new Node(data);
		return true;
	}

	Node* pParent = nullptr;
	Node* pCur = _pRoot;
	while (pCur) {
		pParent = pCur;
		if (data < pCur->_data)
			pCur = pCur->_pLeft; // 往左子树查找
		else if (data > pCur->_data) 
			pCur = pCur->_pRight; // 往右子树查找
		else
			return false; // 重复值不插入
	}

	// 创建新节点
	pCur = new Node(data);
	if (data < pParent->_data)
		pParent->_pLeft = pCur;
	else
		pParent->_pRight = pCur;

	pCur->_pParent = pParent;

	// 插入节点后，更新平衡因子并进行平衡处理
	while (pParent) {
		if (pCur == pParent->_pLeft) // 更新节点在左子树
			--pParent->_bf; // 更新父节点的平衡因子
		else
			++pParent->_bf; // 更新父节点的平衡因子

		if (0 == pParent->_bf) // 如果平衡旋转结束
			break;

			// 如果父节点的bf==1或-1，则不需要调整，直接向上更新即可
		if (1 == pParent->_bf || -1 == pParent->_bf) {
			pCur = pParent;
			pParent = pParent->_pParent;
		} 
		else { // 父节点不平衡，需要旋转调整
			if (pParent->_bf == 2) {
				if (pCur->_bf == 1) // LL型
					// 左单旋
					RotateL(pParent);
				else // LR型
					// 先左旋后右旋
					RotateRL(pParent);
			}
			else {
				if (pCur->_bf == -1) // RR型
					// 右单旋
					RotateR(pParent);
				else // RL型
					// 先左旋后右旋
					RotateLR(pParent);
			}
			break;
		}
	}
	return true;
}

AVL树的旋转

AVL树的平衡是通过维护每个节点的平衡因子来实现的。平衡因子指的是节点的左子树高度减去右子树高度的差值，其取值范围为-1、0和1。当平衡因子的绝对值超过1时，AVL树就需要进行旋转操作来重新平衡。

右单旋

在这里插入图片描述

// 右单旋
	void RotateR(Node* pParent) {
		Node* pSubL = pParent->_pLeft;
		Node* pSubLR = pSubL->_pRight;

		// 右旋
		pParent->_pLeft = pSubLR;
		if (pSubLR)
			pSubLR->_pParent = pParent;

		pSubL->_pRight = pParent;
		pSubL->_pParent = pParent->_pParent;
		pParent->_pParent = pSubL;

		if (pParent == _pRoot)
			_pRoot = pSubL;
		else {
			if (pSubL->_pParent->_pLeft == pParent)
				pSubL->_pParent->_pLeft = pSubL;
			else
				pSubL->_pParent->_pRight = pSubL;
		}

		pParent->_bf = pSubL->_bf = 0;
	}

左单旋

在这里插入图片描述

// 左单旋
void RotateL(Node* pParent) {
	Node* pSubR = pParent->_pRight;
	Node* pSubRL = pSubR->_pLeft;

	// 左旋
	pParent->_pRight = pSubRL;
	if (pSubRL)
		pSubRL->_pParent = pParent;

	pSubR->_pLeft = pParent;
	pSubR->_pParent = pParent->_pParent;
	pParent->_pParent = pSubR;

	if (pParent == _pRoot)
		_pRoot = pSubR;
	else
	{
		if (pSubR->_pParent->_pLeft == pParent)
			pSubR->_pParent->_pLeft = pSubR;
		else
			pSubR->_pParent->_pRight = pSubR;
	}

	pParent->_bf = pSubR->_bf = 0;
}

左右双旋

在这里插入图片描述

// 左右双旋
void RotateLR(Node* pParent) {
	// 先左旋后右旋
	Node* pSubL = pParent->_pLeft;
	Node* pSubLR = pSubL->_pRight;

	// 旋转之前，保存pSubLR的平衡因子，旋转完成之后，需要根据该平衡因子来调整其他节点的平衡因子
	int bf = pSubLR->_bf;

	// 进行左单旋
	RotateL(pParent->_pLeft);

	// 进行右单旋
	RotateR(pParent);
	if (1 == bf)
		pSubL->_bf = -1;
	else if (-1 == bf)
		pParent->_bf = 1;
}

右左双旋

在这里插入图片描述

// 右左双旋
void RotateRL(Node* pParent) {
	// 先右旋后左旋
	Node* pSubR = pParent->_pRight;
	Node* pSubRL = pSubR->_pLeft;

	// 旋转之前，保存pSubRL的平衡因子，旋转完成之后，需要根据该平衡因子来调整其他节点的平衡因子
	int bf = pSubRL->_bf;

	// 进行右单旋
	RotateR(pParent->_pRight);

	//进行左单旋
	RotateL(pParent);
	if (1 == bf)
		pParent->_bf = -1;
	else if (-1 == bf)
		pSubR->_bf = 1;
}

AVL树的应用

AVL树由于其高效的插入、删除和查找操作，在计算机科学领域有着广泛的应用。例如，在数据库系统中，AVL树常被用作索引结构，用于加速数据的检索操作；在编译器的符号表实现中，也可以使用AVL树来存储和查找变量信息。

完整代码

// AVLTree.h
#include <iostream>
using namespace std;
template<class T>
struct AVLTreeNode
{
	AVLTreeNode(const T& data = T())
		: _pLeft(nullptr)
		, _pRight(nullptr)
		, _pParent(nullptr)
		, _data(data)
		, _bf(0)
	{}

	AVLTreeNode<T>* _pLeft;
	AVLTreeNode<T>* _pRight;
	AVLTreeNode<T>* _pParent;
	T _data;
	int _bf;   // 节点的平衡因子
};


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

	// 在AVL树中插入值为data的节点
	bool Insert(const T& data) {
		// 插入节点
		if (_pRoot == nullptr) {
			_pRoot = new Node(data);
			return true;
		}

		Node* pParent = nullptr;
		Node* pCur = _pRoot;
		while (pCur) {
			pParent = pCur;
			if (data < pCur->_data)
				pCur = pCur->_pLeft; // 往左子树查找
			else if (data > pCur->_data) 
				pCur = pCur->_pRight; // 往右子树查找
			else
				return false; // 重复值不插入
		}

		// 创建新节点
		pCur = new Node(data);
		if (data < pParent->_data)
			pParent->_pLeft = pCur;
		else
			pParent->_pRight = pCur;

		pCur->_pParent = pParent;

		// 插入节点后，更新平衡因子并进行平衡处理
		while (pParent) {
			if (pCur == pParent->_pLeft) // 更新节点在左子树
				--pParent->_bf; // 更新父节点的平衡因子
			else
				++pParent->_bf; // 更新父节点的平衡因子

			if (0 == pParent->_bf) // 如果平衡旋转结束
				break;

				// 如果父节点的bf==1或-1，则不需要调整，直接向上更新即可
			if (1 == pParent->_bf || -1 == pParent->_bf) {
				pCur = pParent;
				pParent = pParent->_pParent;
			} 
			else { // 父节点不平衡，需要旋转调整
				if (pParent->_bf == 2) {
					if (pCur->_bf == 1) // LL型
						// 左单旋
						RotateL(pParent);
					else // LR型
						// 先左旋后右旋
						RotateRL(pParent);
				}
				else {
					if (pCur->_bf == -1) // RR型
						// 右单旋
						RotateR(pParent);
					else // RL型
						// 先左旋后右旋
						RotateLR(pParent);
				}
				break;
			}
		}
		return true;
	}

	// AVL树的验证
	bool IsAVLTree()
	{
		return _IsAVLTree(_pRoot);
	}

private:
	// 根据AVL树的概念验证pRoot是否为有效的AVL树
	bool _IsAVLTree(Node* pRoot) {
		if (pRoot == nullptr)
			return true;

		int leftHeight = _Height(pRoot->_pLeft);
		int rightHeight = _Height(pRoot->_pRight);

		if (abs(leftHeight - rightHeight) > 1)
			return false;

		return _IsAVLTree(pRoot->_pLeft) && _IsAVLTree(pRoot->_pRight);
	}
	size_t _Height(Node* pRoot) {
		if (pRoot == nullptr)
			return 0;

		int leftHeight = _Height(pRoot->_pLeft);
		int rightHeight = _Height(pRoot->_pRight);

		return 1 + max(leftHeight, rightHeight);
	}
	// 右单旋
	void RotateR(Node* pParent) {
		Node* pSubL = pParent->_pLeft;
		Node* pSubLR = pSubL->_pRight;

		// 右旋
		pParent->_pLeft = pSubLR;
		if (pSubLR)
			pSubLR->_pParent = pParent;

		pSubL->_pRight = pParent;
		pSubL->_pParent = pParent->_pParent;
		pParent->_pParent = pSubL;

		if (pParent == _pRoot)
			_pRoot = pSubL;
		else {
			if (pSubL->_pParent->_pLeft == pParent)
				pSubL->_pParent->_pLeft = pSubL;
			else
				pSubL->_pParent->_pRight = pSubL;
		}

		pParent->_bf = pSubL->_bf = 0;
	}
	// 左单旋
	void RotateL(Node* pParent) {
		Node* pSubR = pParent->_pRight;
		Node* pSubRL = pSubR->_pLeft;

		// 左旋
		pParent->_pRight = pSubRL;
		if (pSubRL)
			pSubRL->_pParent = pParent;

		pSubR->_pLeft = pParent;
		pSubR->_pParent = pParent->_pParent;
		pParent->_pParent = pSubR;

		if (pParent == _pRoot)
			_pRoot = pSubR;
		else
		{
			if (pSubR->_pParent->_pLeft == pParent)
				pSubR->_pParent->_pLeft = pSubR;
			else
				pSubR->_pParent->_pRight = pSubR;
		}

		pParent->_bf = pSubR->_bf = 0;
	}
	// 右左双旋
	void RotateRL(Node* pParent) {
		// 先右旋后左旋
		Node* pSubR = pParent->_pRight;
		Node* pSubRL = pSubR->_pLeft;

		// 旋转之前，保存pSubRL的平衡因子，旋转完成之后，需要根据该平衡因子来调整其他节点的平衡因子
		int bf = pSubRL->_bf;

		// 进行右单旋
		RotateR(pParent->_pRight);

		//进行左单旋
		RotateL(pParent);
		if (1 == bf)
			pParent->_bf = -1;
		else if (-1 == bf)
			pSubR->_bf = 1;
	}
	// 左右双旋
	void RotateLR(Node* pParent) {
		// 先左旋后右旋
		Node* pSubL = pParent->_pLeft;
		Node* pSubLR = pSubL->_pRight;

		// 旋转之前，保存pSubLR的平衡因子，旋转完成之后，需要根据该平衡因子来调整其他节点的平衡因子
		int bf = pSubLR->_bf;

		// 进行左单旋
		RotateL(pParent->_pLeft);

		// 进行右单旋
		RotateR(pParent);
		if (1 == bf)
			pSubL->_bf = -1;
		else if (-1 == bf)
			pParent->_bf = 1;
	}

private:
	Node* _pRoot;
};

// test.cpp
#include <iostream>
#include <ctime>
#include <cstdlib>
#include "AVLTree.h"


int main() {
    AVLTree<int> avlTree;
    const int NUM_VALUES = 1000000;

    // 生成并插入 10 万个随机整数值
    srand(static_cast<unsigned int>(time(nullptr)));
    for (int i = 0; i < NUM_VALUES; ++i) {
        int randomValue = rand() % 1000000; // 生成 0 到 999999 之间的随机整数
        avlTree.Insert(randomValue);
    }

    // 验证是否为 AVL 树
    if (avlTree.IsAVLTree()) {
        std::cout << "AVL Tree validation: This is an AVL tree." << std::endl;
    }
    else {
        std::cout << "AVL Tree validation: This is not an AVL tree." << std::endl;
    }

    return 0;
}

总结

本篇博客深入介绍了AVL树，包括其原理、实现和应用。通过C++代码示例展示了AVL树的基本结构和操作，以及探讨了在计算机科学领域的广泛应用。整体内容帮助读者更好地理解和应用AVL树这一自平衡的二叉搜索树。

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

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

相关文章

Linux - 安装 Jenkins(详细教程)

Linux - 安装 Jenkins(详细教程)

目录 前言一、简介二、安装前准备三、下载与安装四、配置镜像地址五、启动与关闭六、常用插件的安装 前言 虽然说网上有很多关于 Jenkins 安装的教程&#xff0c;但是大部分都不够详细&#xff0c;或者是需要搭配 docker 或者 k8s 等进行安装&#xff0c;对于新手小白而已&…
阅读更多...
2024人工智能四大趋势→

2024人工智能四大趋势→

2023年&#xff0c;世人见证了ChatGPT在全球范围的大火。以生成式人工智能为代表的新一代人工智能问世&#xff0c;改变了人工智能&#xff08;AI&#xff09;技术与应用的发展轨迹&#xff0c;加速了人与AI的互动进程&#xff0c;是人工智能发展史上的新里程碑。2024年&#x…
阅读更多...
职场中的“跨界思维”：如何拓宽你的职业发展道路？

职场中的“跨界思维”：如何拓宽你的职业发展道路？

在当今职场&#xff0c;单一技能的竞争已经越来越激烈&#xff0c;具备跨界思维的人才越来越受到企业的青睐。本文将探讨职场中的“跨界思维”&#xff0c;帮助您拓宽职业发展道路&#xff0c;提升自身竞争力。 一、什么是跨界思维&#xff1f; 跨界思维&#xff0c;顾名思义&a…
阅读更多...
【重新定义matlab强大系列十八】Matlab深度学习长短期记忆 (LSTM) 网络生成文本

【重新定义matlab强大系列十八】Matlab深度学习长短期记忆 (LSTM) 网络生成文本

&#x1f517; 运行环境&#xff1a;Matlab &#x1f6a9; 撰写作者&#xff1a;左手の明天 &#x1f947; 精选专栏&#xff1a;《python》 &#x1f525; 推荐专栏&#xff1a;《算法研究》 #### 防伪水印——左手の明天 #### &#x1f497; 大家好&#x1f917;&#x1f91…
阅读更多...
Etcd 介绍与使用（入门篇）

Etcd 介绍与使用（入门篇）

etcd 介绍 etcd 简介 etc &#xff08;基于 Go 语言实现&#xff0c;&#xff09;在 Linux 系统中是配置文件目录名&#xff1b;etcd 就是配置服务&#xff1b; etcd 诞生于 CoreOS 公司&#xff0c;最初用于解决集群管理系统中 os 升级时的分布式并发控制、配置文件的存储与分…
阅读更多...
Bean的作用域、Bean的自动装配、注解自动装配 （Spring学习笔记五）

Bean的作用域、Bean的自动装配、注解自动装配 （Spring学习笔记五）

1、Bean 的作用域 官网上显示有六种 1、Bean的作用域默认的是singleton&#xff08;单例模式的实现&#xff09; 也可以显示的设置&#xff08;单例模式的实现&#xff09; <!--用scope可以设置Bean的作用域--><bean id"user2" class"com.li.pojo.Us…
阅读更多...
Elasticsearch从入门到精通-05ES匹配查询

Elasticsearch从入门到精通-05ES匹配查询

Elasticsearch从入门到精通-05ES匹配查询 &#x1f44f;作者简介&#xff1a;大家好&#xff0c;我是程序员行走的鱼 &#x1f4d6; 本篇主要介绍和大家一块学习一下ES各种场景下的匹配查询,有助于我们在项目中进行综合使用 前提 创建索引并指定ik分词器: PUT /es_db {"…
阅读更多...
[ Linux ] vim的使用（附：命令模式的常见命令列表）

[ Linux ] vim的使用（附：命令模式的常见命令列表）

1.下载安装 这里是在通过yum进行下载安装 yum install -y vim 2.了解 vim是一款编辑器&#xff0c;它具有多模式的特点 主要有&#xff1a;插入模式&#xff0c;命令模式&#xff0c;底行模式 3.使用 打开 vim 文件名 命令模式的常见命令列表 插入模式 按「 i 」切换…
阅读更多...
建设IAM/IDM统一身份管理,实现系统之间的单点登录（SSO）

建设IAM/IDM统一身份管理,实现系统之间的单点登录（SSO）

企业实施身份管理的现状&#xff1a; 1.身份存储分散&#xff0c;不能统一供应诸多应用系统&#xff0c;企业用户信息常常存在于多个系统&#xff0c;如HR系统有一套用户信息&#xff0c;OA系统也有一套用户信息&#xff0c;身份存储不集中&#xff0c;不能统一地为诸多应用系…
阅读更多...
BUUCTF-WEB1

BUUCTF-WEB1

[ACTF2020 新生赛]Exec1 1.打开靶机 是一个ping命令 2.利用管道符“|” ping一下本地主机并查看ls ping 127.0.0.1 | ls 可以看到回显的内容是一个文件 127.0.0.1 | cat index.php #查看主机下index.php 127.0.0.1 | ls / #查看主机根目录下的文件 看的一个flag文件 …
阅读更多...
C++：菱形继承与虚继承

C++：菱形继承与虚继承

看下面这个示例代码 class A{ public: int num10; A(){cout<<"A构造"<<endl;} virtual void fun(){cout<<"A虚函数"<<endl;} };class B:public A{ public: B(){cout<<"B构造"<<endl;} void fun(){cout<…
阅读更多...
Linux基本使用

Linux基本使用

&#x1f3a5; 个人主页&#xff1a;Dikz12&#x1f525;热门专栏&#xff1a;网络原理&#x1f4d5;格言&#xff1a;那些在暗处执拗生长的花&#xff0c;终有一日会馥郁传香欢迎大家&#x1f44d;点赞✍评论⭐收藏 目录 Linux是什么&#xff1f; Linux常用命令介绍 命令提示…
阅读更多...
云服务器容器常用操作系统介绍

云服务器容器常用操作系统介绍

常用操作系统介绍 开源软件国内镜像源Alpine操作系统介绍镜像源修改镜像源apk包管理器 Debian操作系统介绍镜像源修改镜像源apt包管理器 ubuntu操作系统介绍修改镜像源apt包管理器 CentOS操作系统介绍修改镜像源yum包管理器 开源软件国内镜像源 名称地址南京大学mirror.nju.ed…
阅读更多...
【安全类书籍-2】Web渗透测试：使用Kali Linux

【安全类书籍-2】Web渗透测试：使用Kali Linux

目录 内容简介 作用 下载地址 内容简介 书籍的主要内容是指导读者如何运用Kali Linux这一专业的渗透测试平台对Web应用程序进行全面的安全测试。作者们从攻击者的视角出发，详细阐述了渗透测试的基本概念和技术，以及如何配置Kali Linux以适应渗透测试需求。书中不仅教授读者…
阅读更多...
初识Java篇（JavaSE基础语法）（1）

初识Java篇（JavaSE基础语法）（1）

个人主页&#xff08;找往期文章包括但不限于本期文章中不懂的知识点&#xff09;&#xff1a; 我要学编程(ಥ_ಥ)-CSDN博客 目录 前言&#xff1a; 初识Java 运行Java程序 注释 标识符 关键字 数据类型与变量 字面常量 数据类型 变量 类型转换 类型提升 字…
阅读更多...
Android Kotlin（五）数据流StateFlow和LiveData

Android Kotlin（五）数据流StateFlow和LiveData

Android 上的 Kotlin 数据流 在协程中&#xff0c;与仅返回单个值的挂起函数相反&#xff0c;数据流可按顺序发出多个值。数据流以协程为基础构建&#xff0c;可提供多个值。从概念上来讲&#xff0c;数据流是可通过异步方式进行计算处理的一组数据序列。所发出值的类型必须…
阅读更多...
【C语言】字符函数与字符串函数以及内存函数 { 超详细攻略，一篇学会 }

【C语言】字符函数与字符串函数以及内存函数 { 超详细攻略，一篇学会 }

今日分享&#xff1a;字符、字符串函数和内存函数 内存函数就是对内存进行操作的函数 字符串函数就是对字符串进行操作的函数 字符函数就是对字符进行操作的函数 str前缀的函数是字符串函数&#xff0c;头文件string.h mem前缀的函数是内存函数&#xff0c;头文件stdlib.h 字符…
阅读更多...
GEC6818——QT开发之两个UI界面切换与表格显示DHT11数据

GEC6818——QT开发之两个UI界面切换与表格显示DHT11数据

GEC6818——QT开发之两个UI界面切换与表格显示DHT11数据 使用环境: ubantu16 QT5.7 开发板GEC6818 实现要求&#xff1a; 利用A53按键1、按键2与温湿度传感器完成QT界面动态显示温湿度记录&#xff0c;并指定温湿度记录超过指定范围&#xff0c;进行报警&#xff08;LED&#…
阅读更多...
21-分支和循环语句_while语句（中）（初阶）

21-分支和循环语句_while语句（中）（初阶）

21-2 代码准备 getchar()&#xff1a;获取字符 int ch getchar(); //把获取的字符的ASCII码值放在ch中 int main() {int ch getchar();printf("%c\n", ch); //ch存的是该字符的ASCII码值&#xff0c;此处以字符形式打印ASCII码值对应的字符putchar(ch); } 运…
阅读更多...
MATLAB的多项式相加

MATLAB的多项式相加

多项式的加减在阶次相同的情况下可直接运算&#xff0c;若两个相加减的多项式阶次不同&#xff0c;则低阶多项式必须用零填补高阶项系数&#xff0c;使其与高阶多项式有相同的阶次。而且通常情况下&#xff0c;进行加减的两个多项 式的阶次不会相同&#xff0c;这时可以自定义一…
阅读更多...
最新文章

Copyright @ 2022~2023