1.AVL树概念

二叉搜索树虽可以缩短查找的效率，但如果数据有序或接近有序二叉搜索树将退化为单支树，查
找元素相当于在顺序表中搜索元素，效率低下,
所以在此基础上提出解决办法：
当向二叉搜索树中插入新节结点时，如果能保证每个节点的左右子树高度之差的绝对值不超过1即可降低树的高度，从而减少平均搜索长度
AVL树又称平衡二叉搜索树

2. AVL树性质

AVL树的性质：
1.它的左右子树都是AVL树
2.左右子树高度之差(平衡因子)的绝对值不超过1(1/0/-1)
平衡因子=右子树高度-左子树高度

3.AVL树的实现

在实现结构与插入功能时，与二叉搜索树有很多相似的地方 ：二叉搜索树
所以一部分关于二叉搜索树的地方就不详细说了

---

与二叉搜索树定义结构不同的是，多了一个父节点parent以及平衡因子bf

insert

insert的实现前半部分与二叉搜索树的insert实现大部分相同

---

parent的右子树连接新节点为例，出while循环后，需要反向链接父节点，而此时的父节点就为刚才记录cur前一个节点的parent

---

插入情况分析

---

1.

若新增节点作为parent的右子树即cur==parent->right
parent的平衡因子+1 即 parent->bf++

---

若新增节点作为parent的左子树即cur==parent->left
parent的平衡因子 -1 即 parent->bf–

---

3.

若新增节点作为parent的左子树即cur==parent->left
parent的平衡因子-1 即 parent->bf–

---

若parent的平衡因子等于1或者-1 即第一种与第二种情况，说明parent所在子树变了，需要继续向上更新爷爷节点
为什么需要继续更新？
说明插入前parent的平衡因子为0，插入前左右高度相等，现在一边高1，高度变了

若parent的平衡因子等于2或者-2 ， 说明parent所在子树不平衡，需要以旋转的方式处理子树

若parent的平衡因子等于0， parent所在子树高度不变，就不需要向上更新，插入结束了
为什么插入结束了呢？
插入前parent的平衡因子是-1或者1，插入前一边高一边低，插入节点到矮的那边，高度不变

更新平衡因子

插入新增节点后，更新平衡因子
如果更新之后，平衡因子没有问题(绝对值<=1)，说明插入对树的平衡机构没有影响，不需要处理
如果更新之后，平衡出现问题，平衡结构受到影响(平衡因子为2/-2)，需要旋转
插入新增节点，会影响部分/整体祖先

旋转处理

旋转的原则：保持继续是搜索树
旋转的目的：左右均衡，降低高度

---

a/b/c分别代表高度为h的AVL子树
平衡因子=右子树深度-左子树深度

---

情况1——h=0

当h=0时，60的平衡因子：0-1=-1
30的平衡因子：2-0=2
由于平衡因子出现2，所以需要旋转

---

情况2——h=1

当h=2时，60的平衡因子:2-1=1，30的平衡因子:3-1=2
由于平衡因子出现2，所以需要旋转
在parent节点左右插入，都会引发平衡因子变为2

---

情况3——h=2

---

对于c来说，必定是x形状
假设c为y形状

在左子树新插入一个节点，那这颗子树的平衡因子变为-2，需要旋转，而不会去往上更新到30

---

若右子树插入一个节点，parent的平衡因子变为0，不需要往上更新到30

---

对于a和b，必定是x、y、z中的一种形状

假设abc都是x形状，则在c中插入节点，无论插入左边还是右边，都会导致parent的平衡因子为2或者-2

c的高度变化，必定引发旋转

---

在红框中的四个位置任意一边插入，30的平衡因子都会变为2/-2

虽然分为三种情况，但是旋转的规则是相同

左单旋

以h=1为例

左单旋的旋转方式：
把B变成30的右边，30变成60的左边，60变成整棵树的根

---

左单旋抽象图

父节点问题
把subR作为30的右子树时，需要更新sub的父节点为parent
把parent作为subR的左子树时，更新parent的父节点为subR

有可能当前旋转的是整棵树或者整棵树的一部分
设置一个ppnode，用于存放parent的父节点
若旋转一部分时，跟ppnode相连接，同时也要判断连接到左子树还是右子树
若旋转整棵树时，父节点置NULL，subR作为新的根

---

右单旋

在a处新增节点，使其高度变为h+1，造成旋转
右单旋的旋转方式：
b作为60的左边，60作为30的右边，30变成整棵树的根
右单旋h与左单旋一样，都有h为1、2、3的三种情况，只不过右单旋的插入节点在a处，其他的条件都是相同的

---

右单旋跟左单旋思想相同，
只不过把b作为60的左子树，再把60作为30的右子树
同样考虑父节点问题以及旋转整棵树或者部分子树旋转问题

---

在insert中判断左右单旋的条件

当parent的平衡因子为2并且cur的平衡因子为1时，为左单旋

---

当parent的平衡因子为-2并且cur的平衡因子为-1时，为右单旋

---

双旋转

抽象图

---

当h=0时，60作为新增节点

---

当h==1时，60的左右子树新增都会引用旋转

---

假设在左子树处新增节点

---

若h==2时

a/d是x/y/z中的任意一种
b/c的孩子位置的任意一点插入节点，都会引发旋转

左右双旋

当h==2时， 假设在b的右子树插入节点

将30进行左旋：30是parent的左子树
将b作为30的右子树，将30作为60的左子树，将60作为90的左子树

---

将60进行右旋：60作为整棵树新的根
将60的右子树作为90的左子树，将90作为60的右子树

---

假设在c的右子树插入新增节点

新增节点插入在b和c节点，各个位置的平衡因子是不一样的

---

当h=0时，左右双旋后，平衡因子与上述两个也是不同的

---

当subLR即60节点处的平衡因子为-1时，说明在b处插入新增节点，
双旋后 subl的平衡因子为0，subLR的平衡因子为0，parent的平衡因子为1

当subLR即60节点处的平衡因子为1时，说明在c处插入新增节点，
双旋后 subl的平衡因子为-1，subLR的平衡因子为0，parent的平衡因子为0

当subLR即60节点处的平衡因子为0时，说明在60即为新增节点，
双旋后 subl的平衡因子为0，subLR的平衡因子为0，parent的平衡因子为0

整体代码

#include<iostream>
using namespace std;
template<class K, class V>
class AVLTreeNode
{
	AVLTreeNode<K, V>* _left;
	AVLTreeNode<K, V>* _right;
	AVLTreeNode<K, V>* _parent;
	pair<K, V> _kv;//当前节点值
	int _bf;//平衡因子

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

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;//用于记录cur的前一个节点
		Node* cur = _root;
		while (cur)
		{
			//若插入的值比当前树的值小 插入左边
			if (cur->_kv.first > kv.first)
			{
				parent = cur;
				cur = cur->_left;
			}
			//若插入的值比当前树的值大 插入右边
			else if (cur->_kv.first < kv.first)
			{
				parent = cur;
				cur = cur->_right;
			}
			else
			{
				//若插入的值，在树中有相同的值 ，则插入失败
				return false;
			}
		}
		cur = new Node(kv);
		//再次判断parent当前节点值与插入值大小
		if (parent->_kv.first > kv.first)
		{
			parent->_left = cur;
		}
		else
		{
			parent->_right = cur;
		}
		//cur的上一个节点即为 刚才的记录cur前一个节点的parent
		cur->_parent = parent;



		//更新平衡因子
		while (parent)
		{
			//若插入节点在parent的右子树
			if (cur == parent->_right)
			{
				parent->_bf++;
			}
			//若插入节点在parent的左子树
			else
			{
				parent->_bf--;
			}


			if (parent->_bf == 1 || parent->_bf == -1)
			{
				//继续向上更新
				parent = parent->_parent;
				cur = cur->_parent;
			}
			//平衡因子为0，不需要向上更新
			else if (parent->_bf == 0)
			{
				break;
			}
			else if (parent->_bf == 2 || parent->_bf == -2)
			{
				//旋转
				//1.让这颗子树平衡 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)//双旋
				{
					RotateLR(parent);
				}

				//旋转后整颗树已经平衡了，就不需要在继续了
				break;
			}
		}

		return true;
	}


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

		parent->_right = subRL;
		if (subRL != nullptr)
		{
			subRL->_parent = parent;
		}
		Node* ppnode = parent->_parent;//记录parent的前一个节点

		subR->left = parent;
		parent->_parent = subR;

		if (ppnode == nullptr)//说明parent是根即代表整棵树
		{
			_root = subR;//subR作为新的根
			_root->_parent = nullptr;//subR的父节点指向原来的parent,所以要置nullptr
		}
		else//说明旋转的是一部分，所以要跟ppnode相连接
		{
			if (ppnode->_left == parent)//若连接在左子树上
			{
				ppnode->_left = subR;
			}
			else//若连接在右子树上
			{
				ppnode->_right = subR;
			}
			subR->_parent = ppnode;//将subR父节点置为ppnode
		}
		parent->_bf = subR->_bf = 0;//平衡因子都为0
	}

	void RoateR(Node* parent)//右单旋
	{
		Node* subL = parent->_left;
		subLR = subL->_right;
		parent->_left = subLR;
		if (subLR != nullptr)
		{
			subLR->_parent = parent;
		}
		Node* ppnode = parnet->_parent;//记录parent的父节点
		subL->_right = parent;
		parent->_parent = subL;

		if (ppnode == nullptr)//若旋转整棵树
		{
			_root = subL;
			_root->_parent = nullptr;
		}
		else//若旋转整棵树的部分子树
		{
			if (ppnode->_left == parent)
			{
				ppnode->_left = subL;
			}
			else
			{
				ppnode->_right = subL;
			}
			subL->_parent = ppnode;//使subL的父节点为ppnode
		}
		parent->_bf = subL->_bf = 0;

	}

	void RotateLR(Node* parent)//左右双旋
	{
		Node* subL = parent->_left;
		Node* subLR = subL->_right;
		int bf = subLR->_bf;//记录平衡因子，在后续单旋会置为0
		
		//先对parent的左子树进行左单旋
		RotateL(parent->_left);
		//再对当前根进行右单旋
		RotateR(parent);

		if (bf == -1)//h==2时，在b处插入节点
		{
			subL->_bf = 0;
			subLR->_bf = 0;
			parent->_bf = 1;
		}
		else if (bf == 1)//h==2时，在c处插入节点
		{
			subL ->_bf = -1;
			subLR ->_bf= 0;
			parent->_bf = 0;
		}
		else if (bf == 0)//当h==0时，60作为新增节点
		{
			subL->_bf = 0;
			subLR->_bf = 0;
			parent->_bf = 0;
		}

	}

private:
	Node* _root = nullptr;
};