AVL树的完全指南:平衡与性能

文章目录

  • AVL树简介
  • AVL的操作
    • 建立一个AVL树
    • 插入操作
    • 删除操作
  • 书写代码
    • 1.构造函数和析构函数
    • 2.获取最大值和最小值
    • 3.树的高度和节点个数
    • 3.前序中序和后序遍历
    • 4.判断树是否为空树
    • 5.四个旋转操作
    • 6.获取平衡因子
    • 7.插入操作
    • 8.删除操作
    • 9.搜索节点
    • .h文件中的定义
  • 总结

在这里插入图片描述

AVL树简介

AVL树是一种自平衡的二叉搜索树,它的命名来源于其发明者 G. M. Adelson-Velsky 和 E. M. Landis。AVL树通过保持树的平衡性来提高搜索、插入和删除操作的效率。
在AVL树中,每个节点都有一个平衡因子,它表示节点的左子树高度与右子树高度的差值。平衡因子可以是-1、0或1,如果任何节点的平衡因子的绝对值大于1,则该树就不平衡,需要进行平衡调整。

AVL树本质也是一颗二叉查找树
但是在二叉查找树上加了平衡的概念,因为二叉查找树有很多限制的因素,当二叉查找树的节点呈线性分布的时候,整个二叉查找树就的效率就变成O(N),所以在AVL树中就不存在不平衡的情况。

1.AVL树的特点:

  1. 左子树和右子树的高度差不大于1。
  2. 左子树和右子树的子树也是一颗AVL树

2.AVL树的相关概念

  1. 平衡因子:节点的平衡因子=左子树的高度-右子树的高度在这里插入图片描述
    注意看上面的图上面的等式分别都代表了每个节点的平衡因子

3.AVL树对比普通二叉搜索树
2. 平衡性保证: AVL树保持了树的平衡性,即任何时刻树中任意节点的左右子树高度差不超过1。而普通的二叉搜索树可能会因为插入或删除操作而导致树的不平衡,从而影响了搜索、插入和删除操作的性能。

  1. 稳定的性能: 由于AVL树的平衡性,搜索、插入和删除操作的时间复杂度始终保持在 O(log n) 的水平,其中 n 表示树中节点的数量。而普通的二叉搜索树在最坏情况下可能会退化成链表,导致搜索、插入和删除操作的时间复杂度上升至 O(n)。

  2. 高效的搜索操作: AVL树的平衡性保证了树的高度始终保持在较小的范围内,使得搜索操作非常高效。而普通的二叉搜索树可能会因为不平衡而导致搜索操作的性能下降。

  3. 快速的插入和删除操作: AVL树的自平衡性保证了插入和删除操作的高效性,使得这些操作的时间复杂度始终为 O(log n)。而普通的二叉搜索树在插入或删除节点后可能需要进行额外的平衡调整操作,导致性能下降。

  4. 适用于高性能需求的场景: 由于AVL树在搜索、插入和删除操作上的高效性,它常被用作数据库中的索引结构,以提供快速的数据检索功能。而普通的二叉搜索树可能无法满足高性能的需求。

最直接的:
在这里插入图片描述

AVL的操作

建立一个AVL树

首先AVL树和二叉树一样,需要一个左子树和右子树的索引,还有需要一个存储值的关键字,除此之外,我们还需要保存当前节点的高度,因为在AVL树当中涉及到了高度之差,如果我们将当前节点的高度保存起来,就不用每次去计算了

代码:

class AVLNode
{
	friend class AVLTree;
public:

private:
	AVLNode* _left;
	AVLNode* _right;
	int _key;
	int _height;
};


class AVLTree
{
public:

private:
	AVLNode* _root;
};

**这里我们用两个类来定义AVL树,比较方便,一个类定义节点,一个类维护节点

插入操作

当当前节点的平衡因子为0的时候,下一个值随便怎么插入都不会影响平衡,而当当前节点的平衡因子等于1的时候,下一个值插入的位置就会影响当前节点的平衡了,插入操作一共分为四种情况,我们一一介绍:

1.右旋
在这里插入图片描述

首先我们看上面这张图,当我们插入一个新的节点0时,很显然10的平衡因子是2,已经超过了AVL树定义的最大的平衡因子,所以,我们要对上面这颗树进行旋转让其满足AVL树的要求.
很显然,只需要将10右旋,然后让7作为10和4的新的父亲节点就可以了。
动图展示:
在这里插入图片描述

第二种需要右旋的情况:
在这里插入图片描述

这里只需要记住,,当我们要右旋时,冲突的右孩子作为新的左孩子就行了。
2.左旋

在这里插入图片描述
同样的,上面这个AVL树中的7的平衡因子的绝对值已经超过了1,所以应该对其进行旋转,由于4的平衡是-2,7的平衡因子是-1,,所以这种情况也被称之为RR型,对于这种RR型我们只需要对其进行一次右旋就可以解决问题了。
动图展示:
在这里插入图片描述
还有一种复杂的清情形:
在这里插入图片描述
先右旋再左旋
在这里插入图片描述

对于上面的AVL树,E是新插入的节点,首先这颗树的A节点的平衡因子是-2,然后就是C的平衡因子是1,这种情况我们把它叫做RL型,只需要对平衡因子是1的节点先进行右旋,然后再对平衡因子是A的节点进行左旋就可以了。

先左旋再右旋
在这里插入图片描述

6是最后插入的节点对于这种情况,1的平衡因子是2,而2的平衡因子是-1.这种情况被称为是LR型,只需要先对平衡因子为-1的节点先左旋,然后再对平衡因子是2的节点进行右旋即可。

删除操作

删除操作和插入操作类似,再每次删除之后都要对祖先节点的平衡因子进行检查。

书写代码

1.构造函数和析构函数

//构造函数
AVLTree::AVLTree(AVLNode* root) :_root(root) {}

//析构函数
AVLTree::~AVLTree()
{
	clear(_root);
}
void AVLTree::clear(AVLNode* node)
{
	if (node == nullptr)
	{
		return;
	}
	clear(node->_left);
	clear(node->_right);
	delete node;
}

2.获取最大值和最小值

//获取最小值
int AVLTree::getMin()
{
	if (_root == nullptr)
	{
		return INT_MIN;
	}
	AVLNode* root = _root;
	while (root->_left != nullptr)
	{
		root = root->_left;
	}
	return root->_key;
}

//获取最大值
int AVLTree::getMax()
{
	if (_root == nullptr)
	{
		return INT_MAX;
	}
	AVLNode* root = _root;
	while (root->_right != nullptr)
	{
		root = root->_right;
	}
	return root->_key;
}
//函数重载,用于返回节点
AVLNode* AVLTree::getMin(AVLNode* node)
{
	if (node == nullptr)
	{
		return nullptr;
	}
	while (node->_left != nullptr)
	{
		node = node->_left;
	}
	return node;
}

3.树的高度和节点个数

//获取AVL树的节点的个数
int AVLTree::AssistgetSize(AVLNode* root)
{
	if (root == nullptr)
	{
		return 0;
	}
	return AssistgetSize(root->_left) + AssistgetSize(root->_right) + 1;
}
int AVLTree::getSize()
{
	return AssistgetSize(_root);
}
//获取高度
int AVLTree::getHeight()
{
	return AssistgetHeight(_root);
}
int AVLTree::AssistgetHeight(AVLNode* root)
{
	if (root == nullptr)
	{
		return 0;
	}
	return root->_height;
}

3.前序中序和后序遍历

//中序遍历
void AVLTree::AssistinOrderTraversal(AVLNode* _root)
{
	if (_root == nullptr)
	{
		return;
	}
	AssistinOrderTraversal(_root->_left);
	cout << _root->_key << ' ';
	AssistinOrderTraversal(_root->_right);
}
void AVLTree::inOrderTraversal()
{
	AssistinOrderTraversal(_root);
}

//前序遍历
void AVLTree::preOrderTraversal()
{
	AssistpreOrderTraversal(_root);
}
void AVLTree::AssistpreOrderTraversal(AVLNode* root)
{
	if (root == nullptr)
	{
		return;
	}
	cout << root->_key << ' ';
	AssistpreOrderTraversal(root->_left);
	AssistpreOrderTraversal(root->_right);
}
//后序遍历
void AVLTree::AssistpostOrderTraversal(AVLNode* root)
{
	if (root == nullptr)
	{
		return;
	}
	AssistpostOrderTraversal(root->_left);
	AssistpostOrderTraversal(root->_right);
	cout << root->_key << ' ';
}
void AVLTree::postOrderTraversal()
{
	AssistpostOrderTraversal(_root);
}

4.判断树是否为空树

//判空
bool AVLTree::isEmpty()
{
	return _root == nullptr;
}

5.四个旋转操作

/左旋
void AVLTree::leftRotate(AVLNode*& node)
{
	AVLNode* right = node->_right;
	node->_right = right->_left;
	right->_left = node;
	node = right;
}
//右旋
void AVLTree::rightRotate(AVLNode*& node)
{
	AVLNode* left = node->_left;
	node->_left = left->_right;
	left->_right = node;
	node = left;
}
//先右旋再左旋
void AVLTree::rightleftRotate(AVLNode*& node)
{
	rightRotate(node->_right);
	leftRotate(node);
}
//先左旋再右旋
void AVLTree::leftrightRotate(AVLNode*& node)
{
	leftRotate(node->_left);
	rightRotate(node);
}

6.获取平衡因子

int AVLTree::getbalance(AVLNode* root)
{
	return AssistgetHeight(root->_left) - AssistgetHeight(root->_right);
}

7.插入操作

AVLNode* AVLTree::AssistInsert(int key, AVLNode*& node)
{
	if (node == nullptr)
	{
		node = new AVLNode(key, nullptr, nullptr);
		return node;
	}
  	else if (node->_key > key)
	{
		AssistInsert(key, node->_left);
		//判断平衡因子是否是2,判断是LL型还是LR型
		if (getbalance(node) == 2)
		{
			//LL
			if (getbalance(node->_left) == 1)
			{
				//右旋
				rightRotate(node);
			}
			//LR
			else
			{
				//先左旋再右旋
				leftrightRotate(node);
			}
		}
	}
	else if (node->_key < key)
	{
		//向右边插入
		AssistInsert(key, node->_right);
		//如果是-2,那就是RR型或者是RL型
		if (getbalance(node) == -2)
		{
			//RR
			if (getbalance(node->_right) == -1)
			{
				//左旋
				leftRotate(node);
			}
			//RL
			else
			{
				//先右旋再左旋
				rightleftRotate(node);
			}
		}
	}
	node->_height = max(AssistgetHeight(node->_left), AssistgetHeight(node->_right)) + 1;
	return node;
}

void AVLTree::Insert(int key)
{
	_root = AssistInsert(key, _root);
}

8.删除操作

AVLNode* AVLTree::Assistremove(int key, AVLNode*& node)
{
	if (node == nullptr)
	{
		//空节点不需要删除直接返回nullptr
		return nullptr;
	}
	//要删除的值小于当前节点的值
	if (node->_key > key)
	{
		//递归左子树
		node->_left = Assistremove(key, node->_left);
	}
	//删除值大于当前节点的值
	else if (node->_key < key)
	{
		//递归右子树
		node->_right = Assistremove(key, node->_right);
	}
	else
	{
		//1.左子树是空树,右子树和左子树都是空树
		if (node->_left == nullptr)
		{
			AVLNode* tmp = node->_right;
			delete node;
			return tmp;
		}
		//只有右子树是空树的时候
		if (node->_right == nullptr)
		{
			AVLNode* tmp = node->_left;
			delete node;
			return tmp;
		}
		//左子树和右子树都不是空树时
		else
		{
			//找到右子树的最小值节点
			AVLNode* min = getMin(node->_right);
			//赋值
			node->_key = min->_key;
			//将删除有左子树和右子树的节点转换为删除末尾的节点
			node->_right = Assistremove(min->_key, node->_right);
		}
	}
	node->_height = max(AssistgetHeight(node->_left), AssistgetHeight(node->_right)) + 1;
	int balance = getbalance(node);
	if (balance == 2)
	{
		if (getbalance(node->_left) == 1)
		{
			rightRotate(node);
		}
		else
		{
			leftrightRotate(node);
		}
	}
	else if (balance == -2)
	{
		if (getbalance(node->_right) == -1)
		{
			leftRotate(node);
		}
		else
		{
			rightleftRotate(node);
		}
	}
	return node;
}
void AVLTree::remove(int key)
{
	_root = Assistremove(key, _root);
}

9.搜索节点

//搜索
bool AVLTree::search(int key, AVLNode* node)
{
	if (node == nullptr)
	{
		return false;
	}
	if (node->_key == key)
	{
		return true;
	}
	if (node->_key > key)
	{
		return search(key, node->_left);
	}
	else
	{
		return search(key, node->_right);
	}
}
bool AVLTree::search(int key)
{
	return search(key, _root); 
}

上面的代码对照着图理解更容易理解

.h文件中的定义

class AVLNode
{
	friend class AVLTree;
public:
	AVLNode(int key, AVLNode* left, AVLNode* right, int hight = 0)
	{
		_key = key;
		_left = left;
		_right = right;
		_height = hight;
	}
private:
	AVLNode* _left;
	AVLNode* _right;
	int _key;
	int _height;
};


class AVLTree
{
public:
	AVLTree(AVLNode* root = nullptr);
	~AVLTree();

	int getbalance(AVLNode* root);

	AVLNode* AssistInsert(int key, AVLNode*& node);
	void Insert(int key);

	void leftRotate(AVLNode*& node);
	void rightRotate(AVLNode*& node);
	void rightleftRotate(AVLNode*& node);
	void leftrightRotate(AVLNode*& node);

	AVLNode* Assistremove(int key, AVLNode*& node);
	void remove(int key);

	bool search(int key);
	bool search(int key, AVLNode* node);

	int getMin();
	AVLNode* getMin(AVLNode* node);
	int getMax();
	int AssistgetHeight(AVLNode* root);
	int getHeight();

	void inOrderTraversal();
	void AssistinOrderTraversal(AVLNode* _root);
	void preOrderTraversal();
	void AssistpreOrderTraversal(AVLNode* _root);
	void postOrderTraversal();
	void AssistpostOrderTraversal(AVLNode* _root);

	int getSize();
	int AssistgetSize(AVLNode* root);
	void clear(AVLNode* node);
	bool isEmpty();
private:
	AVLNode* _root;
};

总结

在本篇博客中,我们深入探讨了 AVL 树这一经典的数据结构。AVL 树作为一种自平衡的二叉搜索树,通过保持树的平衡性,提供了高效的搜索、插入和删除操作。我们从 AVL 树的基本概念出发,介绍了它的定义、特性和基本操作,包括旋转操作和平衡因子的概念。通过具体的例子和图示,我们深入理解了 AVL 树的工作原理和算法设计。

AVL 树之所以如此重要和受欢迎,主要是因为它在各种应用中都具有突出的优势。无论是作为数据库索引、编译器中的符号表还是操作系统中的文件系统,AVL 树都能够提供高效的数据检索功能,保证了程序的性能和效率。通过学习和掌握 AVL 树,我们不仅可以解决实际问题,提高程序的性能,还能够深入理解和应用其他复杂数据结构,为我们的编程技能和软件工程能力增添新的高度。

希望通过本篇博客的阅读,读者能够对 AVL 树有一个更加深入的理解,并且能够将其应用到实际的项目中去,为软件开发和数据处理带来更大的价值。感谢大家的阅读和支持!

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

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

相关文章

Linux---vim编辑器(续写)

5. vim正常模式命令集 插入模式 按「i」切换进入插入模式「insert mode」&#xff0c; 按“i”进入插入模式后是从光标当前位置开始输入文件&#xff1b; 按「a」进入插入模式后&#xff0c;是从目前光标所在位置的下一个位置开始输入文字&#xff1b; 按「o」进入插入模式…

未来相遇过去:博物馆藏品管理平台的科技革新之旅

引言&#xff1a; 尊重历史&#xff0c;意味着保护其实体的载体。在博物馆这个时间的容器中&#xff0c;每一件藏品都承载着人类文明的印记&#xff0c;它们是历史的低语&#xff0c;是过去对现在的细语。在这篇文章中&#xff0c;我将带您走进博物馆的幕后&#xff0c;探究藏品…

基于SSM的“图书仓储管理系统”的设计与实现(源码+数据库+文档)

基于SSM的“图书仓储管理系统”的设计与实现&#xff08;源码数据库文档) 开发语言&#xff1a;Java 数据库&#xff1a;MySQL 技术&#xff1a;SSM 工具&#xff1a;IDEA/Ecilpse、Navicat、Maven 系统展示 系统功能结构图 系统登录页面 人员管理信息页面 添加人员信息页…

全球静态住宅IP:网络时代的稳定之锚

在数字化浪潮席卷全球的今天&#xff0c;网络已经成为人们生活和工作中不可或缺的一部分。而在网络世界中&#xff0c;IP地址作为设备的重要身份标识&#xff0c;其稳定性和安全性显得尤为重要。全球静态住宅IP&#xff0c;以其独特的稳定性和安全性&#xff0c;为广大用户提供…

EdgeOne 免费证书快速实现网站 HTTPS 访问

在当今互联网环境下&#xff0c;HTTPS访问已经成为现代网站的必备功能。HTTPS 访问不仅能够更有效地保障用户在访问到网站时的数据安全传输&#xff0c;防止信息泄露、消息劫持等问题&#xff0c;在搜索引擎中&#xff0c;未实现 HTTPS 还会被浏览器提示为不安全网站&#xff0…

文件操作IO网络编程网络原理

​ 文件操作—IO 文件在计算机中可以代表很多东西 在操作系统中, 文件主要是指硬盘文件 硬盘主要分为机械硬盘和固态硬盘。机械硬盘通过磁头在旋转的磁盘上读取数据&#xff0c;适合顺序读取。而固态硬盘则使用闪存芯片来存储数据&#xff0c;没有机械部件&#xff0c;因此读…

怎么通过微信小程序实现远程控制8路控制器/断路器

怎么通过微信小程序实现远程控制8路控制器/断路器呢&#xff1f; 本文描述了使用微信小程序调用HTTP接口&#xff0c;实现控制8路控制器/断路器&#xff0c;支持8路输出&#xff0c;均可独立控制&#xff0c;可接入各种电器。 可选用产品&#xff1a;可根据实际场景需求&#…

GStreamer中如何自定义配置线程优先级

1.引言 如果看了gstreamer官方教程配置多线程出现编译不过的问题了&#xff0c;不妨进来看看这篇文章或许能解决一些编译问题。 GStreamer 本质上是多线程的&#xff0c;并且是完全线程安全的。大多数线程内部对应用程序是隐藏的&#xff0c;这应该使应用程序开发更容易。但是&…

R语言:肿瘤突变负荷分析

> merge_maf <- function(metadata, path){ #通过合并path,还有sample sheet前两列得到每一个文件的完整路径 filenames <- file.path(path, metadata$file_id, metadata$file_name, fsep .Platform$file.sep) message (##############…

RabbitMQ的用途

RabbitMQ主要有四个用途&#xff0c;分别是应用解耦、异步提速、削峰填谷、消息分发。详情讲解如下&#xff1a; RabbitMQ介绍、解耦、提速、削峰、分发 详解、RabbitMQ安装 可视化界面讲解 1.应用解耦&#xff1a;提高系统容错性和可维护性 2.异步提速&#xff1a;提升用户体验…

【JVM基础篇】打破双亲委派机制

文章目录 打破双亲委派机制自定义类加载器双亲委派机制核心代码打破双亲委派机制自定义类加载器父类怎么是AppClassLoader呢&#xff1f;两个自定义类加载器加载相同限定名的类&#xff0c;不会冲突吗&#xff1f;拓展类加载器功能 线程上下文类加载器JDBC案例那么问题来了&…

打造本地GPT专业领域知识库AnythingLLM+Ollama

如果你觉得openai的gpt没有隐私&#xff0c;或者需要离线使用gpt&#xff0c;还是打造专业领域知识&#xff0c;可以借用AnythingLLMOllama轻松实现本地GPT. AnythingLLMOllama 实现本地GPT步聚&#xff1a; 1 下载 AnythingLLM软件 AnythingLLM官网地址&#xff1a; Anythi…

C++17新特性 结构化绑定

一、Python中的相似功能 熟悉python的应该对下面的代码很熟悉 def return_multiple_values():return 11, 7x, y return_multiple_values()函数返回一个元组&#xff0c;元组自动分配给了x和y。 二、C11中的元组 c11中就存在类似python元组的概念了&#xff1a; std::tupl…

高速电流反馈运放总结

目录 前言 基础架构 CFB运算放大器拓扑结构的进步 前言 最近项目发现有震荡&#xff0c;发现是电流反馈型运放导致&#xff0c;所以对电流运放的知识做了全面的复习。 基础架构 现在&#xff0c;我们将详细考察高速运算放大器中非常流行的电流反馈(CFB)运算放大器拓扑结 构…

黑盒测试中的边界值分析

黑盒测试是一种基于需求和规格的测试方法&#xff0c;它主要关注软件系统输出的正确性和完整性&#xff0c;而不考虑内部代码的实现方式。在黑盒测试中&#xff0c;边界值分析是一种重要的测试技术&#xff0c;它可以帮助测试人员有效地发现输入和输出的问题。本文将从什么是边…

【数据结构】二叉排序树(查找+插入+删除+效率分析)完整代码+解析

3.1 二叉排序树 3.1.1 定义 二叉排序树的定义 又称二叉查找树&#xff08;BST&#xff0c;Binary Search Tree&#xff09; 二叉排序树是具有以下性质的二叉树&#xff1a; 左子树结点值<根结点值<右子树结点值 进行中序遍历&#xff0c;可以得到一个递增的有序序列。 3…

无需公网IP、无需云服务器,异地组网实现远程直连NAS、游戏联机

手机图片、视频太多&#xff0c;存储空间不够用怎么办?出门在外无法直连家中NAS&#xff0c;远程访问NAS速度慢&#xff1f;自建私有云、多媒体服务器&#xff0c;如何多人远程共享媒体资源&#xff1f;幻兽帕鲁、我的世界、泰拉瑞亚…局域网游戏&#xff0c;想远程多人联机&a…

Golang面向对象编程(二)

文章目录 封装基本介绍封装的实现工厂函数 继承基本介绍继承的实现字段和方法访问细节多继承 封装 基本介绍 基本介绍 封装&#xff08;Encapsulation&#xff09;是面向对象编程&#xff08;OOP&#xff09;中的一种重要概念&#xff0c;封装通过将数据和相关的方法组合在一起…

RobbitMQ基本消息队列的消息接收

1.先给工程引入依赖 父工程有了子工程就不用导了 <!--AMQP依赖&#xff0c;包含RabbitMQ--> <dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-amqp</artifactId> </dependency> 2.配置yml…

基于大数据+Hadoop的豆瓣电子图书推荐系统设计和实现

博主介绍&#xff1a;✌全网粉丝30W,csdn特邀作者、博客专家、CSDN新星计划导师、Java领域优质创作者,博客之星、掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域和学生毕业项目实战,高校老师/讲师/同行交流合作✌ 主要内容&#xff1a;SpringBoot、Vue、SSM、HLM…