【C++】AVL树

阿里云国内75折 回扣 微信号：monov8
阿里云国际，腾讯云国际，低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号：monov8 飞机：@monov6

​🌠 作者@阿亮joy.
🎆专栏《吃透西嘎嘎》
🎇 座右铭每个优秀的人都有一段沉默的时光那段时光是付出了很多努力却得不到结果的日子我们把它叫做扎根
在这里插入图片描述

目录

👉AVL树👈

AVL树的概念

二叉搜索树虽可以缩短查找的效率但如果数据有序或接近有序二叉搜索树将退化为单支树查找元素相当于在顺序表中搜索元素效率低下。因此两位俄罗斯的数学家 G.M.Adelson-Velskii 和 E.M.Landis 在 1962 年
发明了一种解决上述问题的方法当向二叉搜索树中插入新结点后如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整)即可降低树的高度从而减少平均搜索长度。

AVL 树也称为高度平衡二叉搜索树其满足以下性质

  • 它的左右子树都是 AVL 树注空树也是 AVL 树
  • 左右子树的高度差简称平衡因子的绝对值不超过 1-1 / 0 / 1注无法保证左右子树的高度差永远为 0
  • 平衡因子等于右子树高度减去左子树高度平衡因子是非必须的我们用的话方便实现 AVL 树。

在这里插入图片描述

如果一颗二叉搜索树是高度平衡的它就是 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树节点的定义

template <class K, class V>
struct AVLTreeNode
{
	AVLTreeNode<K, V>* _parent;	// 父节点
	AVLTreeNode<K, V>* _left;	// 左孩子
	AVLTreeNode<K, V>* _right;	// 右孩子

	pair<K, V> _kv;	// 键值对
	int _bf;	// balance factor(平衡因子)

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

AVL 树的节点是三叉链结构的因为插入节点可能会影响父节点的平衡因子有了指向父节点的指针会方便我们进行平衡因子的更新和旋转操作。新插入的节点的平衡因子都是 0。

AVL树的插入

AVL树就是在二叉搜索树的基础上引入了平衡因子因此AVL树也可以看成是二叉搜索树。那么AVL树的插入过程可以分为两步

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

调整节点的平衡因子

在这里插入图片描述

在这里插入图片描述

bool Insert(const pair<K, V>& kv)
{
	// 树为空,新插入的节点就是根节点
	if (_root == nullptr)
	{
		_root = new Node(kv);
		return true;
	}
	// 按照二叉搜索树的方式插入节点
	Node* parent = nullptr;
	Node* cur = _root;
	while (cur)
	{
		if (cur->_kv.first < kv.first)
		{
			parent = cur;
			cur = cur->_right;
		}
		else if (cur->_kv.first > kv.first)
		{
			parent = cur;
			cur = cur->_left;
		}
		else	// 树中已经存在Key
		{
			return false;
		}
	}

	// 插入节点
	cur = new Node(kv);
	// 判断在父节点的哪一边插入
	if (parent->_kv.first < kv.first)
		parent->_right = cur;
	else
		parent->_left = cur;

	cur->_parent = parent;

	// 控制平衡并更新平衡因子
	// 更新平衡因子的最坏情况需要更新到根节点
	while (parent)
	{
		// 新插入节点在父节点的右边,则父节点平衡因子自加一
		if (cur == parent->_left)
			--parent->_bf;
		else
			++parent->_bf;

		if (parent->_bf == 0)	// 不需要继续往上更新
		{
			break;
		}
		else if (abs(parent->_bf) == 1)	// 继续往上更新
		{
			parent = parent->_parent;
			cur = cur->_parent;
		}
		else if (abs(parent->_bf) == 2)
		{
			// 说明parent所在的子树已经不平衡了,需要旋转处理
			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)
				RotateLR(parent);
			else if (parent->_bf == 2 && cur->_bf == -1)
				RotateRL(parent);
			else	// 理论上不会走到这里
				assert(false);

			break;
		}
		else	// 理论上不会走到这里
		{
			assert(false);
		}
	}

	return true;
}

AVL树的旋转

如果在一棵原本是平衡的 AVL 树中插入一个新节点可能造成不平衡此时必须调整树的结构使之平衡化。根据节点插入位置的不同AVL 树的旋转分为四种左单旋、右单旋、左右双旋和右左双旋。注旋转操作可能对整棵树做也可能对子树做。旋转的原则是旋转成平衡数并且符合二叉搜索树的规则。一次插入最多一次旋转。

节点插入在较高右子树的右侧时需要左单旋

在这里插入图片描述
注当parent->_bf == 2 && cur->_bf == 1时此时需要对parent所在的子树进行左单旋。parent和subR不可能为空subRL可能为空。更新subR的父指针是需要需要parent是否是根节点。

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

	parent->_right = subRL;
	if (subRL)	// subRL不为空,其父指针且才能指向parent
		subRL->_parent = parent;
	// 记录parent的父亲
	Node* ppNode = parent->_parent;
	
	subR->_left = parent;
	parent->_parent = subR;
	// parent就是根节点时,则需要将subR更新为根节点,subR的父指针指向nullptr
	if (parent == _root)
	{
		_root = subR;
		subR->_parent = nullptr;
	}
	else
	{
		// 判断原父节点在左边还是右边
		if (ppNode->_left == parent)
			ppNode->_left = subR;
		else
			ppNode->_right = subR;

		subR->_parent = ppN
		ode;
	}
	// 更新平衡因子
	parent->_bf = subR->_bf = 0;
}

节点插入在较高左子树的左侧时需要右单旋。右单旋和左单旋是一致的。

在这里插入图片描述

注当parent->_bf == -2 && cur->_bf == -1时此时需要对parent所在的子树进行右单旋。parent和subL不可能为空subLR可能为空。更新subL的父指针是需要需要parent是否是根节点。

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

	parent->_left = subLR;
	// subLR不为空时,其父指针才能指向parent
	if (subLR)
		subLR->_parent = parent;

	Node* ppNode = parent->_parent;

	subL->_right = parent;
	parent->_parent = subL;
	// parent就是根节点时,则需要将subR更新为根节点,subR的父指针指向nullptr
	if (parent == _root)
	{
		_root = subL;
		subL->_parent = nullptr;
	}
	else
	{
		if (ppNode->_left == parent)
			ppNode->_left = subL;
		else
			ppNode->_right = subL;

		subL->_parent = ppNode;
	}
	// 更新平衡因子
	parent->_bf = subL->_bf = 0;
}

节点插入在较高左子树的右侧时需要左右双旋。当parent->_bf == -2 && cur->_bf == 1时需要进行左右双旋先对subL进行左单旋再对parent进行右单旋。

在这里插入图片描述
在这里插入图片描述

// 左右双旋
void RotateLR(Node* parent)
{
	Node* subL = parent->_left;
	Node* subLR = subL->_right;
	
	// 通过subLR的平衡因子来区分各种情况
	int bf = subLR->_bf;

	// 先左单旋再右单旋
	RotateL(subL);
	RotateR(parent);

	subLR->_bf = 0;
	if (bf == 1)	// 在c插入新节点
	{
		parent->_bf = 0;
		subL->_bf = -1;
	}
	else if (bf == 0)	// 新增节点就是自己
	{
		parent->_bf = 0;
		subL->_bf = 0;
	}
	else if (bf == -1)	// 在b插入新节点
	{
		parent->_bf = 1;
		subL->_bf = 0;
	}
	else	// 理论上不会走到这里
	{
		assert(false);
	}
}

节点插入在较高右子树的左侧时需要右左双旋。当parent->_bf == 2 && cur->_bf == -1时需要进行左右双旋先对subR进行右单旋再对parent进行左单旋。

在这里插入图片描述

// 右左双旋
void RotateRL(Node* parent)
{
	Node* subR = parent->_right;
	Node* subRL = subR->_left;

	// 通过subRL的平衡因子来区分各种情况
	int bf = subRL->_bf;

	// 先右单旋再左单旋
	RotateR(subR);
	RotateL(parent);

	subRL->_bf = 0;
	if (bf == 1)	// 在c插入新节点
	{
		parent->_bf = -1;
		subR->_bf = 0;
	}
	else if (bf == 0)	// 新增节点是自己
	{
		parent->_bf = 0;
		subR->_bf = 0;
	}
	else if (bf == -1)	// 在b插入新节点
	{
		parent->_bf = 0;
		subR->_bf = 1;
	}
	else	// 理论不会走到这里
	{
		assert(false);
	}
}

总结 假如以 pParent 为根的子树不平衡即 pParent 的平衡因子为 2 或者 -2分以下情况考虑

  1. pParent 的平衡因子为 2说明 pParent 的右子树高设 pParent 的右子树的根为 pSubR
    • 当 pSubR 的平衡因子为 1 时执行左单旋
    • 当 pSubR 的平衡因子为 -1 时执行右左双旋
  2. pParent 的平衡因子为 -2说明 pParent 的左子树高设 pParent 的左子树的根为 pSubL
    • 当 pSubL 的平衡因子为 -1 时执行右单旋
    • 当 pSubL 的平衡因子为 1 时执行左右双旋

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

现在已经将 AVL 树的旋转写完了那么现在就来验证一下写得对不对。

AVL树的验证

AVL 树是在二叉搜索树的基础上加入了平衡性的限制因此要验证 AVL 树可以分两步1、验证其为二叉搜索树如果中序遍历可得到一个有序的序列就说明为二叉搜索树。2、验证其为平衡树节点的平衡因子是否计算正确每个节点子树高度差的绝对值不超过 1(注意节点中如果没有平衡因子)。

public:
	// 判断是否是平衡树
	bool IsBalance()
	{
		return _IsBalance(_root);
	}
	// 中序遍历判断是否是二叉搜索树
	void InOrder()
	{
		return _InOrder(_root);
	}
	
private:
	// 求二叉树的高度
	int Height(Node* parent)
	{
		if (parent == nullptr)
			return 0;

		return max(Height(parent->_left), Height(parent->_right)) + 1;
	}
	
	bool _IsBalance(Node* root)
	{
		if (root == nullptr)
			return true;

		int leftHeight = Height(root->_left);
		int rightHeight = Height(root->_right);
		int diff = rightHeight - leftHeight;

		return abs(diff) < 2
			&& _IsBalance(root->_left)
			&& _IsBalance(root->_right);
	}

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

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

测试样例

void AVLTreeTest1()
{
	size_t N = 1000;
	srand(time(nullptr));
	AVLTree<int, int> t;

	for (size_t i = 0; i < N; ++i)
	{
		int x = rand();
		t.Insert(make_pair(x, i));
	}

	t.InOrder();
	cout << endl;
	cout << "IsBalance:" << t.IsBalance() << endl;
}

void AVLTreeTest2()
{
	int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };  // 测试双旋平衡因子调节
	//int a[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };
	AVLTree<int, int> t1;
	for (auto e : a)
	{
		t1.Insert(make_pair(e, e));
	}

	t1.InOrder();
	cout << "IsBalance:" << t1.IsBalance() << endl;
}

在这里插入图片描述
在这里插入图片描述

AVL树的删除(了解)

因为 AVL 树也是二叉搜索树可按照二叉搜索树的方式将节点删除然后再更新平衡因子。最差情况下需要一直要更新到根节点的位置。

具体实现大家可参考《算法导论》或《数据结构-用面向对象方法与C++描述》殷人昆版。

AVL树的性能

AVL 树是一棵绝对平衡的二叉搜索树其要求每个节点的左右子树高度差的绝对值都不超过 1这样可以保证查找高效的时间复杂度即 l o g 2 N log_2 N log2​N。但是如果要对 AVL 树做一些结构修改的操作性能非常低下。比如插入时要维护其绝对平衡旋转的次数比较多。更差的是在删除时有可能一直要让旋转持续到根的位置。因此如果需要一种查询高效且有序的数据结构而且数据的个数为静态的即不会改变可以考虑 AVL 树但一个结构经常修改就不太适合。

在这里插入图片描述

AVL树的完整代码

#pragma once

template <class K, class V>
struct AVLTreeNode
{
	AVLTreeNode<K, V>* _parent;
	AVLTreeNode<K, V>* _left;
	AVLTreeNode<K, V>* _right;

	pair<K, V> _kv;
	int _bf;	// balance factor

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

template <class K, class V>
class AVLTree
{
	typedef AVLTreeNode<K, V> Node;
public:
	bool Insert(const pair<K, V>& kv)
	{
		if (_root == nullptr)
		{
			_root = new Node(kv);
			return true;
		}

		Node* parent = nullptr;
		Node* cur = _root;
		while (cur)
		{
			if (cur->_kv.first < kv.first)
			{
				parent = cur;
				cur = cur->_right;
			}
			else if (cur->_kv.first > kv.first)
			{
				parent = cur;
				cur = cur->_left;
			}
			else
			{
				return false;
			}
		}

		// 插入节点
		cur = new Node(kv);
		// 判断在父节点的哪一边插入
		if (parent->_kv.first < kv.first)
			parent->_right = cur;
		else
			parent->_left = cur;

		cur->_parent = parent;

		// 控制平衡并更新平衡因子
		while (parent)
		{
			// 新插入节点在父节点的右边,则父节点平衡因子自加一
			if (cur == parent->_left)
				--parent->_bf;
			else
				++parent->_bf;

			if (parent->_bf == 0)
			{
				break;
			}
			else if (abs(parent->_bf) == 1)
			{
				//cur = parent;
				//parent = parent->_parent;
				parent = parent->_parent;
				cur = cur->_parent;
			}
			else if (abs(parent->_bf) == 2)
			{
				// 说明parent所在的子树已经不平衡了,需要旋转处理
				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)
					RotateLR(parent);
				else if (parent->_bf == 2 && cur->_bf == -1)
					RotateRL(parent);
				else
					assert(false);

				break;
			}
			else
			{
				assert(false);
			}
		}

		return true;
	}

	bool IsBalance()
	{
		return _IsBalance(_root);
	}

	void InOrder()
	{
		return _InOrder(_root);
	}

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

		parent->_right = subRL;
		if (subRL)
			subRL->_parent = parent;
		
		Node* ppNode = parent->_parent;

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

		if (parent == _root)
		{
			_root = subR;
			subR->_parent = nullptr;
		}
		else
		{
			// 判断原父节点在左边还是右边
			if (ppNode->_left == parent)
				ppNode->_left = subR;
			else
				ppNode->_right = subR;

			subR->_parent = ppNode;
		}

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

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

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

		Node* ppNode = parent->_parent;

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

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

			subL->_parent = ppNode;
		}

		parent->_bf = subL->_bf = 0;
	}
	// 左右双旋
	void RotateLR(Node* parent)
	{
		Node* subL = parent->_left;
		Node* subLR = subL->_right;
		
		// 通过subLR的平衡因子来区分各种情况
		int bf = subLR->_bf;

		// 先左单旋再右单旋
		RotateL(subL);
		RotateR(parent);

		subLR->_bf = 0;
		if (bf == 1)	// 在c插入新节点
		{
			parent->_bf = 0;
			subL->_bf = -1;
		}
		else if (bf == 0)	// 新增节点就是自己
		{
			parent->_bf = 0;
			subL->_bf = 0;
		}
		else if (bf == -1)	// 在b插入新节点
		{
			parent->_bf = 1;
			subL->_bf = 0;
		}
		else
		{
			assert(false);
		}
	}

	// 右左双旋
	void RotateRL(Node* parent)
	{
		Node* subR = parent->_right;
		Node* subRL = subR->_left;

		// 通过subRL的平衡因子来区分各种情况
		int bf = subRL->_bf;

		// 先右单旋再左单旋
		RotateR(subR);
		RotateL(parent);

		subRL->_bf = 0;
		if (bf == 1)	// 在c插入新节点
		{
			parent->_bf = -1;
			subR->_bf = 0;
		}
		else if (bf == 0)	// 新增节点是自己
		{
			parent->_bf = 0;
			subR->_bf = 0;
		}
		else if (bf == -1)	// 在b插入新节点
		{
			parent->_bf = 0;
			subR->_bf = 1;
		}
		else
		{
			assert(false);
		}
	}

	int Height(Node* parent)
	{
		if (parent == nullptr)
			return 0;

		return max(Height(parent->_left), Height(parent->_right)) + 1;
	}

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

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

	bool _IsBalance(Node* root)
	{
		if (root == nullptr)
			return true;

		int leftHeight = Height(root->_left);
		int rightHeight = Height(root->_right);
		int diff = rightHeight - leftHeight;

		return abs(diff) < 2
			&& _IsBalance(root->_left)
			&& _IsBalance(root->_right);
	}

private:
	Node* _root = nullptr;
};

👉总结👈

本篇博客主要讲解了什么是 AVL 树、AVL 树的插入、旋转、验证等等。那么以上就是本篇博客的全部内容了如果大家觉得有收获的话可以点个三连支持一下谢谢大家💖💝❣️

阿里云国内75折 回扣 微信号：monov8
阿里云国际，腾讯云国际，低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号：monov8 飞机：@monov6
标签: c++
返回列表

上一篇：Web Spider XHR断点 堆栈跟值 逆向案例（三）

下一篇：Vue3中操作dom的四种方式，建议收藏！！！

“【C++】AVL树” 的相关文章

把KMP算法嚼碎！（C++）1年前 (2023-02-02)
【PAT甲级 - C++题解】1040 Longest Symmetric String1年前 (2023-02-02)
【C++】面向对象---继承(万字详解)1年前 (2023-02-02)
OpenGL集锦(1)－安装与概述_c++ opengl1年前 (2023-02-02)
C++ 初了解模板1年前 (2023-02-02)
【C++】STL - Stack - Queue - PriorityQueue使用和模拟实现1年前 (2023-02-02)
c++基础篇之C++ STL 教程1年前 (2023-02-02)
C++ 基础语法6（构造函数、析构函数、拷贝、列表初始化、静态成员函数即变量）1年前 (2023-02-02)
【C++】string类的模拟实现1年前 (2023-02-02)
如何学习C++图像处理？1年前 (2023-02-02)

阿里云国际版