数据结构进阶——AVL树

学习本章，需要大家先掌握搜索二叉树，了解键值对pair。int _bf;// balance factor 平衡因子, _kv(kv), _bf(0){}该节点的定义是一个三叉链，_left和_right分别指向左右子树，_parent指向父节点；节点中存储的有效数据为pair，类型的键值对；_bf为平衡因子，在此我们定义为右树高度减去左树高度，用来控制左右子树的高度（注意：平衡因子只是其中一种控

-指短琴长-

1367人浏览 · 2024-06-09 23:23:55

-指短琴长- · 2024-06-09 23:23:55 发布

数据结构进阶——AVL树

0. 前言
1. AVL树的概念
2. AVL树节点，和树的定义
3. AVL树的插入
4. AVL树的旋转
5. AVL树的验证
6. AVL树的删除（了解）
7. AVL树实现完整代码
8. AVL树的性能
9. AVL的封装，终极版本

0. 前言

学习本章，需要大家先掌握搜索二叉树，了解键值对pair。

学习搜索二叉树点击此处：https://blog.csdn.net/weixin_73870552/article/details/138686066?spm=1001.2014.3001.5501

1. AVL树的概念

1. 搜索二叉树的弊端：

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

2. AVL树的性质：

在这里插入图片描述

左右子树都是AVL树；
左右子树高度之差（简称平衡因子）的绝对值不超过1；
空树是AVL树。

如果一棵二叉搜索树是高度平衡的，它就是AVL树。如果它有n个结点，其高度可保持在 $O(log_2 n)$ ，搜索时间复杂度 $O(log_2 n)$ 。

2. AVL树节点，和树的定义

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)
	{}
};

该节点的定义是一个三叉链，_left和_right分别指向左右子树，_parent指向父节点；
节点中存储的有效数据为pair<K, V>，类型的键值对；
_bf为平衡因子，在此我们定义为右树高度减去左树高度，用来控制左右子树的高度（注意：平衡因子只是其中一种控制平衡的手段，并不是唯一的）；
定义了一个模版构造函数，以便后续使用。

2. 树：

template<class K, class V>
class AVLTree
{
	typedef AVLTreeNode<K, V> Node;
public:
	...

private:
	Node* _root = nullptr;
	size_t _size = 0;
};

_size记录树中一共有多少数据（多少节点）。

3. AVL树的插入

1. 思路：

AVL树就是在搜索二叉树的基础上引入了平衡因子，因此AVL树也可以看成是搜索二叉树。那么AVL树的插入过程可以分为两步：
- 按照二叉搜索树的方式插入新节点；
- 调整节点的平衡因子。
调整平衡因子的过程，又可以细分为两部分：
- 平衡因子的更新；
- 节点的调整（旋转）+ 平衡因子的更新。

1. 模拟插入过程（红色节点表示新插入节点）：

在这里插入图片描述

插入新节点后，第一件事，是更新该新节点的父亲的平衡因子：
- 新增节点在左，父亲bf--；
- 新增节点在右，父亲bf++。
更新完该新节点的父亲后，还要判断是否需要往上更新（新增节点可能会影响祖先，但是一定不会影响兄弟）：
- 更新后，父亲bf == 0，父亲所在的子树高度不变，不用再继续往上更新了，插入结束。（ps：在插入节点前，父亲bf == 1 or -1，子树一边高，一边低，新插入节点填补低的那边）
- 更新后，父亲bf == 1 or -1，父亲所在的子树高度变了，需要继续往上更新。（ps：在插入节点前，父亲bf == 0，两边一样高，插入新节点导致高度变化）
- 更新后，父亲bf == 2 or -2，父亲所在的子树不平衡，需要旋转调整。

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);
			_size++;
			return true;
		}

		// 通过parent向上找父节点
		Node* parent = nullptr;
		Node* cur = _root;

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

		cur = new Node(kv);
		if (kv.first > parent->_kv.first)
		{
			parent->_right = cur;
			cur->_parent = parent;
		}
		else
		{
			parent->_left = cur;
			cur->_parent = parent;
		}

		_size++;
		
		// 调整，AVL树的核心部分

		while (parent)
		{
			// 平衡因子的更新
			if (cur == parent->_left)
			{
				// 插入在左节点，_bf--
				parent->_bf--;
			}
			else
			{
				// 插入在右节点，_bf++
				parent->_bf++;
			}
			
			// 判断是否要继续向上更新，和是否旋转调整
			if (parent->_bf == 0)
			{
				// 更新后 _bf == 0，说明子树高度不变，不需要往上更新
				break;
			}
			else if (parent->_bf == 1 || parent->_bf == -1)
			{
				// 更新后子树高度改变，需要往上更新
				cur = parent;
				parent = parent->_parent;
			}
			else if (parent->_bf == 2 || parent->_bf == -2)
			{
				// 旋转调整
				...
			}
			else
			{
				// 平衡因子绝对值大于2，直接报错
				assert(false);
			}
		}

		return true;
	}

	...

private:
	Node* _root = nullptr;
	size_t _size = 0;
};

4. AVL树的旋转

如果在一棵原本是平衡的AVL树中插入一个新节点，可能造成不平衡，此时必须调整树的结构，使之平衡化。根据节点插入位置的不同，AVL树的旋转分为四种：

1. 新节点插入较高左子树的左侧—右右：左单旋

先考虑一种最简单的场景（场景1）：
- 直接将8节点链接到9节点的左边即可。
再看一种更复杂的场景（场景2）：
- 需要将13节点链接到9节点的右子树，将9节点链接到15节点的左子树。
还有更加复杂的情况，但是我们可以对所有的情况进行一个归类，画出抽象图：
- a，b，c 都是高度为h的AVL平衡树；
- 只需要将b框中的节点（subRL），链接到30节点（parent）的右子树（将60节点的左子树链接到30节点的右边）；再将30节点（parent），连接到60节点（subR）的左子树即可。（别忘了是三叉链，要同步更新父节点）
- 旋转完后别忘了更新平衡因子，左单旋后，parent和subR节点的_bf都为0，其余节点的平衡因子均不会受到印象。
- h = 0时，就对应场景1的情况；h = 1时，就对应场景2的情况。

在这里插入图片描述

代码实现：
- 注意，在更新subRL节点的父节点时，需要先判断subRL是否为空（h=0的情况），如果为空，就不要访问subRL了；
- 还需要记录parent的父节点，方便旋转后将subR链接给parent->_parent，和整棵树链接起来；
- 当parent就是根节点时，需要特殊处理，要更新根节点为subR。

template<class K, class V>
class AVLTree
{
	typedef AVLTreeNode<K, V> Node;
public:
	// 左单旋
	void RotateL(Node* parent)
	{
		Node* subR = parent->_right;
		Node* subRL = subR->_left;

		// 更新左右节点
		parent->_right = subRL;
		subR->_left = parent;

		// 提前记录parent的parent
		Node* parentParent = parent->_parent;

		// 更新_parent
		parent->_parent = subR;
		if (subRL)	// 判断为不为空，subRL是唯一一个可能为空的节点
		{
			subRL->_parent = parent;
		}

		// 处理根，将旋转后的子树和整个树链接
		if (_root == parent)
		{
			// 如果parent原来是root根节点，就让subR成为新的根节点
			_root = subR;
			subR->_parent = nullptr;
		}
		else if (parentParent->_left == parent)
		{
			// parent原来在左子树，就和左子树链接
			parentParent->_left = subR;
			subR->_parent = parentParent;
		}
		else
		{
			// parent原来在右子树，就和右子树链接
			parentParent->_right = subR;
			subR->_parent = parentParent;
		}

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

	...

private:
	Node* _root = nullptr;
	size_t _size = 0;
};

2. 新节点插入较高左子树的左侧—左左：右单旋

这里不带着大家一步一步分析了，直接上抽象图：
- a，b，c 均为高度为h的AVL平衡树；
- 只需要将subLR给parent的左，再将parent给subL的右即可；
- 随后更新平衡因子，subL和parent的_bf都更新为0。

在这里插入图片描述

类比左单旋，直接上代码：

template<class K, class V>
class AVLTree
{
	typedef AVLTreeNode<K, V> Node;
public:
	// 右单旋
	void RotateR(Node* parent)
	{
		Node* subL = parent->_left;
		Node* subLR = subL->_right;

		// 更新左右节点
		subL->_right = parent;
		parent->_left = subLR;

		Node* parentParent = parent->_parent;

		// 更新_parent
		parent->_parent = subL;
		if (subLR)
		{
			subLR->_parent = parent;
		}

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

	...

private:
	Node* _root = nullptr;
	size_t _size = 0;
};

3. 新节点插入较高左子树的右侧—左右：先左单旋再右单旋（左右双旋）

注意：该抽象图只是左右双旋中的一种情况，为在60的左子树新增。还有两种情况没有画出来，分别是（1）60作为新增节点的情况；（2）在60的右子树新增的情况。不同的情况，旋转后得到的平衡因子有差别。
h = 0 的情况：60就是新插入节点。此时b，c子树不存在，注意是不存在，连空都不是。旋转后的parent，subL，subLR的平衡因子均为0。
h = 1的情况（该情况又分两种）：
- 在60的左子树新增：注意此时旋转后，subL和subLR的平衡因子均为0，只有parent的平衡因子为1，和h = 0的情况不一样。
- 在60的右子树新增：这种情况最后的到的子树，和上图只有一处区别，就是b变成了NULL，c变成了50，故此时旋转后，subL的平衡因子为-1，parent，subLR的平衡因子均为0。和在60左子树新增的情况，平衡因子又不一样。
代码实现：
- 我们可以根据新节点插入后，subLR的平衡因子来确定到底是上述哪种情况。（1）subLR->_bf == 0，说明subLR就是新增节点；（2）subLR->_bf == -1，说明是在subLR的左子树新增；（3）subLR->_bf == 1，说明是在subLR的右子树新增。

template<class K, class V>
class AVLTree
{
	typedef AVLTreeNode<K, V> Node;
public:
	// 左右双旋
	void RotateLR(Node* parent)
	{
		Node* subL = parent->_left;
		Node* subLR = subL->_right;

		int bf = subLR->_bf;	// 提前记录subLR的平衡因子，避免单旋操作后，值丢失

		// 先左旋再右旋
		RotateL(parent->_left);
		RotateR(parent);

		// 更新平衡因子

		if (bf == 0)
		{
			// subLR自己就是新增节点
			subL->_bf = subLR->_bf = parent->_bf = 0;
		}
		else if (bf == -1)
		{
			// subLR的左子树新增
			parent->_bf = 1;
			subL->_bf = subLR->_bf = 0;
		}
		else if (bf == 1)
		{
			// subLR的右子树新增
			parent->_bf = subLR->_bf = 0;
			subL->_bf = -1;
		}
		else
		{
			assert(false);	// 检查点
		}
	}

	...

private:
	Node* _root = nullptr;
	size_t _size = 0;
};

4. 新节点插入较高右子树的左侧—右左：先右单旋再左单旋（右左双旋）

注意：该抽象图只是右左双旋中的一种情况，为在60的右子树新增。还有两种情况没有表示出来，分别是（1）60就是新增节点；（2）在60的左子树新增。
类比左右双旋，上代码：
- 还是要注意，可以通过subRL的平衡因子区分上述三种情况。（1）subRL->_bf == 0，说明subRL就是新增节点；（2） subRL->_bf == 1，说明是在subRL的右子树新增，parent->_bf == -1；（3）subRL->_bf == -1，说明是在subRL的左子树新增，subR->_bf == 1。

template<class K, class V>
class AVLTree
{
	typedef AVLTreeNode<K, V> Node;
public:
	// 右左双旋
	void RotateRL(Node* parent)
	{
		Node* subR = parent->_right;
		Node* subRL = subR->_left;

		int bf = subRL->_bf;	// 提前记录subRL的平衡因子，避免单旋操作后，值丢失

		// 先右旋再左旋
		RotateR(parent->_right);
		RotateL(parent);

		// 更新平衡因子
		
		if (bf == 0)
		{
			// subRL自己就是新增节点
			parent->_bf = subR->_bf = subRL->_bf = 0;
		}
		else if (bf == -1)
		{
			// subRL的左子树新增
			parent->_bf = 0;
			subR->_bf = 1;
			subRL->_bf = 0;
		}
		else if(bf == 1)
		{
			// subRL的右子树新增
			parent->_bf = -1;
			subR->_bf = 0;
			subRL->_bf = 0;
		}
		else
		{
			assert(false);	// 检查点
		}
	}

	...

private:
	Node* _root = nullptr;
	size_t _size = 0;
};

5. 完善插入：

旋转完成后是不需要继续向上更新平衡因子的，因为（1）旋转让这棵树平衡了；（2）旋转降低了这棵子树的高度，恢复到更插入前一样的高度，所以对上一层没有影响，不用更新。

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);
			_size++;
			return true;
		}

		Node* parent = nullptr;
		Node* cur = _root;

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

		cur = new Node(kv);
		if (kv.first > parent->_kv.first)
		{
			parent->_right = cur;
			cur->_parent = parent;
		}
		else
		{
			parent->_left = cur;
			cur->_parent = parent;
		}

		_size++;
		
		// 调整，AVL树的核心部分

		while (parent)
		{
			// 平衡因子的更新
			if (cur == parent->_left)
			{
				// 插入在左节点，_bf--
				parent->_bf--;
			}
			else
			{
				// 插入在右节点，_bf++
				parent->_bf++;
			}
			
			// 判断是否要继续向上更新，和是否旋转调整
			if (parent->_bf == 0)
			{
				// 更新后 _bf == 0，说明子树高度不变，不需要往上更新
				break;
			}
			else if (parent->_bf == 1 || parent->_bf == -1)
			{
				// 更新后子树高度改变，需要往上更新
				cur = parent;
				parent = parent->_parent;
			}
			else if (parent->_bf == 2 || parent->_bf == -2)
			{
				// 平衡因子绝对值等于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);
				}
				else
				{
					assert(false);
				}

				// 完成旋转后，不需要再往上更新平衡因子了，直接break
				//	1、旋转让这棵树平衡了
				//	2、旋转降低了这棵子树的高度，恢复到更插入前一样的高度，所以对上一层没有影响，不用更新
				break;
			}
			else
			{
				// 平衡因子绝对值大于2，直接报错
				assert(false);
			}
		}

		return true;
	}

	...

private:
	Node* _root = nullptr;
	size_t _size = 0;
};

5. AVL树的验证

1. 验证其为二叉搜索树：

如果中序遍历可得到一个有序的序列，就说明为二叉搜索树。

2. 验证其为平衡树：

每个节点子树高度差的绝对值不超过1；
节点的平衡因子是否计算正确。

3. 相关函数实现：

template<class K, class V>
class AVLTree
{
	typedef AVLTreeNode<K, V> Node;
public:
	void _InOrder(Node* root)
	{
		if (root == nullptr)
			return;

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

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

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

		int leftHeight = _Height(root->_left);
		int rightHeight = _Height(root->_right);
		return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
	}

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

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

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

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

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

		return abs(rightHeight - leftHeight) < 2
			&& _IsBalance(root->_left)
			&& _IsBalance(root->_right);
	}
	
	size_t Size() const 
	{
		return _size;
	}
	
	...

private:
	Node* _root = nullptr;
	size_t _size = 0;
};

4. 测试代码：

void Test()
{
	const int N = 100;
	srand(time(0));
	vector<int> v;

	for (int i = 0; i < N; i++)
	{
		v.push_back(rand());
	}

	AVLTree<int, int> tree;
	for (auto e : v)
	{
		tree.Insert(make_pair(e, e));
	}
	tree.InOrder();		// 检查是否有序
	cout << tree.IsBalance() << endl;	// 检查是否平衡
	cout << tree.Height() << endl;	// 看看高度
	cout << tree.Size() << endl;	// 看看数据量
}

6. AVL树的删除（了解）

1. 思路：

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

2. 例：

在这里插入图片描述

假如我们要删除根节点，可以先在右子树找到替换节点6，进行替换删除，然后更新平衡因子，得到的树如下图所示：

在这里插入图片描述

更新7这个节点的平衡因子，更新为2，不用继续向上更新了，对7节点进行左单旋调整即可。

删除的代码不再写了，面试时也几乎不会考察，最多考察思路。

7. AVL树实现完整代码

#pragma once

#include<iostream>
#include<assert.h>

using namespace std;

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)
	{}
};

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);
			_size++;
			return true;
		}

		Node* parent = nullptr;
		Node* cur = _root;

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

		cur = new Node(kv);
		if (kv.first > parent->_kv.first)
		{
			parent->_right = cur;
			cur->_parent = parent;
		}
		else
		{
			parent->_left = cur;
			cur->_parent = parent;
		}

		_size++;
		
		// 调整，AVL树的核心部分

		while (parent)
		{
			// 平衡因子的更新
			if (cur == parent->_left)
			{
				// 插入在左节点，_bf--
				parent->_bf--;
			}
			else
			{
				// 插入在右节点，_bf++
				parent->_bf++;
			}
			
			// 判断是否要继续向上更新，和是否旋转调整
			if (parent->_bf == 0)
			{
				// 更新后 _bf == 0，说明子树高度不变，不需要往上更新
				break;
			}
			else if (parent->_bf == 1 || parent->_bf == -1)
			{
				// 更新后子树高度改变，需要往上更新
				cur = parent;
				parent = parent->_parent;
			}
			else if (parent->_bf == 2 || parent->_bf == -2)
			{
				// 平衡因子绝对值等于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);
				}
				else
				{
					assert(false);
				}

				// 完成旋转后，不需要再往上更新平衡因子了，直接break
				//	1、旋转让这棵树平衡了
				//	2、旋转降低了这棵子树的高度，恢复到更插入前一样的高度，所以对上一层没有影响，不用更新
				break;
			}
			else
			{
				// 平衡因子绝对值大于2，直接报错
				assert(false);
			}
		}

		return true;
	}

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

		// 更新左右节点
		parent->_right = subRL;
		subR->_left = parent;

		// 提前记录parent的parent
		Node* parentParent = parent->_parent;

		// 更新_parent
		parent->_parent = subR;
		if (subRL)	// 判断为不为空，subRL是唯一一个可能为空的节点
		{
			subRL->_parent = parent;
		}

		// 处理根
		if (_root == parent)
		{
			_root = subR;
			subR->_parent = nullptr;
		}
		else if (parentParent->_left == parent)
		{
			parentParent->_left = subR;
			subR->_parent = parentParent;
		}
		else
		{
			parentParent->_right = subR;
			subR->_parent = parentParent;
		}

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

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

		// 更新左右节点
		subL->_right = parent;
		parent->_left = subLR;

		Node* parentParent = parent->_parent;

		// 更新_parent
		parent->_parent = subL;
		if (subLR)
		{
			subLR->_parent = parent;
		}

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

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

		int bf = subRL->_bf;	// 提前记录subRL的平衡因子，避免单旋操作后，值丢失

		// 先右旋再左旋
		RotateR(parent->_right);
		RotateL(parent);

		// 更新平衡因子
		
		if (bf == 0)
		{
			// subRL自己就是新增节点
			parent->_bf = subR->_bf = subRL->_bf = 0;
		}
		else if (bf == -1)
		{
			// subRL的左子树新增
			parent->_bf = 0;
			subR->_bf = 1;
			subRL->_bf = 0;
		}
		else if(bf == 1)
		{
			// subRL的右子树新增
			parent->_bf = -1;
			subR->_bf = 0;
			subRL->_bf = 0;
		}
		else
		{
			assert(false);	// 检查点
		}
	}

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

		int bf = subLR->_bf;	// 提前记录subLR的平衡因子，避免单旋操作后，值丢失

		// 先左旋再右旋
		RotateL(parent->_left);
		RotateR(parent);

		// 更新平衡因子

		if (bf == 0)
		{
			// subLR自己就是新增节点
			subL->_bf = subLR->_bf = parent->_bf = 0;
		}
		else if (bf == -1)
		{
			// subLR的左子树新增
			parent->_bf = 1;
			subL->_bf = subLR->_bf = 0;
		}
		else if (bf == 1)
		{
			// subLR的右子树新增
			parent->_bf = subLR->_bf = 0;
			subL->_bf = -1;
		}
		else
		{
			assert(false);	// 检查点
		}
	}

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

		return nullptr;
	}

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

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

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

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

		int leftHeight = _Height(root->_left);
		int rightHeight = _Height(root->_right);
		return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
	}

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

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

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

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

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

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

	size_t Size() const 
	{
		return _size;
	}

private:
	Node* _root = nullptr;
	size_t _size = 0;
};

8. AVL树的性能

AVL树是一棵绝对平衡的二叉搜索树，其要求每个节点的左右子树高度差的绝对值都不超过1，这样可以保证查询时高效的时间复杂度，即 $log_2 (N)$ 。但是如果要对AVL树做一些结构修改的操作，性能非常低下，比如：

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

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

9. AVL的封装，终极版本

记得是大二的时候，本人曾经用AVL树做过一个课题。当时需要一颗功能完善的AVL树，需要能够遍历和删除节点。为了实现这两个功能，本人曾经手撕了AVL树。时隔多年，无意间翻到当初的代码，竟然忘了自己曾经实现过迭代器部分和删除部分，这部分代码还差点被删除。为了让自己努力成果保存下来，现在将这棵终极AVL树放在博客里，实现赛博永生！！！

1. 树的源码：

#pragma once

#include<iostream>
#include<assert.h>

using namespace std;

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)
	{}
};

template<class K, class V>
struct __TreeIterator
{
	typedef AVLTreeNode<K, V> Node;
	typedef __TreeIterator<K, V> Self;
	Node* _node;//迭代器存的是二叉树的节点

	__TreeIterator(Node* node)
		:_node(node)
	{}

	pair<K, V>& operator*()
	{
		return _node->_kv;
	}

	pair<K, V>* operator->()
	{
		return &_node->_kv;
	}

	//这就是平衡二叉树迭代器的运行核心 一定要理解这部分逻辑才能理解好这个迭代器
	Self& operator++()
	{
		if (_node->_right)
		{
			// 下一个就是右子树的最左节点
			Node* cur = _node->_right;
			while (cur->_left)
			{
				cur = cur->_left;
			}

			_node = cur;
		}
		else
		{
			// 左子树 根 右子树
			// 右为空，找孩子是父亲左的那个祖先
			Node* cur = _node;
			Node* parent = cur->_parent;
			while (parent && cur == parent->_right)
			{
				cur = parent;
				parent = parent->_parent;
			}

			_node = parent;
		}

		return *this;
	}

	//给外界判断提供的
	bool operator!=(const Self& s)
	{
		return _node != s._node;
	}

	bool operator==(const Self& s)
	{
		return _node == s._node;
	}
};


template<class K, class V>
class AVLTree
{
	typedef AVLTreeNode<K, V> Node;
	typedef struct __TreeIterator<K, V> iterator;
public:
	iterator begin()
	{
		Node* cur = _root;
		if (cur == nullptr)
			return cur;

		while (cur->_left)
		{
			cur = cur->_left;
		}
		return cur;
	}

	iterator end()
	{
		return nullptr;
	}

	bool Insert(const pair<K, V>& kv)
	{
		// 插入，类比搜索二叉树插入
		if (_root == nullptr)
		{
			_root = new Node(kv);
			_size++;
			return true;
		}

		Node* parent = nullptr;
		Node* cur = _root;

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

		cur = new Node(kv);
		if (kv.first > parent->_kv.first)
		{
			parent->_right = cur;
			cur->_parent = parent;
		}
		else
		{
			parent->_left = cur;
			cur->_parent = parent;
		}

		_size++;
		
		// 调整，AVL树的核心部分

		while (parent)
		{
			// 平衡因子的更新
			if (cur == parent->_left)
			{
				// 插入在左节点，_bf--
				parent->_bf--;
			}
			else
			{
				// 插入在右节点，_bf++
				parent->_bf++;
			}
			
			// 判断是否要继续向上更新，和是否旋转调整
			if (parent->_bf == 0)
			{
				// 更新后 _bf == 0，说明子树高度不变，不需要往上更新
				break;
			}
			else if (parent->_bf == 1 || parent->_bf == -1)
			{
				// 更新后子树高度改变，需要往上更新
				cur = parent;
				parent = parent->_parent;
			}
			else if (parent->_bf == 2 || parent->_bf == -2)
			{
				// 平衡因子绝对值等于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);
				}
				else
				{
					assert(false);
				}

				// 完成旋转后，不需要再往上更新平衡因子了，直接break
				//	1、旋转让这棵树平衡了
				//	2、旋转降低了这棵子树的高度，恢复到更插入前一样的高度，所以对上一层没有影响，不用更新
				break;
			}
			else
			{
				// 平衡因子绝对值大于2，直接报错
				assert(false);
			}
		}

		return true;
	}

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

		// 更新左右节点
		parent->_right = subRL;
		subR->_left = parent;

		// 提前记录parent的parent
		Node* parentParent = parent->_parent;

		// 更新_parent
		parent->_parent = subR;
		if (subRL)	// 判断为不为空，subRL是唯一一个可能为空的节点
		{
			subRL->_parent = parent;
		}

		// 处理根
		if (_root == parent)
		{
			_root = subR;
			subR->_parent = nullptr;
		}
		else if (parentParent->_left == parent)
		{
			parentParent->_left = subR;
			subR->_parent = parentParent;
		}
		else
		{
			parentParent->_right = subR;
			subR->_parent = parentParent;
		}

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

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

		// 更新左右节点
		subL->_right = parent;
		parent->_left = subLR;

		Node* parentParent = parent->_parent;

		// 更新_parent
		parent->_parent = subL;
		if (subLR)
		{
			subLR->_parent = parent;
		}

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

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

		int bf = subRL->_bf;	// 提前记录subRL的平衡因子，避免单旋操作后，值丢失

		// 先右旋再左旋
		RotateR(parent->_right);
		RotateL(parent);

		// 更新平衡因子
		
		if (bf == 0)
		{
			// subRL自己就是新增节点
			parent->_bf = subR->_bf = subRL->_bf = 0;
		}
		else if (bf == -1)
		{
			// subRL的左子树新增
			parent->_bf = 0;
			subR->_bf = 1;
			subRL->_bf = 0;
		}
		else if(bf == 1)
		{
			// subRL的右子树新增
			parent->_bf = -1;
			subR->_bf = 0;
			subRL->_bf = 0;
		}
		else
		{
			assert(false);	// 检查点
		}
	}

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

		int bf = subLR->_bf;	// 提前记录subLR的平衡因子，避免单旋操作后，值丢失

		// 先左旋再右旋
		RotateL(parent->_left);
		RotateR(parent);

		// 更新平衡因子

		if (bf == 0)
		{
			// subLR自己就是新增节点
			subL->_bf = subLR->_bf = parent->_bf = 0;
		}
		else if (bf == -1)
		{
			// subLR的左子树新增
			parent->_bf = 1;
			subL->_bf = subLR->_bf = 0;
		}
		else if (bf == 1)
		{
			// subLR的右子树新增
			parent->_bf = subLR->_bf = 0;
			subL->_bf = -1;
		}
		else
		{
			assert(false);	// 检查点
		}
	}

	void Erase_rotate(Node* cur)  //删除节点的操作函数 传入的是已经修改过bf的删除节点的父节点
	{
		Node* prev = nullptr;
		while (cur)
		{

			if (cur->_bf == 1 || cur->_bf == -1)
				break;
			else if (cur->_bf == 0)
			{
				prev = cur;
				cur = cur->_parent;
			}
			else if (cur->_bf == 2)
			{
				if (cur->_right->_bf == 1)  //左单旋
				{
					RotateL(cur);
					prev = cur->_parent;
					cur = prev->_parent;

					continue;
				}
				else if (cur->_right->_bf == -1)  //先来一个右单旋 再来一个左单旋
				{
					Node* subR = cur->_left;
					Node* subRL = subR->_left;
					int _bf = subRL->_bf;
					RotateR(cur->_right);
					RotateL(cur);

					if (_bf == 1)
					{
						cur->_bf = -1;
						subR->_bf = 0;
					}
					else if (_bf == -1)
					{
						cur->_bf = 0;
						subR->_bf = 1;
					}
					else if (_bf == 0)
					{
						cur->_bf = 0;
						subR->_bf = 0;
					}

					cur = subRL->_parent;
					prev = subRL;
					continue;
				}
				else if (cur->_right->_bf == 0)
				{
					RotateL(cur);
					cur->_parent->_bf = -1;
					cur->_bf = 1;
					break;     //由于旋转完的树的bf的值为-1，所以不用继续循环
				}

			}
			else if (cur->_bf == -2)
			{
				if (cur->_left->_bf == 1)  // 先来一个左单旋 再来一个右单旋
				{
					Node* subL = cur->_left;
					Node* subLR = subL->_right;
					int _bf = subLR->_bf;
					RotateL(cur->_left);
					RotateR(cur);

					if (_bf == 1)
					{
						cur->_bf = 0;
						subL->_bf = -1;
					}
					else if (_bf == -1)
					{
						cur->_bf = 1;
						subL->_bf = 0;
					}
					else if (_bf == 0)
					{
						cur->_bf = 0;
						subL->_bf = 0;
					}

					cur = subLR->_parent;
					prev = subLR;

					continue;
				}
				else if (cur->_left->_bf == -1)  //右单旋
				{
					RotateR(cur);
					prev = cur->_parent;
					cur = prev->_parent;
					continue;
				}
				else if (cur->_left->_bf == 0)
				{
					RotateR(cur);
					cur->_bf = -1;
					cur->_parent->_bf = 1;
					break;
				}

			}
			if (cur && prev == cur->_left)
			{
				(cur->_bf)++;
			}
			else if (cur && prev == cur->_right)
			{
				(cur->_bf)--;
			}
		}
	}

	bool Erase(const pair<K, V>& x)
	{
		if (_root == nullptr)   //开头检查一下是否是空树
			assert(_root == nullptr);
		Node* cur = _root;
		Node* father = _root;

		while (cur)
		{
			if (cur->_kv.first < x.first)
			{
				father = cur;
				cur = cur->_right;
			}
			else if (cur->_kv.first > x.first)
			{
				father = cur;
				cur = cur->_left;
			}
			else
			{
				//删除操作
				if (cur->_left == nullptr || cur->_right == nullptr) //左右子树至少一个为空
				{
					if (cur == _root)   //cur是根结点的情况要考虑一下！
					{
						_root = (cur->_left == nullptr) ? cur->_right : cur->_left;  //不可能出现旋转的情况
					}
					else if (cur->_left == nullptr && cur->_right == nullptr)  //左右子树均为空
					{
						if (father->_left == cur)
						{
							father->_left = nullptr;
							delete cur;
							father->_bf++;
						}
						else
						{
							father->_right = nullptr;
							delete cur;
							father->_bf--;
						}

						Erase_rotate(father);
					}
					else  if (cur->_left == nullptr && cur->_right != nullptr)  //左空右不空
					{
						cur->_kv = cur->_right->_kv;
						Node* temp = cur->_right;
						cur->_right = nullptr;
						delete temp;

						cur->_bf--;
						Erase_rotate(cur);
					}
					else if (cur->_right == nullptr && cur->_left == nullptr)  //右空左不空
					{
						cur->_kv = cur->_left->_kv;
						Node* temp = cur->_left;
						cur->_left = nullptr;
						delete temp;

						cur->_bf++;
						Erase_rotate(cur);
					}

				}
				else  //左右子树都不为空 
				{
					//找到右子树中的最小值与cur节点的值进行替换

					//找右子树最小节点,也就是右子树的最左边的节点，这个节点：左子树一定为null，右子树未知
					Node* Newcur = cur->_left;
					Node* Newcur_father = cur;
					while (Newcur->_right)
					{
						Newcur_father = Newcur;
						Newcur = Newcur->_right;
					}

					cur->_kv = Newcur->_kv;

					//现在要搞清楚等效删除的是哪个节点，以及从哪个节点开始向上检查！
					if (Newcur_father == cur)
					{
						if (Newcur->_left) //相当于删除的是Newcur的右节点，改变Newcur的bf，并从Newcur节点向上检查
						{
							Newcur->_kv = Newcur->_left->_kv;

							Node* temp = Newcur->_left;
							Newcur->_left = nullptr;
							delete temp;

							Newcur->_bf++;
							Erase_rotate(Newcur);
						}
						else         //相当于删除的是Newcur节点，改变Newcur_father的bf，并从Newcur_father向上检查
						{
							Newcur_father->_left = nullptr;
							delete Newcur;

							Newcur_father->_bf++;  //这是if (Newcur_father == cur)两种情况的本质区别
							Erase_rotate(Newcur_father);
						}
					}
					else
					{
						if (Newcur->_left) //相当于删除的是Newcur的右节点，改变Newcur的bf，并从Newcur节点向上检查
						{
							//这种情况就是上面  左子树为空右子树不为空

							Newcur->_kv = Newcur->_left->_kv;

							Node* temp = Newcur->_left;
							Newcur->_left = nullptr;
							delete temp;

							Newcur->_bf++;
							Erase_rotate(Newcur);
						}
						else         //相当于删除的是Newcur节点，改变Newcur_father的bf，并从Newcur_father向上检查
						{
							//这种情况就是上面  左右子树 均为空的删除情况

							Newcur_father->_right = nullptr;
							delete Newcur;

							Newcur_father->_bf--;
							Erase_rotate(Newcur_father);
						}
					}
				}
				return true;
			}
		}

		return false;
	}

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

		return nullptr;
	}

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

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

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

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

		int leftHeight = _Height(root->_left);
		int rightHeight = _Height(root->_right);
		return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
	}

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

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

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

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

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

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

	size_t Size() const 
	{
		return _size;
	}

private:
	Node* _root = nullptr;
	size_t _size = 0;
};

2. 测试样例：

#include<iostream>
#include"AVLTree.h"
#include<vector>

// 测试insert
void Test()
{
	const int N = 100;
	srand(time(0));
	vector<int> v;

	for (int i = 0; i < N; i++)
	{
		v.push_back(rand());
	}

	AVLTree<int, int> tree;
	for (auto e : v)
	{
		tree.Insert(make_pair(e, e));
	}
	tree.InOrder();
	cout << tree.IsBalance() << endl;
	cout << tree.Height() << endl;
	cout << tree.Size() << endl;
}

// 测试find，并记录时间
void Test2()
{
	const int N = 100000;
	srand(time(0));
	vector<int> v;

	for (int i = 0; i < N; i++)
	{
		v.push_back(rand());
	}

	AVLTree<int, int> tree;
	for (auto e : v)
	{
		tree.Insert(make_pair(e, e));
	}

	size_t begin = clock();
	for (size_t i = 0; i < N; i++)
	{
		tree.Find((rand() + i));
	}

	size_t end = clock();
	cout << "Find time:" << end - begin << endl;
}

// 测试迭代器功能
void Test3()
{
	const int N = 100;
	srand(time(0));
	vector<int> v;

	for (int i = 0; i < N; i++)
	{
		v.push_back(rand());
	}

	AVLTree<int, int> tree;
	for (auto e : v)
	{
		tree.Insert(make_pair(e, e));
	}
	tree.InOrder();

	cout << "=======================" << endl;
	for (auto e : tree)
	{
		cout << e.second << " ";
	}
	cout << endl;
}

// 测试删除功能
void Test4()
{
	const int N = 100;
	
	vector<int> v;

	for (int i = 0; i < N; i++)
	{
		v.push_back(i);
	}

	AVLTree<int, int> tree;
	for (auto e : v)
	{
		tree.Insert(make_pair(e, e));
	}
	tree.InOrder();

	cout << "=======================" << endl;
	for (auto e : tree)
	{
		cout << e.second << " ";
	}
	cout << endl;
	cout << "=======================" << endl;
	tree.Erase(make_pair(99, 99));
	tree.InOrder();

	cout << tree.IsBalance() << endl;

	tree.Erase(make_pair(90, 90));
	tree.Erase(make_pair(66, 66));
	tree.Erase(make_pair(35, 35));
	cout << "=======================" << endl;
	tree.InOrder();
	cout << tree.IsBalance() << endl;
}

int main()
{
	// Test1();
	// Test2();
	// Test3();
	Test4();
	return 0;
}

2048 AI社区

有“AI”的1024 = 2048，欢迎大家加入2048 AI社区

更多推荐

SEO老手都在焦虑的事：流量没掉，但用户不搜了

本文探讨了生成式引擎优化(GEO)这一新兴概念，指出随着AI搜索的普及，传统SEO策略已显不足。数据显示AI搜索流量价值更高且增长迅速，其引用逻辑与传统搜索完全不同，更倾向于问答社区和权威内容。文章介绍了GEO与SEO的区别：GEO关注AI如何引用内容而非关键词排名，并提出了六步闭环方法论，包括市场竞争分析、技术优化、提示词调研等。书中案例显示，三星、Hertz等企业已通过GEO获得竞争优势。作者

2048 AI社区

无处不AI！超图以空间智能体重构GIS产业新格局

2048 AI社区

智能火灾报警系统的设计(设计源文件+万字报告+讲解)（支持资料、图片参考_降重降ai）

STC89C51属于CMOS8位微控制器的范畴，由STC公司研发并生产而来，它的功耗非常低，具有较高的使用性能，标准功能如下所示：Flash的字节是8k，RAM的字节是512， I/O口线的类型是32位的，使用的计时器是一种看门狗计时器，内置4KB EEPROM，MAX810复位电路，使用的是全双工串行口，7向量4级中断结构有1个，外部中断与16位定时器/计数器的数量分别是4个与3个。因为它具有