【C++】AVL 树平衡二叉搜索的神奇结构，代码实现全解析，从概念到应用，助你轻松掌握这一高效数据结构，编程能力更上一层楼！

//节点
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
{
    //重命名为Node
	typedef AVLTreeNode<K, V> Node;
public:
	//...
private:
	Node* _root = nullptr;
};

//节点
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* cur = _root;
		Node* par = nullptr;
		//走到空
		while (cur)
		{
			//小于往左走
			if (kv.first < cur->_kv.first)
			{
				par = cur;
				cur = cur->_left;
			}
			//大于往右走
			else if (kv.first > cur->_kv.first)
			{
				par = cur;
				cur = cur->_right;
			}
			else
			{
				return false;
			}
		}
		//判断该插入左边还是右边
        cur = new Node(kv);
		if (kv.first < par->_kv.first)
		{
			par->_left = cur;
		}
		else
		{
			par->_right = cur;
		}
		//连接父亲节点
        cur->_parent = par;

		//更新平衡因子
		while (par != nullptr)
		{
			//是左子树平衡因子就--
			if (par->_left == cur)
			{
				par->_bf--;
			}
			else //是右子树平衡因子就++
			{
				par->_bf++;
			}

			if (par->_bf == 0)
			{
				//更新结束
				break;
			}
			else if (par->_bf == 1 || par->_bf == -1)
			{
				//继续向上更新
				cur = par;
				par = par->_parent;
			}
			else if (par->_bf == 2 || par->_bf == -2)
			{
				//不平衡,旋转处理

                //旋转完结束循环
				break
			}
			else
			{
				//其他数值就说明有问题，assert报错
				assert(false);
			}
		}
      return true;
	}

private:
	Node* _root = nullptr;
};

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

	parent->_left = subLR;
	//subLR节点不为空，连接父亲节点
	if (subLR != nullptr)
	{
		subLR->_parent = parent;
	}
	//parent上面有可能还有节点，保存parent的父亲节点
	Node* ppNode = parent->_parent;

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

	//如果ppNode为空，就说明parent之前为根节点
	if (ppNode == nullptr)
	{
		//更新根节点
		_root = subL;
		//父亲节点指向空
		subL->_parent = nullptr;
	}
	else //不为空，说明还有节点
	{
		//判断ppNode连接左边还是右边
		if (ppNode->_left == parent)
		{
			ppNode->_left = subL;
		}
		else
		{
			ppNode->_right = subL;
		}
		//ppNode给subL的父亲节点
		subL->_parent = ppNode;

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

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

	parent->_right = subRL;
	//subRL节点不为空，连接父亲节点
	if (subRL != nullptr)
	{
		subRL->_parent = parent;
	}
	//parent上面有可能还有节点，保存parent的父亲节点
	Node* ppNode = parent->_parent;
	subR->_left = parent;
	parent->_parent = subR;
	//如果ppNode为空，就说明parent之前为根节点
	if (ppNode == nullptr)
	{
		//更新根节点
		_root = subR;
		//父亲节点指向空
		subR->_parent = nullptr;
	}
	else // //不为空，说明还有节点
	{
		//判断ppNode连接左边还是右边
		if (ppNode->_left == parent)
		{
			ppNode->_left = subR;
		}
		else
		{
			ppNode->_right = subR;
		}
		//subL的父亲节点连接ppNode。
		subR->_parent = ppNode;
	}
	//更新平衡因子
	parent->_bf = 0;
	subR = 0;
}

//左右双旋
void RotLR(Node* parent)
{
	// 1. 先保存相关节点指针
	
	// 保存parent节点的左子节点
	Node* subL = parent->_left;
	// 保存左子节点的右子节点
	Node* subLR = subL->_right;
	// 保存subLR节点的平衡因子，后续用于调整各节点的平衡因子
	int bf = subLR->_bf;
	//左单旋
	RotL(parent->_left);
	//右单旋
	RotR(parent);

	// 4. 根据subLR节点原本的平衡因子来调整parent、subL和subLR节点的平衡因子

	if (bf == -1)
	{
		// 如果subLR的平衡因子为 -1，说明其右子树较高
		parent->_bf = 1;
		subL->_bf = 0;
		subLR->_bf = 0;//平衡因子为0，节点平衡
	}

	else if (bf == 1)
	{
		// 如果subLR的平衡因子为1，说明其左子树较高
		parent->_bf = 0;
		// subL的平衡因子变为 -1，因为右子树相对变高
		subL->_bf = -1;
		subLR->_bf = 0;
	}
	else if (bf == 0)
	{
		// 如果subL的平衡因子为0，说明subL的左右子树等高
		parent->_bf = 0;
		subL->_bf = 0;
		subLR->_bf = 0;
	}
	else
	{
		// 理论上bf只可能是 -1、0、1这三个值，如果出现其他值，说明程序逻辑有错误，触发断言
		assert(false);
	}
}

	//右左双旋
	void RotRL(Node* parent)
	{
		// 保存parent节点的右子节点
		Node* subR = parent->_right;
		// 保存右子节点的左子节点
		Node* subRL = subR->_left;
		// 保存subRL节点的平衡因子，后续用于调整各节点的平衡因子
		int bf = subRL->_bf;
		//右单旋
		RotR(parent->_right);
		//左单旋
		RotL(parent);

		if (bf == -1)
		{
			// 如果subRL的平衡因子是 -1，说明它的左子树更高
		    // 旋转后，parent节点恢复平衡，平衡因子设为0
			parent->_bf = 0;
			// subR节点的右子树会相对变高，平衡因子设为1
			subR->_bf = 1;
			subRL->_bf = 0;
		}
		else if (bf == 1)
		{
			// 如果subRL的平衡因子是 1，说明它的右子树更高
		    // 旋转后，parent节点平衡因子设为 -1
			parent->_bf = -1;
			subR->_bf = 0;
			subRL->_bf = 0;
		}
		else if (bf == 0)
		{
			// 如果subRL平衡因子是0，说明它左右子树等高
			parent->_bf = 0;
			subR->_bf = 0;
			subRL->_bf = 0;
		}
		else
		{
			// 理论上bf只可能是 -1、0、1这三个值，如果出现其他值，说明程序逻辑有错误，触发断言
			assert(false);
		}
	}

    //查询和二叉搜索树一样
	bool  find(const K& key)
	{
		Node* cur = _root;
		while (cur)
		{
			if (key < cur->_kv.first)
			{
				cur = cur->_left;
			}
			else if(key > cur->_kv.first)
			{
				cur = cur->_right;
			}
			else
			{
				return true;
			}
		}
		return false;
	}

//计算节点的平衡因子
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;
}


bool _IsBalanceTree(Node* root)
{
	// 空树也是AVL树 
	if (nullptr == root)
		return true;
	// 计算pRoot结点的平衡因⼦：即pRoot左右⼦树的⾼度差 
	int leftHeight = _Height(root->_left);
	int rightHeight = _Height(root->_right);
	int diff = rightHeight - leftHeight;
	// 如果计算出的平衡因⼦与pRoot的平衡因⼦不相等，或者 
// 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);
}

	int _Size(Node* root)
	{
		if (root == nullptr)
		{
			return 1;
		}
		return _Size(root->_left) + _Size(root->_right) + 1;

	}

// 插⼊⼀堆随机值，测试平衡，顺便测试⼀下⾼度和性能等 
void TestAVLTree2()
{
	const int N = 100000;
	vector<int> v;
	v.reserve(N);
	srand(time(0));
	for (size_t i = 0; i < N; i++)
	{
		v.push_back(rand() + i);
	}
	size_t begin2 = clock();
	AVLtree<int, int> t;
	for (auto e : v)
	{
		t.insert(make_pair(e, e));
	}
	size_t end2 = clock();
	cout << "Insert:" << end2 - begin2 << endl;
	cout << t.IsBalanceTree() << endl;
	cout << "Height:" << t.Height() << endl;
	cout << "Size:" << t.Size() << endl;
	size_t begin1 = clock();
	// 确定在的值 
	/*for (auto e : v)
	{
	t.Find(e);
	}*/
	// 随机值 
	for (size_t i = 0; i < N; i++)
	{
		t.Find((rand() + i));
	}
	size_t end1 = clock();
	cout << "Find:" << end1 - begin1 << endl;
}

#pragma once
#include<iostream>
#include<map>
#include<assert.h>
#include<vector>
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* cur = _root;
		Node* par = nullptr;
		//走到空
		while (cur)
		{
			//小于往左走
			if (kv.first < cur->_kv.first)
			{
				par = cur;
				cur = cur->_left;
			}
			//大于往右走
			else if (kv.first > cur->_kv.first)
			{
				par = cur;
				cur = cur->_right;
			}
			else
			{
				return false;
			}
		}
		//判断该插入左边还是右边
		cur = new Node(kv);
		if (kv.first < par->_kv.first)
		{
			par->_left = cur;
		}
		else
		{
			par->_right = cur;
		}
		//连接父亲节点
		cur->_parent = par;

		//更新平衡因子
		while (par != nullptr)
		{
			//左子树--
			if (par->_left == cur)
			{
				par->_bf--;
			}
			else //右子树++
			{
				par->_bf++;
			}

			if (par->_bf == 0)
			{
				//更新结束
				break;
			}
			else if (par->_bf == 1 || par->_bf == -1)
			{
				//继续向上更新
				cur = par;
				par = par->_parent;
			}
			else if (par->_bf == 2 || par->_bf == -2)
			{
				//左边不平衡,右单旋处理
				if (par->_bf == -2 && cur->_bf == -1)
				{
					//调用右单旋处理
					RotR(par);
				}
				//右边不平衡,左单旋处理
				else if (par->_bf == 2 && cur->_bf == 1)
				{
					//调用左单旋处理
					RotL(par);
				}
				else if (par->_bf == -2 && cur->_bf == 1)
				{
					//调用左右双旋处理
					RotLR(par);
				}
				else if (par->_bf == 2 && cur->_bf == -1)
				{
					//调用右左双旋处理
					RotRL(par);
				}
				else
				{
					assert(false);
				}

				break;
			}
			else
			{
				//其他数值就说明有问题，assert报错
				assert(false);
			}
		}
		return true;
	}
	//右旋转
	void RotR(Node* parent)
	{
		Node* subL = parent->_left;
		Node* subLR = subL->_right;

		parent->_left = subLR;
		//subLR节点不为空，连接父亲节点
		if (subLR != nullptr)
		{
			subLR->_parent = parent;
		}
		//parent上面有可能还有节点，保存parent的父亲节点
		Node* ppNode = parent->_parent;

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

		//如果ppNode为空，就说明parent之前为根节点
		if (ppNode== nullptr)
		{
			//更新根节点
			_root = subL;
			//父亲节点指向空
			subL->_parent = nullptr;
		}
		else //不为空，说明还有节点
		{
			//判断ppNode连接左边还是右边
			if (ppNode->_left == parent)
			{
				ppNode->_left = subL;
			}
			else
			{
				ppNode->_right = subL;
			}
			//ppNode给subL的父亲节点
			subL->_parent = ppNode;

		}
		parent->_bf = 0;
		subL->_bf = 0;
	}
	//左旋转
	void RotL(Node* parent)
	{
		Node* subR = parent->_right;
		Node* subRL = subR->_left;

		parent->_right = subRL;
		//subRL节点不为空，连接父亲节点
		if (subRL != nullptr)
		{
			subRL->_parent = parent;
		}
		//parent上面有可能还有节点，保存parent的父亲节点
		Node* ppNode = parent->_parent;
		subR->_left = parent;
		parent->_parent = subR;
		//如果ppNode为空，就说明parent之前为根节点
		if (ppNode == nullptr)
		{
			//更新根节点
			_root = subR;
			//父亲节点指向空
			subR->_parent = nullptr;
		}
		else // //不为空，说明还有节点
		{
			//判断ppNode连接左边还是右边
			if (ppNode->_left == parent)
			{
				ppNode->_left = subR;
			}
			else
			{
				ppNode->_right = subR;
			}
			//subL的父亲节点连接ppNode。
			subR->_parent = ppNode;
		}
		//更新平衡因子
		parent->_bf = 0;
		subR->_bf = 0;
	}
	//左右双旋
	void RotLR(Node* parent)
	{
		// 1. 先保存相关节点指针
		
		// 保存parent节点的左子节点
		Node* subL = parent->_left;
		// 保存左子节点的右子节点
		Node* subLR = subL->_right;
		// 保存subLR节点的平衡因子，后续用于调整各节点的平衡因子
		int bf = subLR->_bf;
		//左单旋
		RotL(parent->_left);
		//右单旋
		RotR(parent);

		// 4. 根据subLR节点原本的平衡因子来调整parent、subL和subLR节点的平衡因子

		if (bf == -1)
		{
			// 如果subLR的平衡因子为 -1，说明其右子树较高
			parent->_bf = 1;
			subL->_bf = 0;
			subLR->_bf = 0;//平衡因子为0，左右子树高度平衡
		}

		else if (bf == 1)
		{
			// 如果subLR的平衡因子为1，说明其左子树较高
			parent->_bf = 0;
			// subL的平衡因子变为 -1，因为右子树相对变高
			subL->_bf = -1;
			subLR->_bf = 0;
		}
		else if (bf == 0)
		{
			// 如果subL的平衡因子为0，说明subL的左右子树等高
			parent->_bf = 0;
			subL->_bf = 0;
			subLR->_bf = 0;
		}
		else
		{
			// 理论上bf只可能是 -1、0、1这三个值，如果出现其他值，说明程序逻辑有错误，触发断言
			assert(false);
		}
	}
	//右左双旋
	void RotRL(Node* parent)
	{
		// 保存parent节点的右子节点
		Node* subR = parent->_right;
		// 保存右子节点的左子节点
		Node* subRL = subR->_left;
		// 保存subRL节点的平衡因子，后续用于调整各节点的平衡因子
		int bf = subRL->_bf;
		//右单旋
		RotR(parent->_right);
		//左单旋
		RotL(parent);

		if (bf == -1)
		{
			// 如果subRL的平衡因子是 -1，说明它的左子树更高
			// 旋转后，parent节点恢复平衡，平衡因子设为0
			parent->_bf = 0;
			// subR节点的右子树会相对变高，平衡因子设为1
			subR->_bf = 1;
			subRL->_bf = 0;
		}
		else if (bf == 1)
		{
			// 如果subRL的平衡因子是 1，说明它的右子树更高
			// 旋转后，parent节点平衡因子设为 -1
			parent->_bf = -1;
			subR->_bf = 0;
			subRL->_bf = 0;
		}
		else if (bf == 0)
		{
			// 如果subRL平衡因子是0，说明它左右子树等高
			parent->_bf = 0;
			subR->_bf = 0;
			subRL->_bf = 0;
		}
		else
		{
			// 理论上bf只可能是 -1、0、1这三个值，如果出现其他值，说明程序逻辑有错误，触发断言
			assert(false);
		}
	}
	Node*  Find(const K& key)
	{
		Node* cur = _root;
		while (cur)
		{
			if (key < cur->_kv.first)
			{
				cur = cur->_left;
			}
			else if(key > cur->_kv.first)
			{
				cur = cur->_right;
			}
			else
			{
				return cur;
			}
		}
		return nullptr;
	}

	void print()
	{
		zho(_root);
	}
	bool IsBalanceTree()
	{
		return  _IsBalanceTree(_root);
	}
	int Size()
	{
		return _Size(_root);
	}
	int Height()
	{
		return _Height(_root);
	}


private:

	int _Size(Node* root)
	{
		if (root == nullptr)
		{
			return 1;
		}
		return _Size(root->_left) + _Size(root->_right) + 1;

	}


	//计算节点的平衡因子
	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;
	}


	bool _IsBalanceTree(Node* root)
	{
		// 空树也是AVL树 
		if (nullptr == root)
			return true;
		// 计算pRoot结点的平衡因⼦：即pRoot左右⼦树的⾼度差 
		int leftHeight = _Height(root->_left);
		int rightHeight = _Height(root->_right);
		int diff = rightHeight - leftHeight;
		// 如果计算出的平衡因⼦与pRoot的平衡因⼦不相等，或者 
 // 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 zho(Node* root)
	{
		if (root == nullptr)
		{
			return;
		}

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

	Node* _root = nullptr;
};

#include"AVLtree.h"


// 测试代码 
void TestAVLTree1()
{
	AVLtree<int, int> t;
	// 常规的测试⽤例 
	//int a[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };
	// 特殊的带有双旋场景的测试⽤例 
	int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };
	for (auto e : a)
	{
		t.insert({ e, e });
	}
	t.print();
	cout << t.IsBalanceTree() << endl;
}
// 插⼊⼀堆随机值，测试平衡，顺便测试⼀下⾼度和性能等 
void TestAVLTree2()
{
	const int N = 100000;
	vector<int> v;
	v.reserve(N);
	srand(time(0));
	for (size_t i = 0; i < N; i++)
	{
		v.push_back(rand() + i);
	}
	size_t begin2 = clock();
	AVLtree<int, int> t;
	for (auto e : v)
	{
		t.insert(make_pair(e, e));
	}
	size_t end2 = clock();
	cout << "Insert:" << end2 - begin2 << endl;
	cout << t.IsBalanceTree() << endl;
	cout << "Height:" << t.Height() << endl;
	cout << "Size:" << t.Size() << endl;
	size_t begin1 = clock();
	// 确定在的值 
	/*for (auto e : v)
	{
	t.Find(e);
	}*/
	// 随机值 
	for (size_t i = 0; i < N; i++)
	{
		t.Find((rand() + i));
	}
	size_t end1 = clock();
	cout << "Find:" << end1 - begin1 << endl;
}

int main()
{
	//TestAVLTree1();
	TestAVLTree2();

	return 0;
}