?map/multimap/set/multiset的底层都按照二叉搜索树实现，但是在【C++】-- 搜索二叉树一文中已经了解到二叉搜索树的缺点在于，假如向树中插入的元素有序或者接近有序时，二叉搜索树就会退化成单支树，时间复杂度会退化成O(N)，相当于在顺序表中搜索元素，效率低下。所以map/multimap/set/multiset的底层结构对二叉搜索树做了处理，采用平衡树来实现。

2.AVL树的概念?

如何避免二叉树搜索树会退化成单支树的缺点呢？

向二叉搜索树中插入新结点后，如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整)，即可降低树的高度，从而减少平均搜索长度。为什么高度差的绝对值不超过1而不是0呢？因为如果高度差的绝对值不超过0，那么二叉树就变成满二叉树了，因此绝对值不能超过1。这就引入了平衡二叉树的概念：

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

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

?如果一棵二叉搜索树是高度平衡的，它就是AVL树。如果它有n个结点，其高度可保持在，搜索时
间复杂度O（）。

二、AVL树定义

由于要实现AVL树的增删改查，所以定义AVL树的节点，就需要定义parent，否则插入节点时，不知道要链接到树里面哪个节点下面。

1.AVL树节点定义

节点定义：

#pragma once
#include<iostream>
using namespace std;

template<class K,class V>
class AVLTreeNode
{
	AVLTreeNode<K, V>* _left;//左子树
	AVLTreeNode<K, V>* _right;//右子树
	AVLTreeNode<K, V>* _parent;//父亲

	int _bf;//平衡因子

	pair<K, V> _kv;//节点

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

};

?2.AVL树定义

template<class K,class V>
struct AVLTree
{
	typedef AVLTreeNode<K, V> Node;
public:
		//构造函数
	AVLTree()
		:_root(nullptr)
	{}

	void _Destroy(Node* root)
	{
		if (root == nullptr)
		{
			return;
		}
		_Destroy(root->_left);
		_Destroy(root->_right);

		delete root;
	}

    //重载operator[]
	V& operator[](const K& key)
	{
		pair<Node*, bool> ret = Insert(make_pair(key, V()));
		return ret.first->_kv.second;
	}

	//析构函数
	~AVLTree()
	{
		_Destroy(_root);
		_root = nullptr;
	}

private:
	Node* _root;
};

三、AVL树插入?

1.插入节点

插入节点需要先判断树是否为空：

（1）若为空，让该节点作为根节点

（2）若不为空，分3种情况：

①key比当前节点小，向左走

②key比当前节点大，向右走

③相等，插入失败

如果没找到节点，那么需要插入新节点

	bool Insert(const pair<K, V>& kv)
	{
		//1.空树
		if (_root == nullptr)
		{
			_root = new Node(kv);
			return true;
		}

		//2.非空树
		Node* parent = _root, * 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);
		if (parent->_kv.first < cur->_kv.first)
		{
			parent->_right = cur;
			cur->_parent = parent;
		}
		else
		{
			parent->_left = cur;
			cur->_parent = parent;
		}

		return true;
	}

2.控制平衡?

（1）更新平衡因子

?一个节点的平衡因子是否需要更新，取决于它的左右子树的高度是否发生变化。插入一个节点，如果它的父亲的平衡因子需要更新，那么它所在这条路径的从父亲到根的所有节点的平衡因子都需要更新。因此

①如果新增节点是父亲的左子树，那么parent->_bf--

②如果新增节点是父亲的右子树，那么parent->_bf++

更新后：?

????????a.如果parent->_bf=0，则停止更新

????????b.如果parent->_bf==1||-1，需要继续往上更新（说明以parent为根的子树高度变了，由0变成了1或-1，有可能导致parent的parent的平衡因子=2或=-2）

????????c.如果parent->_bf=2||-2已经不平衡了，那么需要旋转处理

		//控制平衡
		//1.更新平衡因子
		while (cur != root)
		{
			if (parent->_left == cur)//新节点插入到parent左孩子，parent的左子树变高了，平衡因子-1
			{
				parent->_bf--;
			}
			else
			{
				parent->_bf++;
			}

			
			if (parent->_bf == 0)
			{
				//已经平衡，停止更新
				break;
			}
			else if(parent->_bf == 1 || parent->_bf == -1)
			{
				//说明以parent为根的子树高度变了，由0变成了1或-1，有可能影响parent的parent的平衡因子，需要继续往上更新
				cur = parent;
				parent = parent->_parent;
			}
			else if (parent->_bf == 2 || parent->_bf == -2)
			{
				//已经出现了不平衡，需要旋转处理
				if (parent->_bf == -2)
				{
					if (cur->_bf == -1)
					{
						//右单旋
						RotateR(parent);
					}
				}
			}
			else
			{
				//插入新节点之前，树已经不平衡了
				assert(false);
			}
		}

（2）旋转

旋转处理有4种：右单旋、左单旋、右左单旋、左右单旋

①右单旋

将新节点插入到较高左子树的左侧，即左左-----右单旋

?插入新节点前，AVL树是平衡的，新节点插入到10的左子树，那么10的左子树增加了一层，导致以20为根的二叉树不平衡。为了让20平衡，只能让20的左子树的高度减小一层，并把10的右子树的高度增加一层。

因此，要把10的左子树往上提，把20转下来，因为20比10大，只能把20放在10的右子树，10的右子树比10大，比20小，因此只能把10的右子树放在20的左子树。再更新节点平衡因子。

抽象图：

?需要考虑的情况：

（1）10的右孩子可能存在，也可能不存在

（2）20可能是根节点，也可能是子树；如果是根节点，旋转后，要更新根节点。如果是子树，可能是左子树也可能是右子树，就把20原来的父亲的左或右指向10。

	void RotateR(Node* parent)
	{
		Node* subL = parent->_left;
		Node* subLR = nullptr;
		
		if (subL)
		{
			subLR = subL->_right;
		}
		//1.左子树的右子树变我的左子树
		parent->_left = subLR;

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

		//左子树变父亲
		subL->_right = parent;
		Node* parentParent = parent->_parent;
		parent->_parent = subL;
		

		if (parent == _root)//parent是根
		{
			_root = subL;
			_root->_parent = nullptr;
		}
		else//parent不是根，是子树
		{
			if (parentParent->_left == parent)
			{
				//parent是自己父亲的左子树,将subL作为parent父亲的左孩子
				parentParent->_left = subL;
			}
			else
			{
				//parent是自己父亲的右子树,将subL作为parent父亲的右孩子
				parentParent->_right = subL;
			}
			
			//subL的父亲就是parent的父亲
			subL->_parent = parentParent;
		}

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

具象图：

h=0的情况：

20变成10的左子树，10的左子树为空，不用考虑?

h=1的情况：

20变成10的右子树，10的右子树12变成20的左子树

h=2的情况：

?20变成10的左子树，10的右子树12变成20的左子树???????

②左单旋

?新节点插入到较高右子树的右侧，即右右-----左单旋

?插入新节点前，AVL树是平衡的，新节点插入到20的右子树，那么20的右子树增加了一层，导致以10为根的二叉树不平衡。为了让10平衡，只能让10的右子树的高度减小一层，并把20的左子树的高度增加一层。

因此，要把20的右子树往上提，把10转下来，因为10比20小，只能把10放在20的左子树，20的左子树比20小，比10大，因此只能把20的左子树放在10的右子树。再更新节点平衡因子。

抽象图：

需要考虑的情况：

（1）20的左孩子可能存在，也可能不存在

（2）10可能是根节点，也可能是子树；如果是根节点，旋转后，要更新根节点。如果是子树，可能是左子树也可能是右子树，就把10原来的父亲的左或右指向20。

	void RotateL(Node* parent)
	{
		Node* subR = parent->_right;
		Node* subRL = nullptr;
		
		if (subR)
		{
			subRL = subR->_left;
		}
			
		//1.右子树的左子树变我的右子树
		parent->_right = subRL;

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

		//2.右子树变父亲
		subR->_left = parent;
		Node* parentParent = parent->_parent;
		parent->_parent = subR;
		
		if (parent == _root)//parent是根
		{
			_root = parent;
			_root->_parent = nullptr;
		}
		else//parent不是根，是子树
		{
			if (parentParent->_left == parent)
			{
				//parent是自己父亲的左子树,将subR作为parent父亲的左孩子
				parentParent->_left = subR;
			}
			else
			{
				//parent是自己父亲的右子树,将subR作为parent父亲的右孩子
				parentParent->_right = subR;
			}

			//subR的父亲就是parent的父亲
			subR->_parent = parentParent;
		}

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

具象图：

h=0的情况：

10变成20的左子树，20的左子树为空，不考虑

h=1的情况：

10变成20的左子树，20的左子树变成10的右子树

h=2的情况：?

?10变成20的左子树，20的左子树变成10的右子树???????

?③左右双旋

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

插入新节点前，AVL树是平衡的，新节点插入到20的左子树，那么20的左子树增加了一层，导致以30为根的二叉树不平衡。为了让30平衡，只能让30的左子树的高度减小一层。

现在30左子树的高度是h+1，但是现在不能把10进行右单旋，因为要把10右单旋，那么20和30都必须处于10的右子树，这办不到。因此要分为两步：

（1）先把10左单旋

（2）再把20右单旋

void RotateLR(Node* parent)
	{
		Node* subL = parent->_left;
		Node* subLR = subL->_right;
		int bf = 0;
		
		if (subLR)
		{
			bf = subLR->_bf;
		}
		

		RotateL(parent->_left);
		RotateR(parent);

		//平衡因子调节还需要分析
		if (bf == -1)
		{
			subL->_bf = 0;
			parent->_bf = 1;
			subLR->_bf = 0;
		}
		else if (bf == 1)
		{
			parent->_bf = 0;
			subL->_bf = -1;
			subLR->_bf = 0;
		}
		else if (bf == 0)
		{
			parent->_bf = 0;
			subL->_bf = 0;
			subLR->_bf = 0;
		}
		else
		{
			assert(false);
		}
	}

④右左双旋

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

插入新节点前，AVL树是平衡的，新节点插入到30的右子树，那么30的右子树增加了一层，导致以10为根的二叉树不平衡。为了让10平衡，只能让10的右子树的高度减小一层。?

现在10右子树的高度是h+1，但是现在不能把30进行左单旋，因为要把30左单旋，那么10和20都必须处于30的左子树，这办不到。因此要分为两步：

（1）先把20右单旋

（2）再把10左单旋

	void RotateRL(Node* parent)
	{
		Node* subR = parent->_right;
		Node* subRL = subR->_left;
		int bf = 0;

		if (subRL)
		{
			bf = subRL->_bf;
		}
		

		//先右旋再左旋
		RotateR(parent->_right);
		RotateL(parent);

		//平衡因子调节还需要具体分析
		if (bf == 1)
		{
			parent->_bf = -1;
			subR->_bf = 0;			
			subRL->_bf = 0;
		}
		else if (bf == -1)
		{
			parent->_bf = 0;
			subR->_bf = 1;
			subRL->_bf = 0;
		}
		else if (bf == 0)
		{
			parent->_bf = 0;
			subR->_bf = 0;
			subRL->_bf = 0;
		}
		else
		{
			assert(false);
		}
	}

四、AVL树查找

查找比较简单：

（1）如果key比当前节点大，那就继续向右查找；

（2）如果key比当前节点小，那就继续向左查找；

（3）如果key恰好等于当前节点，找到了

	Node* Find(const K& key)
	{
		Node* cur = _root;
		while (cur)
		{
			if (cur.first < key)//比当前节点大，向右查找
			{
				cur = cur->_right;
			}
			else if (cur.first > key)//比当前节点小，向左查找
			{
				cur = cur->_left;
			}
			else//等于当前节点，找到了
			{
				return cur;
			}
		}
		return nullptr;
	}

五、AVL树高度?

计算树高度肯定要递归计算：

（1）计算左右子树的高度

（2）谁的高度大，那AVL树的高度就为较高子树的高度+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;
	}

?六、判断是否为AVL树

检查树是否是AVL树：

（1）获取左右子树高度

（2）根据左右子树高度计算平衡因子

（3）当平衡因子<=2 || -2时就是平衡的

	bool _IsBanlance(Node* root)
	{
		if (root == nullptr)
		{
			return true;
		}

		int leftHeight = Height(root->_left);
		int rightHeight = Height(root->_right);

		//检查平衡因子是否正确
		if (rightHeight - leftHeight != root->_bf)
		{
			cout << "平衡因子异常：" << root->_kv.first << endl;
			return false;
		}

		return abs(rightHeight - leftHeight) < 2
			&& _IsBanlance(root->_left)
			&& _IsBanlance(root->_right);
	}

	//判断是否是AVL树
	bool IsAVLTree()
	{
		return _IsBanlance(_root);
	}

七、AVL树遍历

遍历也很简单：递归遍历左子树和右子树即可?

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

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

	void InOrder()
	{
		_InOrder(_root);
	}