当前位置： 首页 > article >正文

Cpp::AVL树的机制详解与实现(23)

article 2025/1/5 8:07:52

文章目录

  • 前言
  • 一、何为AVL树？
  • 二、AVL树的节点定义
  • 三、AVL树的查找逻辑
  • 四、AVL树的插入逻辑
    • (1).当parent平衡因子从1/-1变到0
    • (2).当parent平衡因子从0变到1/-1，或者从1/-1变到2/-2
  • 五、AVL树的旋转逻辑
    • 一、右单旋
    • 二、左单旋
    • 三、右左双旋
    • 四、左右双旋
  • 六、AVL树的验证
    • 一、验证是否是二叉搜索树
    • 二、验证是否平衡
  • 七、AVL树的删除(了解)
  • 八、AVL树的性能分析
  • 总结

前言

  Hello，朋友们，我又回来啦！
  今天给大家带来AVL树的细致讲解，另外我想说的是，本节以及马上要学到的红黑树会是我们学习C++的道路上最难的部分，但是请大家不要放弃，毕竟关关难过关关过！

一、何为AVL树？

当一棵二叉搜索树为空树的时候，或者具备以下性质的时候，称之为AVL树：

  1. 它的左右子树都是AVL树
  2. 左右子树高度之差(简称平衡因子)的绝对值不超过1(-1/0/1)
  3. 平衡因子并不是必须，只是他的一种实现方式

我们可以思考下，为什么要在二叉搜索树的基础上再定义这么一个数据结构，事实上我们回想一下，我们可以发现虽然二叉搜索树理论上的搜索效率为O(logN)，但是万一数据成序排列，就会退化成单支树，甚至成了链表（

这就与我们最初的愿景相背离了，于是我们如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整)，即可降低树的高度，从而减少平均搜索长度

同时，如果节点数量为2或者4或者其他一些数据的时候，无法做到左右子树高度相等，所以退而求其次，我们让左右高度差不超过1

在这里插入图片描述

平衡因子：右子树高度 - 左子树高度

二、AVL树的节点定义

template<class K, class V>
struct AVLTreeNode
{
	pair<K, V> _kv;
	AVLTreeNode<K, V>* _left;
	AVLTreeNode<K, V>* _right;
	AVLTreeNode<K, V>* _parent;
	int _bf; // balance factor

	AVLTreeNode(const pair<K, V>& kv)
		:_kv(kv)
		,_left(nullptr)
		,_right(nullptr)
		,_parent(nullptr)
		,_bf(0)
	{}
};

AVL树每个结构存储一个pair<K, V>对象，其中需要parent指针目的是为了方便访问当前节点的上一个节点

三、AVL树的查找逻辑

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

这个跟二叉搜索树的查找逻辑没差

四、AVL树的插入逻辑

这个比较难，我们要重点学习

  既然AVL也是二叉搜索树，那么插入逻辑也是一样的，不同在于需要进行平衡因子的调正。(平衡因子 = 右子树高度 - 左子树高度)

  当插入节点结束后，对插入节点的父亲节点进行平衡因子的修改。当对于父亲节点达到特定值会对应不同的情况，不断利用parent向上调整父亲节点的平衡因子。

(1).当parent平衡因子从1/-1变到0

在这里插入图片描述

(2).当parent平衡因子从0变到1/-1，或者从1/-1变到2/-2

在这里插入图片描述

我们可以发现，当父亲节点变为0的时候，已经达到平衡；当变为1/-1的时候，需要向上调整；当变为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 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;
	}

五、AVL树的旋转逻辑

  首先我们要明白，如果将一整棵AVL树全部拆分进行研究，不同节点插入的位置很多选择，情况有很多种，难以全部罗列出来，而且没有必要，如果将一种有问题AVL树治好，就可以将任何该种AVL树治好，所以这边采用使用抽象图进行分析。

旋转完成后，原parent为根的子树个高度降低，已经平衡，不需要再向上更新

一、右单旋

此时 parent->_ bf == -2 && cur->_bf == -1

在这里插入图片描述
此时你需要注意：

  1. 30节点的右孩子可能存在，也可能不存在
  2. 60可能是根节点，也可能是子树
    如果是根节点，旋转完成后，要更新根节点
    如果是子树，可能是某个节点的左子树，也可能是右子树
	void RotateR(Node* parent)
	{
		Node* subL = parent->_left;
		Node* subLR = subL->_right;

		parent->_left = subLR;
		if (subLR)
			subLR->_parent = parent;

		Node* parentParent = parent->_parent;

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

		if (parentParent == nullptr)
		{
			_root = subL;
			subL->_parent = nullptr;
		}

		else 
		{
			if (parentParent->_left == parent)
				parentParent->_left = subL;

			else if (parentParent->_right == parent)
				parentParent->_right = subL;

			subL->_parent = parentParent;
		}

		parent->_bf = subL->_bf == 0;
	}

这里不需要考虑向上更新平衡因子，直接修改平衡因子就可以

二、左单旋

此时 parent->_ bf == 2 && cur->_bf == 1

在这里插入图片描述

要注意的地方同上

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

		parent->_right = subRL;
		if (subRL)
			subRL->_parent = parent;

		Node* parentParent = parent->_parent;

		subR->_left = parent;
		parent->_parent = subR;

		if (parentParent == nullptr)
		{
			_root = subR;
			subR->_parent = nullptr;
		}
		else 
		{
			if (parentParent->_left == parent)
				parentParent->_left = subR;

			else if (parentParent->_right == parent)
				parentParent->_right = subR;

			subR->_parent = parentParent;
		}

		parent->_bf = subR->_bf == 0;
	}

三、右左双旋

此时 parent->_bf == 2 && cur->_bf == -1

在这里插入图片描述
  由上图可以发现使用单旋的话是没有多大作用的，做无用功
  对此可以先对内部旋转变成单独一边高，再使用单旋进行调整AVL树

在这里插入图片描述

  这个时候就可以考虑复用我们之前写的左单旋和右单旋代码了

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

		RotateR(parent->_right);
		RotateL(parent);

		if (bf == 0)
		{
			subR->_bf = 0;
			subRL->_bf = 0;
			parent->_bf = 0;
		}

		else if (bf == 1)
		{
			subR->_bf = 0;
			subRL->_bf = 0;
			parent->_bf = -1;
		}

		else if (bf == -1)
		{
			subR->_bf = 1;
			subRL->_bf = 0;
			parent->_bf = 0;
		}

		else
		{
			assert(false);
		}
}

  这里还是需要根据60这块的平衡因子去判断的，b c分别给谁，会影响平衡因子的分配。左边新增两次旋转给到右边，右边新增两次旋转给到左边，通过结论最后修改平衡因子

四、左右双旋

此时 parent->_bf == -2 && cur->_bf == 1

在这里插入图片描述
  与上面同理，我们还是可以复用之前的左单旋或者右单旋代码，并且还是按照60这块的平衡因子去判断，最后通过画图来修改平衡因子

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

		RotateL(parent->_left);
		RotateR(parent);

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

六、AVL树的验证

一、验证是否是二叉搜索树

  二叉搜索树的中序遍历是有序排列，可以这一性质来判断

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

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

		_InOrder(root->_left);
		cout << root->_kv.first << ":" << root->_kv.second << endl;
		_InOrder(root->_right);
	}

二、验证是否平衡

  我们先来拼凑几个组件，我们主要检查以下两点

  1. 每个节点子树高度差的绝对值不超过1(注意节点种种那个如果没有平衡因子)
  2. 节点的平衡因子是否计算正确
bool isBalance()
{
    return _isBalance(_root);
}

int Height()
{
    return _Height(_root);
}

int Size()
{
    return _Size(_root);
}

private:
int _Size(Node* root)
{
	return root == nullptr ? 0 : _Size(root->_left) + _Size(root->_right) + 1;
}
	
int _Height(Node* root)
{
 	if (root == nullptr)
       return 0;
    return max(_Height(root->_left), _Height(root->_right)) + 1;
}

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->_kv.first << endl;
        return false;
    }

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

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

七、AVL树的删除(了解)

  其实跟插入也差不了太多，在这里就让大家自行去查找资料了~

八、AVL树的性能分析

  AVL树是一棵绝对平衡的二叉搜索树，其要求每个节点的左右子树高度差的绝对值都不超过1，所以做到了尽可能的压缩树的高度，以此来换取搜索的快速，但是但是如果要对AVL树做一些结构修改的操作，性能也就非常低下

插入时要维护其绝对平衡，旋转的次数比较多，更差的是在删除时，有可能一直要让旋转持续到根的位置

  如果需要一种查询高效且有序的数据结构，而且数据的个数为静态的(即不会改变)，可以考虑AVL树，但一个结构经常修改，就不太适合

所以有时候，我们也没有必要那么追求绝对，绝对意味着极端，往往这方面做得很好，别的地方却落下了
我们接下来要学习的红黑树就是这样，达到了插入和搜索两者都有着相对快速的速度

总结

  AVLTree.h源代码


http://www.kler.cn/a/457359.html

相关文章：

  • 【51单片机零基础-chapter6:LCD1602调试工具】
  • Dubbo 核心知识全解析：原理、流程与关键机制
  • kubelet状态错误报错
  • 设计模式 创建型 单例模式（Singleton Pattern）与 常见技术框架应用 解析
  • 代码随想录算法训练营第五十二天|KM101.孤岛的总面积|KM102.沉没孤岛|KM103.水流问题|KM104.建造最大岛屿
  • 前端异常处理合集
  • 产品原型设计
  • IntelliJ IDEA 远程调试
  • 在Ubuntu下通过Docker部署Misskey服务器
  • MATLAB语言的数据库编程
  • 基于STM32F103控制L298N驱动两相四线步进电机
  • 【递归与回溯深度解析：经典题解精讲（中篇）】—— LeetCode
  • 新版IDEA配置 Tomcat
  • 期末算法分析程序填空题
  • 32132132123
  • Leetcode经典题20--长度最小的子数组
  • SpringSecurity使用过滤器实现图形验证码
  • matlab smith自适应模糊PID房间湿度控制
  • 基于TCP的Qt网络通信
  • 【论文解读】Arbitrary-steps Image Super-resolution via Diffusion Inversion
  • UE4 编译报错 “Error LNK2019 : 无法解析的外部符号” 一种可能的原因
  • Flask使用的正例和反例
  • SpringBoot整合篇 05、Springboot整合Redission
  • flask-admin 模型视图（modelView）中重写after_model_delete与on_model_delete
  • 力扣-数据结构-6【算法学习day.77】
  • 李永乐线性代数：A可逆，AX=B相关推论和例题解题思路