AVL 树

二叉搜索树虽可以缩短查找的效率，但如果数据有序或接近有序二叉搜索树将退化为单支树，查找元素相当于在顺序表中搜索元素，效率低下。
例如：

因此，两位俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis在1962年
发明了一种解决上述问题的方法：当向二叉搜索树中插入新结点后，如果能保证每个结点的左右子树高度之差的绝对值不超过1 (需要对树中的结点进行调整)，即可降低树的高度，从而减少平均搜索长度。一棵AVL树或者是空树，或者是具有以下性质的二叉搜索树：它的左右子树都是AVL树左右子树高度之差(简称平衡因子)的绝对值不超过1(-1/0/1)如果一棵二叉搜索树是高度平衡的，它就是AVL树。如果它有n个结点，其高度可保持在log2N ，搜索时间复杂度O( log2N)

---

节点定义

在 二叉搜索树的基础上增加了 平衡因子 这个属性，不能小看这个东西，它立刻使二叉树搜索树的插入变的复杂起来…

template<class T>
struct AVLTreeNode{
	AVLTreeNode(const T& data)
		: _pLeft(nullptr)
		, _pRight(nullptr)
		, _pParent(nullptr)
		, _data(data)
		, _bf(0)//平衡因子，初始值为0，默认已经平衡
	{}
	AVLTreeNode<T>* _pLeft; // 该节点的左孩子
	AVLTreeNode<T>* _pRight; // 该节点的右孩子
	AVLTreeNode<T>* _pParent; // 该节点的双亲
	T _data;
	int _bf; // 该节点的平衡因子
};

AVL 插入节点 和二叉搜索树插入的思路、代码一样
如果插得的是左边则平衡因子减一，右边则加1

如果插入节点后，双亲的平衡因子不满足 AVL 树的性质，那就需要进行旋转，调整为 AVL 树的性质。

旋转一共分为 4 种 ‘花样’

1. 右单旋

对于这个案列，45节点 的存在与否都不重要，如果40 没有右子树，那么它依然要进行单旋。上面的案列 50 没有双亲节点，如果有父节点，那该怎么调整呢？

就拿上列来说，我们假设 50 还有双亲节点

	void RotateRight1(Node* pParent){
		// pParent 代表的是 50 节点
		// pSubL: pParent的左孩子 40
		// pSubLR: pParent左孩子的右孩子 45 
		Node* pSubL = pParent->_pLeft;
		Node* pSubLR = pSubL->_pRight;
		// 旋转完成之后，40 的右孩子作为双亲的左孩子
		pParent->_pLeft = pSubLR;
		
		// 如果 50 的左子树的右孩子存在，更新亲双亲
		// 使 45 的双亲指向 50
		if (pSubLR) {
			pSubLR->_pParent = pParent;
		}
		
		// 50 作为 40 的右孩子
		pSubL->_pRight = pParent;
		// 因为 50 可能是棵子树，因此在更新其双亲前必须先保存 50 的双亲
		Node* pPParent = pParent->_pParent;
		// 更新 50 的双亲
		pParent->_pParent = pSubL;
		// 更新 40 的双亲
		pSubL->_pParent = pPParent;
		// 如果 50 是根节点，根新指向根节点的指针
		if (nullptr == pPParent){
			pRoot = pSubL;
			pSubL->_pParent = nullptr;
		}
		else{
			// 如果 50 是子树，可能是其双亲的左子树，也可能是右子树
			if (pPParent->_pLeft == pParent) {
				pPParent->_pLeft = pSubL;
			}
			else {
				pPParent->_pRight = pSubL;
			}
		}
		// 根据调整后的结构更新部分节点的平衡因子
		pParent->_bf = pSubL->_bf = 0;
	}

2. 左单旋 和 这个正好相反

3. 双旋 — 先左单旋 再 右单旋

4. 双旋 — 先右单旋 再 左单旋

总结：

旋转完成后，原 pParent 为根的子树个高度降低，已经平衡，不需要再向上更新

AVL树的验证

AVL树是在二叉搜索树的基础上加入了平衡性的限制，因此要验证AVL树，可以分两步：

1. 验证其为二叉搜索树，如果中序遍历可得到一个有序的序列，就说明为二叉搜索树
2. 验证其为平衡树，每个节点子树高度差的绝对值不超过1(注意节点中如果没有平衡因子)节点的平衡因子是否计算正确

	//计算深度
	int _Height(Node* pRoot){
		if (root == NULL){
			return 0;
		}
		if (root->left == NULL && root->right == NULL){
			return 1;
		}
		int left = GetHeight(root->left);
		int right = GetHeight(root->right);
		if (left > right){
			return left + 1;
		}else{
			return right + 1;
		}
	}

	//判断是否平衡
	bool _IsBalanceTree(Node* pRoot){
		// 空树也是AVL树
		if (nullptr == pRoot) {
			return true;
		}
		// 计算pRoot节点的平衡因子：即pRoot左右子树的高度差
		int leftHeight = _Height(pRoot->_pLeft);
		int rightHeight = _Height(pRoot->_pRight);
		int diff = rightHeight - leftHeight;
		// 如果计算出的平衡因子与pRoot的平衡因子不相等，或者
		// pRoot平衡因子的绝对值超过1，则一定不是AVL树
		if (diff != pRoot->_bf || (diff > 1 || diff < -1))
			return false;
		// pRoot的左和右如果都是AVL树，则该树一定是AVL树
		return _IsBalanceTree(pRoot->_pLeft) 
			&& _IsBalanceTree(pRoot->_pRight);
	}

AVL 树的性能

AVL树是一棵绝对平衡的二叉搜索树，其要求每个节点的左右子树高度差的绝对值都不超过1，这样可以保证查询时高效的时间复杂度，即 。但是如果要对 AVL 树做一些结构修改的操作，性能非常低下，比如：插入时要维护其绝对平衡，旋转的次数比较多，更差的是在删除时，有可能一直要让旋转持续到根的位置。因此：如果需要一种查询高效且有序的数据结构，而且数据的个数为静态的(即不会改变)，可以考虑AVL树，但一个结构经常修改，就不太适合。