C++：AVL树

目录

AVL树概念

AVL树的实现

AVL树的节点

AVL树的插入

AVL树的平衡调整

右单旋

左单旋

左右双旋

右左双旋

完整的插入函数

AVL树的查找

AVL树的验证

验证有序

验证平衡

完整代码

AVL树概念

AVL树是一种具有特殊性质的二叉搜索树，AVL树的左右子树也都是AVL树，且左右子树的高度差的绝对值不超过1，超过1就说明AVL树失衡，需要调整。AVl树是一颗高度平衡的二叉搜索树，通过高度控制高度差去控制平衡。

AVL树对比二叉搜索树多引入了一个平衡因子的概念，每个节点都有一个平衡因子，任何节点的平衡因子等于右子树的高度减去左子树的高度，所以说平衡因子的取值是0、1和-1。

AVL树整体节点和分布与完全二叉树类似，高度控制在logN范围内，那么增删查改的效率也可以控制在O(logN)，相比二叉搜索树有了本质提升。

以下这棵树就是AVL树。

AVL树的实现

AVL树的节点

由于在调整失衡的AVL树时，需要频繁访问父节点，所以我们在定义节点时也需要引入parent指针。

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;

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

AVL树的插入

向AVL树插入新节点的过程与二叉搜索树的插入类似，但有区别的是，插入新节点后需要更新平衡因子，然后根据平衡因子的情况判断AVL树是否失衡，失衡就对AVL树进行调整。

按照平衡因子的计算公式，如果新节点插入到了父亲节点的左边，那么父亲的平衡因子-1，反之，如果插入到右边，父亲的平衡因子+1。

更新后的平衡因子的情况，可以分为两种：1.平衡因子（从1/-1）变成0。 2.平衡因子（从0）变成1/-1。

情况1就说明已经完成平衡因子的更新了，情况2就还得继续更新，因为当父亲的平衡因子为1/-1时，说明以父亲为根节点的子树高度发生了变化，这样会影响父亲的父亲的平衡因子，所以需要继续往上更新平衡因子。

template<class K, class V>
class AVLTree
{
	typedef AVLTreeNode 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)
		{
			parent = cur;
			if (kv.first > cur->_kv.first)
				cur = cur->_right;
			else if (kv.first < cur->_kv.first)
				cur = cur->_left;
			else
				return false;
		}

		cur = new Node(kv);
		//将父节点与新节点链接
		//判断新节点插入到parent的左边还是右边
		if (kv.first > parent->_kv.first) //新节点插入到parent的右边
			parent->_right = cur;
		else
			parent->_left = cur;
		//更改新节点的父亲指针
		cur->_parent = parent;

		//更新平衡因子
		while (parent)
		{
			//插入节点后除了对父节点造成影响还可能对祖宗节点造成影响
			//随着循环进行，cur不一定为新节点
			//更新父节点的平衡因子
			if (cur == parent->_left)
				parent->_bf--;
			else
				parent->_bf++;

			//检查更新后父亲的平衡因子
			//_bf为0，说明树还是AVL树，退出循环
			if (parent->_bf == 0)
				break;
			//_bf == 1/-1,说明需要继续向上更新平衡因子
			else if (parent->_bf == 1 || parent->_bf == -1)
			{
				cur = parent;
				parent = parent->_parent;
			}
			//_bf == 2/-2，说明AVL树失衡，需要进行旋转操作
			else if (parent->_bf == 2 || parent->_bf == -2)
			{
				//插入后AVl树失衡，需要进行平衡调整
			}
		}

		return true;

	}

private:
	Node* _root = nullptr;;
};

AVL树的平衡调整

AVL树的调整其实就是对失衡的AVl树进行旋转操作，旋转操作必须保持搜索树的规则，让失衡的AVL树变平衡。

旋转操作可以分为4种：右单旋、左单旋、左右双旋和右左双旋。

右单旋

当parent->_bf == -2 && cur->_bf == -1时说明AVL树往左倾斜，需要进行右单旋操作。

右单旋其实就是从树的右边将树顺时针旋转。     

void RotataR(Node* parent)
{
	//subL为parent的左孩子节点
	Node* subL = parent->_left;
	//subLR为subL的右子节点
	Node* SubLR = subL->_right;

	// 将parent与subLR节点进行链接
	parent->_left = SubLR;
	//在SubLR的情况下更改，让其指向正确的父亲
	if (SubLR)
		SubLR->_parent = parent;

	//提前记录祖父节点
	Node* pParent = parent->_parent;

	//链接subL与parent
	subL->_right = parent;
	parent->_parent = subL;

	//根据parent是否是根节点进行不同处理
	if (parent == _root)
	{
		_root = subL;
		subL->_parent = nullptr;
	}
	else 
	{
		//将pParent和subL链接
		//但得先判断parent是pParent的左节点还是右节点
		if (pParent->_left == parent)
			pParent->_left = subL;
		else
			pParent->_right = subL;

		//修改subL的parent指针，让其指向正确的父亲
		subL->_parent = pParent;
	}

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

左单旋

当parent->_bf == 2 && cur->_bf == 1时说明AVL树往右倾斜，需要进行左单旋操作。

左单旋其实就是从树的左边将树逆时针旋转。

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

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

	Node* pParent = parent->_parent;

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

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

		subR->_parent = pParent;
	}

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

左右双旋

当parent->_bf == -2 && cur->_bf == 1时，即新节点插入到较高左子树的右侧：先左单旋然后再右单旋。

左右双旋情况比较复杂，如下图。

void RotateLR(Node* parent)
{
	Node* subL = parent->_left;
	Node* subLR = subL->_right;
	//记录subLR的bf，根据其取值更新左右双旋后各个节点的bf
	int bf = subLR->_bf;	

	RotateL(subL);
	RotateR(parent);

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

}

右左双旋

当parent->_bf == 2 && cur->_bf == -1时，即新节点插入到较高右子树的左侧：先右单旋然后再左单旋。

右左双旋其实就是左右双旋的另一种情况，我们直接上图解。

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

}

完整的插入函数

bool Insert(const pair<K, V>& kv)
{
	//空树的情况特殊处理
	if (_root == nullptr)
	{
		_root = new Node(kv);
		return true;
	}

	//不是空树的情况
	Node* parent = nullptr;
	Node* cur = _root;

	//查找新节点的插入位置
	while (cur)
	{
		parent = cur;
		if (kv.first > cur->_kv.first)
			cur = cur->_right;
		else if (kv.first < cur->_kv.first)
			cur = cur->_left;
		else
			return false;
	}

	cur = new Node(kv);
	//将父节点与新节点链接
	//判断新节点插入到parent的左边还是右边
	if (kv.first > parent->_kv.first) //新节点插入到parent的右边
		parent->_right = cur;
	else
		parent->_left = cur;
	//更改新节点的父亲指针
	cur->_parent = parent;

	//更新平衡因子
	while (parent)
	{
		//插入节点后除了对父节点造成影响还可能对祖宗节点造成影响
		//随着循环进行，cur不一定为新节点
		//更新父节点的平衡因子
		if (cur == parent->_left)
			parent->_bf--;
		else
			parent->_bf++;

		//检查更新后父亲的平衡因子
		//_bf为0，说明树还是AVL树，退出循环
		if (parent->_bf == 0)
			break;
		//_bf == 1/-1,说明需要继续向上更新平衡因子
		else if (parent->_bf == 1 || parent->_bf == -1)
		{
			cur = parent;
			parent = parent->_parent;
		}
		//_bf == 2/-2，说明AVL树失衡，需要进行旋转操作
		else if (parent->_bf == 2 || parent->_bf == -2)
		{
			//插入后AVl树失衡，需要进行平衡调整
			if (parent->_bf == -2 && cur->_bf == -1)
				//右单旋
				RotateR(parent);
			else if (parent->_bf == 2 && cur->_bf == 1)
				//左单旋
				RotateL(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树的查找与二叉搜索树是一摸一样的。

Node* Find(const K& key)
{
	Node* cur = _root;

	while (cur)
	{
		if (key > cur->_kv.first)
			cur = cur->_right;
		else if (key > cur->_kv.first)
			cur = cur->_left;
		else
			return cur;
	}

	return nullptr;
}

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

我们来跑个测试用例。

void test_AVLTree1()
{
	AVLTree<int, int> avlT1;
	AVLTree<int, int> avlT2;

	int a1[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };
	int a2[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };

	for (auto e : a1)
	{
		avlT1.Insert({ e, e });

	}

	for (auto e : a2)
	{
		avlT2.Insert({ e, e });

	}

	avlT1.InOrder();
	avlT2.InOrder();
	
}

可以看到结果是没问题的。

验证平衡

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

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

	int LeftHeight = _Height(root->_left);
	int RightHeight = _Height(root->_right);

	return (LeftHeight > RightHeight ? LeftHeight : RightHeight) + 1;
}

bool IsBalanceTree()
{
	return _IsBalanceTree(_root);
}

bool _IsBalanceTree(Node* root)
{
	// 空树也是AVL树
	if (root == nullptr)
		return true;

	// 计算pRoot结点的平衡因子：即Root左右子树的高度差
	int LeftHeight = _Height(root->_left);
	int RightHeight = _Height(root->_right);
	int diff = RightHeight - LeftHeight;

	// 如果计算出的平衡因子与Root的平衡因子不相等，或者
	// pRoot平衡因子的绝对值超过1，则一定不是AVL树
	if (abs(diff) >= 2)
	{
		cout << root->_kv.first << "高度异常" << endl;
		return false;
	}

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

	// pRoot的左和右如果都是AVL树，则该树一定是AVL树
	return _IsBalanceTree(root->_left) && _IsBalanceTree(root->_right);

	

我们用大量数据来测试下。

void test_AVLTree2()
{
	const int N = 1000000;
	vector<int> v;
	v.reserve(N);
	srand((unsigned int)time(0));
	for (size_t i = 0; i < N; i++)
	{
		v.push_back(rand() + i);
	}

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

	if (t.IsBalanceTree())
		cout << "是AVL树" << endl;
	else
		cout << "不是AVL树" << endl;
	
	cout << "Height:" << t.Height() << endl;
	cout << "Size:" << t.Size() << endl;

}

完整代码

#include<iostream>
#include<assert.h>
using namespace std;

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;

	AVLTreeNode(const pair<K, V>& kv)
		:_kv(kv)
		, _left(nullptr)
		,_right(nullptr)
		,_parent(nullptr)
		,_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)
		{
			parent = cur;
			if (kv.first > cur->_kv.first)
				cur = cur->_right;
			else if (kv.first < cur->_kv.first)
				cur = cur->_left;
			else
				return false;
		}

		cur = new Node(kv);
		//将父节点与新节点链接
		//判断新节点插入到parent的左边还是右边
		if (kv.first > parent->_kv.first) //新节点插入到parent的右边
			parent->_right = cur;
		else
			parent->_left = cur;
		//更改新节点的父亲指针
		cur->_parent = parent;

		//更新平衡因子
		while (parent)
		{
			//插入节点后除了对父节点造成影响还可能对祖宗节点造成影响
			//随着循环进行，cur不一定为新节点
			//更新父节点的平衡因子
			if (cur == parent->_left)
				parent->_bf--;
			else
				parent->_bf++;

			//检查更新后父亲的平衡因子
			//_bf为0，说明树还是AVL树，退出循环
			if (parent->_bf == 0)
				break;
			//_bf == 1/-1,说明需要继续向上更新平衡因子
			else if (parent->_bf == 1 || parent->_bf == -1)
			{
				cur = parent;
				parent = parent->_parent;
			}
			//_bf == 2/-2，说明AVL树失衡，需要进行旋转操作
			else if (parent->_bf == 2 || parent->_bf == -2)
			{
				//插入后AVl树失衡，需要进行平衡调整
				if (parent->_bf == -2 && cur->_bf == -1)
					//右单旋
					RotateR(parent);
				else if (parent->_bf == 2 && cur->_bf == 1)
					//左单旋
					RotateL(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;

	}

	void RotateR(Node* parent)
	{
		//subL为parent的左孩子节点
		Node* subL = parent->_left;
		//subLR为subL的右子节点
		Node* subLR = subL->_right;

		// 将parent与subLR节点进行链接
		parent->_left = subLR;
		//在SubLR的情况下更改，让其指向正确的父亲
		if (subLR)
			subLR->_parent = parent;

		//提前记录祖父节点
		Node* pParent = parent->_parent;

		//链接subL与parent
		subL->_right = parent;
		parent->_parent = subL;

		//根据parent是否是根节点进行不同处理
		if (parent == _root)
		{
			_root = subL;
			subL->_parent = nullptr;
		}
		else 
		{
			//将pParent和subL链接
			//但得先判断parent是pParent的左节点还是右节点
			if (pParent->_left == parent)
				pParent->_left = subL;
			else
				pParent->_right = subL;

			//修改subL的parent指针，让其指向正确的父亲
			subL->_parent = pParent;
		}

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

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

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

		Node* pParent = parent->_parent;

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

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

			subR->_parent = pParent;
		}

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

	void RotateLR(Node* parent)
	{
		Node* subL = parent->_left;
		Node* subLR = subL->_right;
		//记录subLR的bf，根据其取值更新左右双旋后各个节点的bf
		int bf = subLR->_bf;	

		RotateL(subL);
		RotateR(parent);

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

	}

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

	}

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

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

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

	bool IsBalanceTree()
	{
		return _IsBalanceTree(_root);
	}

	Node* Find(const K& key)
	{
		Node* cur = _root;

		while (cur)
		{
			if (key > cur->_kv.first)
				cur = cur->_right;
			else if (key > cur->_kv.first)
				cur = cur->_left;
			else
				return cur;
		}

		return nullptr;
	}


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

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

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

		int LeftHeight = _Height(root->_left);
		int RightHeight = _Height(root->_right);

		return (LeftHeight > RightHeight ? LeftHeight : RightHeight) + 1;
	}

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

		return _Size(root->_left) + _Size(root->_right) + 1;
	}

	bool _IsBalanceTree(Node* root)
	{
		// 空树也是AVL树
		if (root == nullptr)
			return true;

		// 计算pRoot结点的平衡因子：即Root左右子树的高度差
		int LeftHeight = _Height(root->_left);
		int RightHeight = _Height(root->_right);
		int diff = RightHeight - LeftHeight;

		// 如果计算出的平衡因子与Root的平衡因子不相等，或者
		// pRoot平衡因子的绝对值超过1，则一定不是AVL树
		if (abs(diff) >= 2)
		{
			cout << root->_kv.first << "高度异常" << endl;
			return false;
		}

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

		// pRoot的左和右如果都是AVL树，则该树一定是AVL树
		return _IsBalanceTree(root->_left) && _IsBalanceTree(root->_right);

	}

private:
	Node* _root = nullptr;
};

拜拜，下期再见