template<class T,class K>
struct AVLTreeNode
{
	AVLTreeNode<T, K>* _left;
	AVLTreeNode<T, K>* _right;
	AVLTreeNode<T, K>* _parent;
	pair<const K, V> _kv;
	int _bf; // Balance factor
};

因为K是不能被修改的，所以我们传一个const

三、AVL树的插入

AVL树的插入与二叉搜索树类似，首先要找到插入位置，然后是调整平衡因子，判断是否需要旋转，最后是旋转。旋转主要分为四种情况，左单旋，右单旋，左右双旋，右左双旋

	bool insert(const pair<K, V>& kv)
	{
		if (_root == nullptr)
		{
			_root = new Node(kv);
			return true;
		}
		Node* cur = _root;
		Node* parent = nullptr;
		while (cur)
		{
			if (cur->_kv.first < kv.first)
			{
				parent = cur;
				cur = cur->_right;
			}
			else if (cur->_kv.first > kv.first)
			{
				parent = cur;
				cur = cur->_left;
			}
			else
			{
				return false;
			}
		}

		//找到插入位置
		cur = new Node(kv);
		if (parent->_kv.first < kv.first)
		{
			parent->_right = cur;
		}
		else
		{
			parent->_left = cur;
		}
        
        cur->_parent = parent;
		//调整平衡因子+旋转
	}

1、平衡因子更新规则

新增在右，parent->_bf++, 新增在左，parent->_bf--

更新后parent->_bf == 1 or -1，说明在插入之前parent->_bf == 0，说明左右子树高度相同，插入之后左右子树高度不同，需要往上更新平衡因子

更新后，parent->_bf == 0，说明之前parent->_bf == 1? or -1 说明左右子树不一边高，插入后左右子树高度相同，说明插入到了左右子树中矮的那一边，不需要往上更新

更新后parent->_bf == 2 or -2 说明parent插入前的平衡因子是1? or? -1，已经在平衡的临界值，插入之后打破平衡，需要进行旋转

更新之后parent->_bf > 2 or < -2 说明，在插入之前就不是AVL树，需要检查之前的操作

		//调整平衡因子+旋转
		//调整最多是调整到根，根是没有父亲的
		while (parent)
		{
			if (cur == parent->_left)
			{
				parent->_bf--;
			}
			else
			{
				parent->_bf++;
			}

			if (parent->_bf == 0)
			{
				break;
			}
			else if(abs(parent->_bf) == 1)
			{
				//继续向上调整
				parent = parent->_parent;
				cur = cur->_parent;
			}
			else if (abs(parent->_bf) == 2)
			{
				//开始旋转
			}
			else
			{
				//出错了，按照常理不会出现这种情况
				assert(false);
			}
            break;
		}
		return true;

2、左单旋

假如有这样的一棵树，子树a,b,c都是高度为h的AVL树，现在我们要在c子树插入一个节点

?插入之后更新平衡因子，因为是插入在60的右边，导致60的平衡因子变成1，30的平衡因子变成2，右边高了，所以需要我们进行左旋

具体过程：将cur的左子树给parent的右子树，parent作为cur的左子树

最后是更新平衡因子，因为parent的左右子树高度相同所以parent->_bf == 0

cur的左右子树高度相同，所以也是0

	void RotateL(Node* parent)
	{
		Node* subR = parent->_right;
		Node* subRL = subR->_left;
		parent->_right = subRL;
		if (subRL)
		{
			subRL->_parent = parent;
		}
		Node* ppNode = parent->_parent;
		subR->_left = parent;
		parent->_parent = subR;
		if (_root == parent)
		{
			_root = subR;
			subR->_parent = nullptr;
		}
		else
		{
			if (ppNode->_left == parent)
			{
				ppNode->_left = subR;
			}
			else
			{
				ppNode->_right = subR;
			}
			subR->_parent = ppNode;
		}
		subR->_bf = parent->_bf = 0;
	}

3、右单旋

假如有这样的一棵树，子树a,b,c都是高度为h的AVL树，现在我们要在a子树插入一个节点

a这棵树的高度是h+1,更新平衡因子

发现parent->_bf == -2, cur->_bf == -1，这时候左边高，需要我们将左子树向右边旋转

具体的旋转过程是，先将cur的右子树给parent的左边，然后parent作为cur的右子树

最后是要看平衡因子的更新，对于parent(60这个节点)，它的左右子树高度相同，平衡因子是0

cur的左子树高度等于右子树高度，平衡因子是0?

void RotateR(Node* parent)
	{
		Node* subL = parent->_left;
		Node* subLR = subL->_right;
		parent->_left = subLR;
		if (subLR)
		{
			subLR->_parent = parent;
		}
		Node* ppNode = parent->_parent;//记录parent的parent，旋转完成之后链接
		subL->_right = parent;
		parent->_parent = subL;
		if (_root == parent)
		{
			_root = subL;
			subL->_parent = nullptr;
		}
		else
		{
			if (ppNode->_left == parent)
			{
				ppNode->_left = subL;
			}
			else
			{
				ppNode->_right = subL;
			}
			subL->_parent = ppNode;
		}
		//更新bf
		subL->_bf = parent->_bf = 0;
	}

4、左右双旋

接下来是左右双旋，先进行左旋，再进行右旋

?我们要在b的下面插入一个新节点

单看30为根的这棵树，它的右子树高于左子树，所以进行左旋

左旋之后发现左边高，再进行右旋(以60为轴点)

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

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

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

5、右左双旋

再60的右边插入一个节点

这时以90为轴进行右旋

接下来以30为轴进行左旋

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

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

四、AVL树的验证

我们要想验证一棵树是否是AVL树，不能够通过观察它的平衡因子，因为旋转之后的平衡因子是我们手动更新的，就好比我既是裁判又是球员，所以这种方式不可靠。

我们选择判断左右子树高度差是否符合条件来判断 + 中序遍历 + 平衡因子

这三种方式叠加来判断

	void InOrder()
	{
		_InOrder(_root);
	}

	bool IsBalance()
	{
		return _IsBalance(_root);
	}
	
    void _InOrder(Node* root)
	{
		if (root == nullptr)
		{
			return;
		}

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

	bool _IsBalance(Node* root)
	{
		if (root == nullptr)
		{
			return true;
		}
		int leftDepth = GetDepths(root->_left);
		int rightDepth = GetDepths(root->_right);
		int diff = leftDepth - rightDepth;
		if (diff != root->_bf)
		{
			cout << "平衡因子异常" << endl;
			return false;
		}
		return abs(diff) < 2 
			&& _IsBalance(root->_left) 
			&& _IsBalance(root->_right);
	}

	int GetDepths(Node* root)
	{
		if (root == nullptr)
		{
			return 0;
		}
		return max(GetDepths(root->_left), GetDepths(root->_right)) + 1;
	}

我们先拿常规测试用例来测试{16, 3, 7, 11, 9, 26, 18, 14, 15}

接下来是特殊场景{4, 2, 6, 1, 3, 5, 15, 7, 16,?14}

结果也是没有问题的

最后是拿一组随机值来测试

void test_AVLTree()
{
	srand(time(0));
	AVLTree<int, int> t;
	//{16, 3, 7, 11, 9, 26, 18, 14, 15}
	//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 it : a)
	{
		t.insert(make_pair(it, it));
	}*/
	size_t N = 10000;
	for (size_t i = 0; i < N; i++)
	{
		int x = rand();
		t.insert(make_pair(x, x));
	}
	t.InOrder();
	cout << t.IsBalance() << endl;
}