【C++练级之路】【Lv.15】AVL树（双子旋转，领略绝对平衡之美）-Toy模板网

这篇具有很好参考价值的文章主要介绍了【C++练级之路】【Lv.15】AVL树（双子旋转，领略绝对平衡之美）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

【C++练级之路】【Lv.15】AVL树（双子旋转，领略绝对平衡之美）,进击的C++,数据结构世界,c++,开发语言,AVL树,数据结构,深度优先

快乐的流畅：个人主页 个人专栏：《C语言》《数据结构世界》《进击的C++》 远方有一堆篝火，在为久候之人燃烧！

引言

之前讲解了二叉搜索树，最优情况下它具有非常好的搜索性能，但是在极端场景下，它可能退化为单支树，可以形象地称为歪脖子树~

【C++练级之路】【Lv.15】AVL树（双子旋转，领略绝对平衡之美）,进击的C++,数据结构世界,c++,开发语言,AVL树,数据结构,深度优先
这样的话，它搜索的时间复杂度会从O(log₂N)退化为O(N²)，完全丧失了其优良的搜索性能。那么AVL树就可以登场了，它就是为解决这类问题而生的！

一、AVL树的概念

两位俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis在1962年发明了AVL树，AVL树满足两条性质：

它的左右子树都是AVL树
任意结点的左右子树高度差的绝对值不超过1

这样通过控制子树高度差，让AVL树几乎完美接近于平衡，便不会出现单支树的情况，保证了优良的搜索性能，因此AVL树又称为高度平衡二叉搜索树。

二、AVL树的模拟实现

2.1 结点

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

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

细节：

使用三叉链，增加了指向parent的指针
使用KV模型，数据存储键值对pair
结点存储平衡因子，用来记录左右子树高度差

注：平衡因子计算高度差，是右子树高度 - 左子树高度

2.2 成员变量

template<class K, class V>
class AVLTree
{
protected:
	typedef AVLTreeNode<K, V> Node;
public:
protected:
	Node* _root = nullptr;
};

2.3 插入

因为AVL树也是二叉搜索树，所以默认成员函数和遍历与之前写的没什么不同，这里重点讲解AVL树的插入。

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->_right)
		{
			++parent->_bf;
		}
		else
		{
			--parent->_bf;
		}

		if (parent->_bf == 1 || parent->_bf == -1)
		{
			parent = parent->_parent;
			cur = cur->_parent;
		}
		else if (parent->_bf == 0)
		{
			break;
		}
		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)
			{
				RotateLR(parent);
			}
			else if (parent->_bf == 2 && cur->_bf == -1)
			{
				RotateRL(parent);
			}
			else
			{
				assert(false);
			}
			break;
		}
		else
		{
			assert(false);
		}
	}

	return true;
}

思路：

以二叉搜索树的方式正常插入
讨论平衡因子，以及调整结构

这里的重点在于如何讨论和调整平衡因子(bf)。

首先，插入cur结点，调整parent结点的bf，左减右加
讨论parent的bf
- bf为0
- bf为1或-1
- bf为2或-2

bf为0时：
【C++练级之路】【Lv.15】AVL树（双子旋转，领略绝对平衡之美）,进击的C++,数据结构世界,c++,开发语言,AVL树,数据结构,深度优先
分析：此时没有增加高度，而是补上缺口，整棵树是平衡的，直接break即可

bf为1或-1时：
【C++练级之路】【Lv.15】AVL树（双子旋转，领略绝对平衡之美）,进击的C++,数据结构世界,c++,开发语言,AVL树,数据结构,深度优先
分析：此时增加了局部子树的高度，不确定有没有影响整体的高度差，所以要继续向上调整

parent = parent->_parent;
cur = cur->_parent;

bf为2或-2时：

此时bf已经超出平衡限制区间，需要进行结构调整，我们称之为旋转。

2.4 旋转

旋转分为两大类：单旋和双旋。而单旋分为左单旋和右单旋，双旋分为左右旋和右左旋。

2.4.1 左单旋

【C++练级之路】【Lv.15】AVL树（双子旋转，领略绝对平衡之美）,进击的C++,数据结构世界,c++,开发语言,AVL树,数据结构,深度优先

场景：右部外侧插入

过程：

parent接过subR的左子树subRL
subR左边再链接parent

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

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

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

	if (grandparent)
	{
		if (grandparent->_right == parent)
		{
			grandparent->_right = subR;
		}
		else
		{
			grandparent->_left = subR;
		}
	}
	else
	{
		_root = subR;
	}
	subR->_parent = grandparent;

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

细节：

大体是三步链接，注意双向链接
注意判空（subRL，grandparent）
如果判空，注意_root的传递
最后调整平衡因子_bf

2.4.2 右单旋

【C++练级之路】【Lv.15】AVL树（双子旋转，领略绝对平衡之美）,进击的C++,数据结构世界,c++,开发语言,AVL树,数据结构,深度优先

场景：左部外侧插入

过程：

parent接过subL的右子树subLR
subL右边再链接parent

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

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

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

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

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

细节：同左单旋

2.4.3 左右旋

【C++练级之路】【Lv.15】AVL树（双子旋转，领略绝对平衡之美）,进击的C++,数据结构世界,c++,开发语言,AVL树,数据结构,深度优先

场景：左部内侧插入

过程：

先对subL进行左单旋
再对parent进行右单旋

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

	RotateL(subL);
	RotateR(parent);

	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 if (bf == 0)
	{
		subL->_bf = 0;
		subLR->_bf = 0;
		parent->_bf = 0;
	}
	else
	{
		assert(false);
	}
}

细节：

这里旋转直接复用前面单旋的代码
主要的重点，在于平衡因子bf的讨论
- bf为1，在subLR的右侧插入
- bf为-1，在subLR的左侧插入
- bf为0，插入subLR（之前为空）

2.4.4 右左旋

【C++练级之路】【Lv.15】AVL树（双子旋转，领略绝对平衡之美）,进击的C++,数据结构世界,c++,开发语言,AVL树,数据结构,深度优先

场景：右部内侧插入

过程：

先对subR进行右单旋
再对parent进行左单旋

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

	RotateR(subR);
	RotateL(parent);

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

细节：同左右旋

综上所述，旋转的目的：保证平衡，同时降低树的高度。

三、AVL树的验证

我们主要验证左右子树高度是否平衡，即高度差是否小于等于1

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

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

	int leftH = Height(root->_left);
	int rightH = Height(root->_right);

	return leftH > rightH ? leftH + 1 : rightH + 1;
}

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

	int leftH = Height(root->_left);
	int rightH = Height(root->_right);

	if (rightH - leftH != root->_bf)
	{
		cout << root->_kv.first << "节点平衡因子异常" << endl;
		return false;
	}

	return abs(rightH - leftH) <= 1
		&& _IsBalance(root->_left)
		&& _IsBalance(root->_right);
}