AVL树详解

前言

AVL树是二叉搜索树的改进版本，思考一下，二叉搜索树有什么问题？
当我们向二叉搜索树里插入有序序列时，那么二叉搜索树就会退化成线性的，查找效率会变成O(n)

比如我们依次插入1，2，3，4，5，6，7
得到：

这是最坏情况，当然，只要插入数据时稍微有序，也会增加二叉搜索树的高度，所以我们需要寻找一个方法去解决这个问题!
这时就引入了AVL树~

1.AVL树的概念

两位俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis在1962年发明了一种解决上述问题的方法：当向二叉搜索树中插入新结点后，如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整)，即可降低树的高度，从而减少平均搜索长度

一棵AVL树或者是空树，或者是具有以下性质的二叉搜索树：

• 它的左右子树都是AVL树
• 左右子树高度之差(简称平衡因子)的绝对值不超过1(-1/0/1)

2.AVL树的节点

AVL树节点的定义：

template<class T>
struct AVLTreeNode
{
AVLTreeNode(const T& data)
: _pLeft(nullptr), _pRight(nullptr), _pParent(nullptr)
, _data(data), _bf(0)
{}
AVLTreeNode<T>* _pLeft; // 该节点的左孩子
AVLTreeNode<T>* _pRight; // 该节点的右孩子
AVLTreeNode<T>* _pParent; // 该节点的双亲
T _data;
int _bf; // 该节点的平衡因子
};

3.AVL树的插入

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

新节点插入后，其父节点的平衡因子一定需要调整，在插入之前，父节点的平衡因子分为三种情况：-1，0, 1, 分以下两种情况：

1. 如果新节点插入到父节点的左侧，只需给父节点的平衡因子-1即可
2. 如果新节点插入到父节点的右侧，只需给父节点的平衡因子+1即可

此时：父节点的平衡因子可能有三种情况：0，正负1， 正负2

1. 如果父节点的平衡因子为0，说明插入之前父节点的平衡因子为正负1，插入后被调整成0，此时满足AVL树的性质，插入成功
2. 如果父节点的平衡因子为正负1，说明插入前父节点的平衡因子一定为0，插入后被更新成正负1，此时以父节点为根的树的高度增加，需要继续向上更新
3. 如果父节点的平衡因子为正负2，则父节点的平衡因子违反平衡树的性质，需要对其进行旋转处理

此时主要问题在于调整平衡因子， AVL树引入旋转操作来降低树的平衡因子

在了解旋转操作之前，请读者复习一下

4.AVL树的旋转

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

4.1 左单旋

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

void _RotateL(Node* parent) //传入平衡因子为2的节点指针
{
	Node* subR = parent->_right;
	Node* subRL = subR->_left; //这个节点是不一定存在的
	Node* pparent = parent->_parent; 
	//有可能parent就是根节点，此时pparent节点也不存在
	if (pparent)
	{
		if (pparent->_left == parent)
			pparent->_left = subR;
		else
			pparent->_right = subR;
	}
	else
	{
		_root = subR;
	}
	subR->_parent = parent->_parent;
	subR->_left = parent;

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

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

$$h\in [0,+\infty )$$
在旋转时要注意：

1. parent有可能为根节点，需要特判一些问题
2. 新插入的节点不一定直接与subR相连，有可能是下面不断调整平衡因子，最终影响到上面的
3. 如果插入的节点与subR直接相连，则subRL为空，也需要特判一下

4.2 右单旋

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

void _RotateR(Node* parent)
{
	Node* subL = parent->_left;
	Node* subLR = subL->_right;
	Node* pparent = parent->_parent;
	if (pparent)
	{
		if (pparent->_left == parent)
			pparent->_left = subL;
		else
			pparent->_right = subL;
	}
	else
	{
		_root = subL;
	}
	subL->_parent = parent->_parent;
	subL->_right = parent;

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

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

4.3 左右双旋

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

void _RotateLR(Node* parent)
{
	Node* subL = parent->_left;
	Node* subLR = subL->_right;
	int bf = subLR->_bf;
	_RotateL(subL);
	_RotateR(parent);
	subLR->_bf = 0;
	if (bf == 1)
	{
		parent->_bf = 0;
		subL->_bf = -1;
	}
	else if (bf == -1)
	{
		parent->_bf = 1;
		subL->_bf = 0;
	}
	else if (bf == 0) //即subLR子树中只有一个节点
	{
		parent->_bf = subL->_bf = 0;
	}
	else
	{
		assert(false);
	}
}

4.4 右左双旋

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

void _RotateRL(Node* parent)
{
	Node* subR = parent->_right;
	Node* subRL = subR->_left;
	int bf = subRL->_bf;
	_RotateR(subR);
	_RotateL(parent);
	subRL->_bf = 0;
	if (bf == 1)
	{
		subR->_bf = 0;
		parent->_bf = -1;
	}
	else if (bf == -1)
	{
		subR->_bf = 1;
		parent->_bf = 0;
	}
	else if (bf == 0)
	{
		subR->_bf = parent->_bf = 0;
	}
	else
		assert(false);
}

5.AVL树的验证

验证可以分为两步：

1. 验证其为二叉搜索树
2. 验证其为平衡树
   • 每个节点子树高度差不超过1
   • 节点的平衡因子计算正确

bool IsLegal()
{
	return _IsLegal(_root);
}
//判断是否合法
bool _IsLegal(Node* root)
{
	if (root == nullptr) return true;
	//平衡因子超过正负1非法
	if (root->_bf >= 2 || root->_bf <= -2) return false; 
	if (!_IsLegal(root->_left) || !_IsLegal(root->_right)) return false;
	return root->_bf == (Height(root->_right) - Height(root->_left));
}
//求子树高度
int Height(Node* root)
{
	if (root == nullptr) return 0;
	return std::max(Height(root->_left), Height(root->_right)) + 1;
}

测试用例：
常规场景1
{16, 3, 7, 11, 9, 26, 18, 14, 15}
特殊场景2
{4, 2, 6, 1, 3, 5, 15, 7, 16, 14}

6.总体实现

#pragma once

#include <cassert>
#include <algorithm>

namespace moran {
	template<class K,class V>
	struct AVLTreeNode {
		AVLTreeNode<K, V>* _left;
		AVLTreeNode<K, V>* _right;
		AVLTreeNode<K, V>* _parent;
		std::pair<K, V> _kv;
		int _bf;
		AVLTreeNode(const std::pair<K,V>& kv,int bf = 0, AVLTreeNode<K, V>* left = nullptr, 
			AVLTreeNode<K, V>* right = nullptr, AVLTreeNode<K, V>* parent = nullptr)
			:_kv(kv),
			_bf(bf),
			_left(left),
			_right(right),
			_parent(parent)
		{}
	};

	template <class K,class V>
	class AVLTree {
		typedef AVLTreeNode<K, V> Node;
	public:
		AVLTree() = default;
		//迭代器区间构造
		template<class InputIterator>
		AVLTree(InputIterator first, InputIterator last)
		{
			while (first != last)
			{
				insert(*first);
			}
		}
		bool Insert(const std::pair<K,V>& kv)
		{
			//根是否为空
			if (_root == nullptr)
			{
				_root = new Node(kv);
				return true;
			}
			Node* cur = _root;
			while (cur)
			{
				if (cur->_kv.first > kv.first)
				{
					if (cur->_left == nullptr)
					{
						Node* new_node = new Node(kv);
						cur->_left = new_node;
						new_node->_parent = cur;
						//更新cur平衡因子
						cur->_bf--;
						break;
					}
					else
					{
						cur = cur->_left;
					}
				}
				else if (cur->_kv.first < kv.first)
				{
					if (cur->_right == nullptr)
					{
						Node* new_node = new Node(kv);
						cur->_right = new_node;
						new_node->_parent = cur;
						//更新cur的平衡因子
						cur->_bf++;
						break;
					}
					else
					{
						cur = cur->_right;
					}
				}
				else
					return false;
			}
			Node* parent = cur->_parent;
			//如果cur平衡因子为0或者没有父节点，则无需继续更新
			while (cur->_bf && parent)
			{
				if (cur->_bf == 1 || cur->_bf == -1)
				{
					if (cur == parent->_left)
					{
						parent->_bf--;
						//需要调整
						if (parent->_bf == -2)
						{
							if (cur->_bf == 1)
							{
								_RotateLR(parent);//左右旋
							}
							else
							{
								_RotateR(parent);//右旋
							}
							break;
						}
					}
					else
					{
						parent->_bf++;
						//需要调整
						if (parent->_bf == 2)
						{
							if (cur->_bf == 1)
							{
								//左旋
								_RotateL(parent);
							}
							else
							{
								_RotateRL(parent);//右左旋
							}
							break;
						}
					}
				}
				else
				{
					assert(false);
				}
				cur = parent;
				parent = parent->_parent;
			}
			return true;
		}
		bool IsLegal()
		{
			return _IsLegal(_root);
		}
	private:
		bool _IsLegal(Node* root)
		{
			if (root == nullptr) return true;
			if (root->_bf >= 2 || root->_bf <= -2) return false;
			if (!_IsLegal(root->_left) || !_IsLegal(root->_right)) return false;
			return root->_bf == (Height(root->_right) - Height(root->_left));
		}
		int Height(Node* root)
		{
			if (root == nullptr) return 0;
			return std::max(Height(root->_left), Height(root->_right)) + 1;
		}
		void _RotateR(Node* parent)
		{
			Node* subL = parent->_left;
			Node* subLR = subL->_right;
			Node* pparent = parent->_parent;
			if (pparent)
			{
				if (pparent->_left == parent)
					pparent->_left = subL;
				else
					pparent->_right = subL;
			}
			else
			{
				_root = subL;
			}
			subL->_parent = parent->_parent;
			subL->_right = parent;

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

			parent->_bf = subL->_bf = 0;
		}
		void _RotateL(Node* parent)
		{
			Node* subR = parent->_right;
			Node* subRL = subR->_left;
			Node* pparent = parent->_parent;
			if (pparent)
			{
				if (pparent->_left == parent)
					pparent->_left = subR;
				else
					pparent->_right = subR;
			}
			else
			{
				_root = subR;
			}
			subR->_parent = parent->_parent;
			subR->_left = parent;

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

			parent->_bf = subR->_bf = 0;
		}
		void _RotateRL(Node* parent)
		{
			Node* subR = parent->_right;
			Node* subRL = subR->_left;
			int bf = subRL->_bf;
			_RotateR(subR);
			_RotateL(parent);
			subRL->_bf = 0;
			if (bf == 1)
			{
				subR->_bf = 0;
				parent->_bf = -1;
			}
			else if (bf == -1)
			{
				subR->_bf = 1;
				parent->_bf = 0;
			}
			else if (bf == 0)
			{
				subR->_bf = parent->_bf = 0;
			}
			else
				assert(false);
		}
		void _RotateLR(Node* parent)
		{
			Node* subL = parent->_left;
			Node* subLR = subL->_right;
			int bf = subLR->_bf;
			_RotateL(subL);
			_RotateR(parent);
			subLR->_bf = 0;
			if (bf == 1)
			{
				parent->_bf = 0;
				subL->_bf = -1;
			}
			else if (bf == -1)
			{
				parent->_bf = 1;
				subL->_bf = 0;
			}
			else if (bf == 0)
			{
				parent->_bf = subL->_bf = 0;
			}
			else
			{
				assert(false);
			}
		}
	private:
		Node* _root = nullptr;
	};
}

7.AVL树的性能

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

显然AVL树不适合作为STL的map、set底层数据结构，于是就有了对AVL树的改进：