1. AVL树的概念

        AVL树是最先发明的自平衡二叉树，我们可以将其理解为二叉搜索树的升级版，由于我们在二叉搜索树中可能会存在这样的数据结构

        这使得我们二叉搜索树查询的时间复杂度为O（n），但AVL树就巧妙地解决了这种问题。

        AVL的实现引用了平衡因子的概念，每一个树都有一个平衡因子。

        需要明确的是，插入前的这颗AVL树是一个完整的符合规则的AVL树。

        首先，我们需要根据cur为parent的左子树还是右子树判断其parent的平衡因子是增还是减，其次再更新完对应父亲节点的平衡因子之后，我们需要对其平衡因子进行检查呢，判断是否还需要进行更新。

以下为一颗AVL树例子 

2.  AVL树的实现

2.1 AVL树的结构

类似二叉搜索树的，我们需要实现AVl树的节点。

        其次我们需要定义三个指针：struct AVLTreeNode<K, V>* _left和struct AVLTreeNode<K, V>* _right;用来连接左右的子节点，    struct AVLTreeNode<K, V>* _parent用来连接父亲节点（这也是与二叉搜索树所不同的地方，用于更新平衡因子，后续会讲）

        最后我们用int _bf来储存当前节点的平衡因子的值。

        平衡因子=节点右子树的高度 - 左子树的高度。其次，插入位置必须是在a这棵子树中的任意位置，不能是在b或者c这两颗子树上插入，否则进行的操作就不是右单旋。我们在上一步插入节点之后，定义出来的cur和parent分别指向了新增节点和新增节点的父亲节点，我们需要用其往上遍历。

        需要注意的是SubLRNode可能为空节点，即下图情况

        ​​​​​​​        ​​​​​​​        

        所以在更新SubLRNode的_parent之前，需要判断其是否为空，避免造成空指针的解引用

void RotateR(Node* parent)	{		Node* SubLNode = parent->_left;		Node* SubLRNode = SubLNode->_right;		parent->_left = SubLRNode;		SubLNode->_right = parent;		//定义PPNode保存parent的父亲节点，避免其被后续操作覆盖导致avl断开		Node* PPNode = parent->_parent;		parent->_parent = SubLNode;		//防止SubLRNode为空树，导致该操作造成空指针的解引用		if (SubLRNode)			SubLRNode->_parent = parent;		if (PPNode==nullptr)		{			_root = SubLNode;			SubLNode->_parent = nullptr;		}		else		{			if (PPNode->_left == parent)			{				PPNode->_left = SubLNode;			}			else			{				PPNode->_right = SubLNode;			}			SubLNode->_parent = PPNode;		}		//最后不要忘记更新对应节点的平衡因子		parent->_bf = SubLNode->_bf = 0;	}

2.4.3 左单旋

左单旋过程：

        上图作为左单旋的抽象概括。

public:	bool Insert(const pair<K,V>& kv) { ... }	void Print()	{		_Print(_root);		cout << endl;	}private:	void _Print(Node* root)	{		if (root == nullptr)		{			return;		}    }

2.4 AVL树的旋转

        上述提到过，若当前节点的平衡因子为-2/2，那么就说明需要进行旋转

2.4.1 旋转的⽬标

        1、

        若parent的平衡因子更新完之后值为0，则说明parent的父亲节点的其对应的子树高度并未发生变化，此时说明更新完毕，跳出循环。

        左单旋和右单旋的逻辑甚至注意事项都十分类似，因此这里不再过多赘述

void RotateL(Node* parent)	{		Node* SubRNode = parent->_right;		Node* SubRLNode = SubRNode->_left;		Node* PPNode = parent->_parent;		SubRNode->_left = parent;		parent->_parent = SubRNode;		parent->_right = SubRLNode;		if (SubRLNode)			SubRLNode->_parent = parent;		if (PPNode==nullptr)		{			_root = SubRNode;			SubRNode->_parent = nullptr;		}		else		{			if (PPNode->_left == parent)				PPNode->_left = SubRNode;			else				PPNode->_right = SubRNode;			SubRNode->_parent = PPNode;		}		parent->_bf = SubRNode->_bf = 0;	}

2.4.4 左右双旋

         通过以上两种情况我们可以看到，左单旋和右单旋无法解决所有的情况，事实上他们只能处理纯粹的左边高或者右边高，所有我们引出了双旋的概念。如果插⼊之前10整棵树的⼀个局部⼦树，旋转后不会再影响上⼀层，插⼊结束了。

        若parent的平衡因子更新完之后值为上述之外的值，则说明平衡因子有问题，需要进行断言报错。（类似我们之前说的map容器）

        我们插入的逻辑是定义出cur指针用于遍历AVL树，找到插入节点的位置，并且我们需要一个parent指针记录cur的父亲节点，因为cur指针遍历到最后肯定回指向空，只有记录好了其父亲节点才能将新插入的节点位置cur和其父亲节点parent连接起来。

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 (kv.first < cur->_kv.first)			{				parent = cur;				cur = cur->_left;			}			else if(kv.first > cur->_kv.first )			{				parent = cur;				cur = cur->_right;			}			else			{				return false;			}		}		cur = new Node(kv);		if (kv.first < parent->_kv.first)		{			parent->_left = cur;		}		else		{			parent->_right = cur;		}		cur->_parent = parent;		//更新平衡因子		while (parent)		{			if (cur == parent->_left)			{				parent->_bf--;			}			else			{				parent->_bf++;			}			if (parent->_bf == 0)			{				break;			}			else if (parent->_bf == 1 || parent->_bf == -1)			{				//不为零继续更新				cur = parent;				parent = parent->_parent;			}			else if (parent->_bf == 2 || parent->_bf == -2)			{				//AVL树不平衡了，需要旋转				break;			}			else 			{				//出现平衡因子为二的就跳出了不可能有3				//这种情况说明出错了				assert(false);			}		}		return true;	}

2.3 AVL树的遍历

        此处与二叉搜索树类似，其中序遍历为有序数列，由于需要用到私有成员变量 _root,我们也需要实现一个私有成员函数，再用公有成员函数去调用私有成员函数。

        那么在map/set的博客中，我们也讲过pair类型，其含有first，跟second两个值，其中排序的逻辑是根据pair的first值来进行AVL树的排序，pair的second值则是用来存储数据的。

        如上图所示，我们需要从插入节点 cur 开始往回遍历其父亲节点，这时候我们定义的_parent成员变量便要体现作用了。保持搜索树的规则，把 parent⼦树旋转平衡。

这里我们可以得知，插入节点的位置回导致subLR这颗子树的平衡因此的变化，上述三种情况会导致插入后subLR的平衡因子各不相同，因此我们在双旋之前记录下其平衡因子，在旋转之后通过对其平衡因子的判断从而得知平衡因子的更新路径。

其次我们实现AVL树的结构

        类似二叉搜索树，我们只需要定义一个成员变量也就是AVL树的头节点_root即可。

        左右双旋分为以下情况

1.parent节点的左子树的右子树为空

2. parent节点的左子树的右子树不为空

        再分为两种情况讨论，因为不同种情况双旋出的，其插入的节点位置不同，双旋之后所处的位置也不同，导致节点平衡因子的更新路径也会不同，因此我们需要展开来看b这棵树。

        对于图二，在插⼊在b⼦树中，10为跟的⼦树不再是单纯的左边⾼，对于10是左边⾼，但是对于5是右边⾼，需要⽤两次旋转才能解决，以5为旋转点进⾏⼀个左单旋，以10为旋转点进⾏⼀个右单旋，这棵树 这棵树就平衡了。所以旋转后也需要继续往上更新，插⼊结束。

        需要注意的一点是，parent并非一定为根节点，因此我们将parent->_parent

赋值给一个变量PPNode，对其进行分类讨论

        若parent为原来的根节点，那么最后旋转完之后，不要忘记将更新根节点的位置，并更新新的根节点的_parent指向空。

        我们在开始讲过，平衡因子的定义是左右子树的高度差，使用我们可以定义一个Height函数，通过递归的方式计算出左右子树的高度差从而得到当前节点平衡因子。

左单旋和右单旋的代码前面已经实现过来因此这里只需要套用即可，因此这里需要关注的是如何进行平衡因子的更新。

                        ​​​​​​​        

2.4.2 右单旋

右单旋过程：

        上图作为右单旋的抽象概括。

        若parent的平衡因子更新完之后值为1或-1，说明parent的父亲节点的其对应的子树高度发生了变化，因此还需要向上更新，那么我们就让 cur=parent，parent=parent->_parent。

        若parent的平衡因子更新完之后值为2或-2，说明此时AVL树的结构已经遭到了破坏，我们需要对节点进行旋转处理（后续会讲），在进行旋转之后跳出循环。

        如图，首先在a这颗子树上插入了一个新节点，从而导致值为5的节点平衡因子由0变成了-1，进而导致了值为5的节点的父节点，即值为10的节点平衡因子变为-2。

        若parent不为原来的根节点，那么旋转完之后，需要使PPNode节点指向parent的_parent也就是SubLNode。

      旋转核⼼步骤，因为5<b⼦树的值<10,将b变成10的左⼦树，10变成5的右⼦树，5变成这棵树新 的根，符合搜索树的规则，控制了平衡，同时这棵的⾼度恢复到了插⼊之前的h+2，符合旋转原 则。

更新平衡因子

        插入的逻辑与二叉搜索树大致类似，所以我们更需要关注的是，AVL树在插入节点后必然会导致平衡因子发生变化。新增结点以后，只会影响祖先结点的⾼度，也就是可能会影响部分祖先结点的平衡因⼦，所以更新 从新增结点->根结点路径上的平衡因⼦，实际中最坏情况下要更新到根。

template<class K,class V>struct AVLTreeNode{	pair<K, V> _kv;	struct AVLTreeNode<K, V>* _left;	struct AVLTreeNode<K, V>* _right;	struct 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 Node;public:	//AVL树功能的实现private:	Node* _root = nullptr;};

2.2. AVL树的插入

插入

        首先我们要插入节点，这过程与二叉搜索树类似，只不过AVl树的节点存储的数据类型为pair类型。随后再定义一个函数IsBalanceTre，递归检查是否AVL树中的每一个节点都满足即可

对于这种递归的成员函数，我们最好将其实现为私有函数，通过一个公有成员函数去调用

public：    bool IsBalanceTree()	{		return _IsBalanceTree(_root);	}private：	    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)	{		if (nullptr == root)			return true;		int leftHeight = _Height(root->_left);		int rightHeight = _Height(root->_right);		int diff = rightHeight - leftHeight;		if (abs(diff) >= 2)		{			cout << root->_kv.first << "高度差异常" << endl;			return false;		}		if (root->_bf != diff)		{			cout << root->_kv.first << "平衡因子异常" << endl;			return false;		}		return _IsBalanceTree(root->_left) && _IsBalanceTree(root->_right);	}

3.源代码

3.1 AVL Tree.h

#pragma once#include<iostream>#include<assert.h>using namespace std;template<class K,class V>struct AVLTreeNode{	pair<K, V> _kv;	struct AVLTreeNode<K, V>* _left;	struct AVLTreeNode<K, V>* _right;	struct 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)		{			if (kv.first < cur->_kv.first)			{				parent = cur;				cur = cur->_left;			}			else if(kv.first > cur->_kv.first )			{				parent = cur;				cur = cur->_right;			}			else			{				return false;			}		}		cur = new Node(kv);		if (kv.first < parent->_kv.first)		{			parent->_left = cur;		}		else		{			parent->_right = cur;		}		cur->_parent = parent;		//更新平衡因子		while (parent)		{			if (cur == parent->_left)			{				parent->_bf--;			}			else			{				parent->_bf++;			}			if (parent->_bf == 0)			{				break;			}			else if (parent->_bf == 1 || parent->_bf == -1)			{				//不为零继续更新				cur = parent;				parent = parent->_parent;			}			else if (parent->_bf == 2 || parent->_bf == -2)			{				// 旋转				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 			{				//出现平衡因子为二的就跳出了不可能有3				//这种情况说明出错了				assert(false);			}		}		return true;	}	void RotateR(Node* parent)	{		Node* SubLNode = parent->_left;		Node* SubLRNode = SubLNode->_right;		parent->_left = SubLRNode;		SubLNode->_right = parent;		//定义PPNode保存parent的父亲节点，避免其被后续操作覆盖导致avl断开		Node* PPNode = parent->_parent;		parent->_parent = SubLNode;		//防止parent为头节点，导致该操作造成空指针的解引用		if (SubLRNode)			SubLRNode->_parent = parent;		if (PPNode==nullptr)		{			_root = SubLNode;			SubLNode->_parent = nullptr;		}		else		{			if (PPNode->_left == parent)			{				PPNode->_left = SubLNode;			}			else			{				PPNode->_right = SubLNode;			}			SubLNode->_parent = PPNode;		}		//最后不要忘记更新对应节点的平衡因子		parent->_bf = SubLNode->_bf = 0;	}	void RotateL(Node* parent)	{		Node* SubRNode = parent->_right;		Node* SubRLNode = SubRNode->_left;		Node* PPNode = parent->_parent;		SubRNode->_left = parent;		parent->_parent = SubRNode;		parent->_right = SubRLNode;		if (SubRLNode)			SubRLNode->_parent = parent;		if (PPNode==nullptr)		{			_root = SubRNode;			SubRNode->_parent = nullptr;		}		else		{			if (PPNode->_left == parent)				PPNode->_left = SubRNode;			else				PPNode->_right = SubRNode;			SubRNode->_parent = PPNode;		}		parent->_bf = SubRNode->_bf = 0;	}	void RotateLR(Node* parent)	{		Node* SubLNode = parent->_left;		Node* SubLRNode = SubLNode->_right;		int bf = SubLRNode->_bf;		RotateL(SubLNode);		RotateR(parent);		if (bf == 0)		{			SubLNode->_bf = 0;			SubLRNode->_bf = 0;			parent->_bf = 0;		}		else if (bf == 1)		{			SubLNode->_bf = -1;			SubLRNode->_bf = 0;			parent->_bf = 0;		}		else if( bf == -1 )		{			SubLNode->_bf = 0;			SubLRNode->_bf = 0;			parent->_bf = 1;		}		else		{			assert(false);		}	}	void RotateRL(Node* parent)	{		Node* SubRNode = parent->_right;		Node* SubRLNode = SubRNode->_left;		int bf = SubRLNode->_bf;		RotateR(SubRNode);		RotateL(parent);		if (bf == 0)		{			SubRNode->_bf = 0;			SubRLNode->_bf = 0;			parent->_bf = 0;		}		else if (bf == 1)		{			SubRNode->_bf = 0;			SubRLNode->_bf = 0;			parent->_bf = -1;		}		else if (bf == -1)		{			SubRNode->_bf = 1;			SubRLNode->_bf = 0;			parent->_bf = 0;		}		else		{			assert(false);		}	}	void Print()	{		_Print(_root);		cout << endl;	}	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;	}	bool IsBalanceTree()	{		return _IsBalanceTree(_root);	}private:	void _Print(Node* root)	{		if (root == nullptr)		{			return;		}		_Print(root->_left);		cout << root->_kv.first << " " << root->_kv.second<<endl;		_Print(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 + 1 : rightHeight + 1;	}	bool _IsBalanceTree(Node* root)	{		if (nullptr == root)			return true;		int leftHeight = _Height(root->_left);		int rightHeight = _Height(root->_right);		int diff = rightHeight - leftHeight;		if (abs(diff) >= 2)		{			cout << root->_kv.first << "高度差异常" << endl;			return false;		}		if (root->_bf != diff)		{			cout << root->_kv.first << "平衡因子异常" << endl;			return false;		}		return _IsBalanceTree(root->_left) && _IsBalanceTree(root->_right);	}	Node* _root = nullptr;};

3.2 AVL Tree.c

#define _CRT_SECURE_NO_WARNINGS 1#include"AVL Tree.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;}int main(){	TestAVLTree1();	//AVLTree<int,string> avl;	//avl.Insert({ 1,"h"});	//avl.Insert({ 2,"e" });	//avl.Insert({ 3,"l" });	//avl.Insert({ 4,"l" });	//avl.Insert({ 5,"o"});	//avl.Print();	return 0;}