平衡二叉树（Balanced Binary Tree）是二叉查找树的一个进化体，也是第一个引入平衡概念的二叉树。1962年，G.M. Adelson-Velsky 和 E.M. Landis发明了这棵树，所以它又叫AVL树。

平衡二叉树要求对于每一个节点来说，它的左右子树的高度之差不能超过1，如果插入或者删除一个节点使得高度之差大于1，就要进行节点之间的旋转，将二叉树重新维持在一个平衡状态。这个方案很好的解决了二叉查找树退化成链表的问题，把插入，查找，删除的时间复杂度最好情况和最坏情况都维持在O(logN)。

但是频繁旋转会使插入和删除牺牲掉O(logN)左右的时间，不过相对二叉查找树来说，时间上稳定了很多。

平衡二叉树实现的大部分过程和二叉查找树是一样的（学平衡二叉树之前一定要会二叉查找树），区别就在于插入和删除之后要写一个旋转算法去维持平衡，维持平衡需要借助一个节点高度的属性。

讲解视频：链接：https://pan.baidu.com/s/1w5hlEwgbG7qFF7ZJr52QmA 提取码：mhmw

#pragma once

//二叉树节点
template<class T>
struct BinaryNode
{
	T mValue;
	int mHeight; //树的高度
	BinaryNode<T>* pLchild; //指向左子树节点
	BinaryNode<T>* pRchild; //指向右子树节点
	BinaryNode<T>* pParent; //指向父节点
};


template<class T>
class BinarySearchTree
{
public:
	// 构造函数
	BinarySearchTree();
	// 析构函数
	~BinarySearchTree();
	// 拷贝构造函数
	BinarySearchTree(const BinarySearchTree<T>& bst);

	//插入
	void Insert(const T& val);
	//查找
	BinaryNode<T>* SearchNode(const T& val);

	// 中序遍历
	template<class _Func>
	void Foreach(_Func func);
	// 辅助中序遍历
	template<class _Func>
	void MyForeach(BinaryNode<T>* root, _Func func);

	//释放二叉树
	void MyFree(BinaryNode<T>* root)l;
	//拷贝二叉树
	BinaryNode<T>* MyCopy(BinaryNode<T>* root, BinaryNode<T>* parent = NULL);

	//删除算法
	void Remove(const T& val);
	//第一种情况，如果删除的结点是叶子节点
	void RemoveNoChildNode(BinaryNode<T>* delNode);
	//第二种情况，如果删除的结点只有一个孩子
	void RemoveSingleChildNode(BinaryNode<T>* delNode);
	//第三种情况，如果删除的结点有两个孩子
	void RemoveDoubleChildNode(BinaryNode<T>* delNode);

	//获得最大值结点
	BinaryNode<T>* GetMaxNode(BinaryNode<T>* root);
	//获得最小值结点
	BinaryNode<T>* GetMinNode(BinaryNode<T>* root);
	/* 平衡二叉树接口 */
	//更新树的高度
	int UpdateTreeHeight(BinaryNode<T>* root);
	//获得某个子树的高度
	int GetTreeHeight(BinaryNode<T>* node);
	//求某个子树的平衡因子
	int GetBalanceFactor(BinaryNode<T>* node);
	// 右旋
	void RightRotate(BinaryNode<T>* node);
	// 左旋
	void leftRotate(BinaryNode<T>* node);
	// 调整树的平衡（subRoot）
	void AdjustTreeBalance(BinaryNode<T>* subRoot);

public:
	BinaryNode<T>* pRoot; //永远指向二叉排序树的根节点
	int mSize;
};

1. 初始化和销毁

// 构造函数
template<class T>
BinarySearchTree<T>::BinarySearchTree()
{
	pRoot = NULL;
	mSize = 0;
}

// 析构函数
template<class T>
BinarySearchTree<T>::~BinarySearchTree()
{
	MyFree(pRoot);
}

// 拷贝构造
template<class T>
BinarySearchTree<T>::BinarySearchTree(const BinarySearchTree<T>& bst)
{
	mSize = bst.mSize;
	pRoot = MyCopy(bst.pRoot, NULL);
}

//释放二叉树
template<class T>
void BinarySearchTree<T>::MyFree(BinaryNode<T>* root)
{
	if (NULL == root)
	{
		return;
	}

	//释放左子树内存
	MyFree(root->pLchild);
	//释放右子树内存
	MyFree(root->pRchild);
	//释放当前结点的内存
	delete root;
}

//拷贝二叉树
template<class T>
BinaryNode<T>* BinarySearchTree<T>::MyCopy(BinaryNode<T>* root, BinaryNode<T>* parent = NULL)
{
	if (NULL == root)
	{
		return NULL;
	}

	//拷贝当前结点
	BinaryNode<T>* newnode = new BinaryNode<T>;
	newnode->mValue = root->mValue;
	newnode->pParent = parent;

	newnode->pLchild = NULL;
	newnode->pRchild = NULL;

	//拷贝左子树
	BinaryNode<T>* pLeft = MyCopy(root->pLchild, newnode);
	//拷贝右子树
	BinaryNode<T>* pRight = MyCopy(root->pRchild, newnode);

	//更新新节点的左右指针指向
	newnode->pLchild = pLeft;
	newnode->pRchild = pRight;

	return newnode;
}

2. 遍历函数

template<class T> template<class _Func>
void BinarySearchTree<T>::Foreach(_Func func)
{
	MyForeach(pRoot, func);
}

//辅助中序遍历
template<class T> template<class _Func>
void BinarySearchTree<T>::MyForeach(BinaryNode<T>* root, _Func func)
{
	if (NULL == root)
	{
		return;
	}
	MyForeach(root->pLchild, func);
	func(root->mValue);
	MyForeach(root->pRchild, func);
}

3. 查找函数

template<class T>
BinaryNode<T>* BinarySearchTree<T>::SearchNode(const T& val)
{
	//辅助指针变量
	BinaryNode<T>* pCurrent = pRoot;
	while (pCurrent != NULL)
	{
		if (val < pCurrent->mValue)
		{
			pCurrent = pCurrent->pLchild;
		}
		else if (!(val < pCurrent->mValue) && !(pCurrent->mValue < val))
		{
			return pCurrent;
		}
		else
		{
			pCurrent = pCurrent->pRchild;
		}
	}

	return NULL;
}

4. 树高度函数

//获得子树的高度
template<class T>
int BinarySearchTree<T>::GetTreeHeight(BinaryNode<T>* node)
{
	if (NULL == node)
	{
		return 0;
	}

	return node->mHeight;
}

//求某个子树的平衡因子
template<class T>
int BinarySearchTree<T>::GetBalanceFactor(BinaryNode<T>* node)
{
	if (NULL == node)
	{
		return 0;
	}

	return GetTreeHeight(node->pLchild) - GetTreeHeight(node->pRchild);
}

5. 树旋转操作

//树的旋转-向右旋转
template<class T>
void BinarySearchTree<T>::RightRotate(BinaryNode<T>* node)
{

	if (NULL == node)
	{
		return;
	}

	//缓存下当前子树的根节点的父节点
	BinaryNode<T>* pParent = node->pParent;
	//缓存下当前子树的根节点的左子树
	BinaryNode<T>* pLeftNode = node->pLchild;

	node->pLchild = pLeftNode->pRchild;
	if (pLeftNode->pRchild != NULL)
	{
		pLeftNode->pRchild->pParent = node;
	}


	pLeftNode->pRchild = node;
	node->pParent = pLeftNode;

	//备注：设置父节点
	pLeftNode->pParent = pParent;

	//父节点为NULL
	if (pParent == NULL)
	{
		pRoot = pLeftNode;
	}
	else
	{
		if (pParent->pLchild == node)
		{
			pParent->pLchild = pLeftNode;
		}
		else
		{
			pParent->pRchild = pLeftNode;
		}
	}

}


//左旋
template<class T>
void BinarySearchTree<T>::leftRotate(BinaryNode<T>* node)
{

	if (NULL == node)
	{
		return;
	}

	//缓存下父节点
	BinaryNode<T>* pParent = node->pParent;
	//缓存下右子树
	BinaryNode<T>* pRight = node->pRchild;

	node->pRchild = pRight->pLchild;
	if (pRight->pLchild != NULL)
	{
		pRight->pLchild->pParent = node;
	}


	pRight->pLchild = node;
	node->pParent = pRight;

	//备注：设置父节点
	pRight->pParent = pParent;

	if (pParent == NULL)
	{
		pRoot = pRight;
	}
	else
	{
		if (pParent->pLchild == node)
		{
			pParent->pLchild = pRight;
		}
		else
		{
			pParent->pRchild = pRight;
		}
	}

}

//调整树的平衡（subRoot）
template<class T>
void BinarySearchTree<T>::AdjustTreeBalance(BinaryNode<T>* subRoot)
{
	if (NULL == subRoot)
	{
		return;
	}

	//找到最小不平衡子树
	BinaryNode<T>* pBack = subRoot;
	//当前结点的平衡因子
	int factor = 0;
	while (pBack != NULL)
	{
		//计算当前结点的平衡因子
		factor = GetBalanceFactor(pBack);
		if (abs(factor) > 1)
		{
			break;
		}

		pBack = pBack->pParent;
	}


	if (pBack == NULL)
	{
		//此时树不需要调整
		return;
	}

	if (factor > 1)
	{
		//右旋
		if (GetBalanceFactor(pBack->pLchild) > 0)
		{
			//进行一次向右旋转
			RightRotate(pBack);
		}
		else
		{
			//先把pBack->pLchild左旋一次
			leftRotate(pBack->pLchild);
			//再把pBack整体向右旋转一次
			RightRotate(pBack);
		}
	}
	else
	{
		//左旋
		if (GetBalanceFactor(pBack->pRchild) < 0)
		{
			//直接向左旋转一次
			leftRotate(pBack);
		}
		else
		{
			//先把pBack->pRcild向右旋转一次
			RightRotate(pBack->pRchild);
			//然后再把pBack整体向左旋转一次
			leftRotate(pBack);
		}
	}
}

6. 插入函数

//插入
template<class T>
void BinarySearchTree<T>::Insert(const T& val)
{
	if (SearchNode(val))
	{
		cout << "节点存在，拒绝插入!" << endl;
	}

	//指向插入位置的父节点
	BinaryNode<T>* pInsertNode = NULL;
	//指向当前结点
	BinaryNode<T>* pCurrent = pRoot;

	while (pCurrent != NULL)
	{
		pInsertNode = pCurrent;

		if (val < pCurrent->mValue)
		{
			pCurrent = pCurrent->pLchild;
		}
		else
		{
			pCurrent = pCurrent->pRchild;
		}
	}

	//创建新节点
	BinaryNode<T>* newnode = new BinaryNode<T>;
	newnode->mValue = val;
	newnode->pLchild = NULL;
	newnode->pRchild = NULL;
	newnode->pParent = pInsertNode;

	//判断pInsertNode是否是NULL，如果为NULL，说明当前树是一个空树
	if (pInsertNode == NULL)
	{
		pRoot = newnode;
	}
	else
	{
		if (val < pInsertNode->mValue)
		{
			pInsertNode->pLchild = newnode;
		}
		else
		{
			pInsertNode->pRchild = newnode;
		}
	}

	++mSize;

	//更新树的高度
	UpdateTreeHeight(pRoot);
	//调整树的平衡
	AdjustTreeBalance(newnode->pParent);
}

7. 删除函数

//删除算法
template<class T>
void BinarySearchTree<T>::Remove(const T& val)
{
	BinaryNode<T>* pDelNode = SearchNode(val);

	if (pDelNode == NULL)
	{
		cout << "删除的结点不存在!" << endl;
		return;
	}

	//第一种情况，删除节点是叶子节点
	if (pDelNode->pLchild == NULL && pDelNode->pRchild == NULL)
	{
		RemoveNoChildNode(pDelNode);
	}
	//第三种情况，删除节点有两个孩子
	else if (pDelNode->pLchild != NULL && pDelNode->pRchild != NULL)
	{
		RemoveDoubleChildNode(pDelNode);
	}
	//第二种情况
	else
	{
		RemoveSingleChildNode(pDelNode);
	}

	//释放删除节点的内存
	delete pDelNode;
	pDelNode = NULL;
	--mSize;

}

//第一种情况，如果删除的结点是叶子节点
template<class T>
void BinarySearchTree<T>::RemoveNoChildNode(BinaryNode<T>* delNode)
{
	BinaryNode<T>* pDelNode = delNode;

	if (NULL == pDelNode)
	{
		return;
	}

	//判断删除的结点是否是根节点
	if (pDelNode == pRoot)
	{
		pRoot = NULL;
	}
	else
	{
		if (pDelNode->pParent->pLchild == pDelNode)
		{
			pDelNode->pParent->pLchild = NULL;
		}
		else
		{
			pDelNode->pParent->pRchild = NULL;
		}
	}
}

//第二种情况，如果删除的结点只有一个孩子
template<class T>
void BinarySearchTree<T>::RemoveSingleChildNode(BinaryNode<T>* delNode)
{
	BinaryNode<T>* pDelNode = delNode;

	if (NULL == pDelNode)
	{
		return;
	}

	if (pRoot == pDelNode)
	{
		//拿到删除节点的子节点
		BinaryNode<T>* pChild = (pRoot->pLchild == NULL ? pRoot->pRchild : pRoot->pLchild);
		//设置子节点的父节点为NULL
		pChild->pParent = NULL;
		//pRoot指向子节点
		pRoot = pChild;

	}
	else
	{
		BinaryNode<T>* pChild = (pDelNode->pLchild == NULL ? pDelNode->pRchild : pDelNode->pLchild);

		//更新pChild的父节点
		pChild->pParent = pDelNode->pParent;

		if (pDelNode->pParent->pLchild == pDelNode)
		{
			pDelNode->pParent->pLchild = pChild;
		}
		else
		{
			pDelNode->pParent->pRchild = pChild;
		}

	}

}
//第三种情况，如果删除的结点有两个孩子
template<class T>
void BinarySearchTree<T>::RemoveDoubleChildNode(BinaryNode<T>* delNode)
{
	BinaryNode<T>* pDelNode = delNode;

	if (NULL == pDelNode)
	{
		return;
	}

	//删除的结点是根节点的情况
	//pDelNode左子树最大值的结点，或者右子树中最小值的结点

	//获得删除节点左子树中最大的结点
	BinaryNode<T>* pLeftMaxNode = GetMaxNode(pDelNode->pLchild);
	if (pDelNode == pRoot)
	{

		if (pLeftMaxNode == pDelNode->pLchild)
		{
			pLeftMaxNode->pRchild = pRoot->pRchild;

		}
		else
		{
			//最大值的结点的父节点指向最大值结点的左子树
			pLeftMaxNode->pParent->pRchild = pLeftMaxNode->pLchild;
			if (pLeftMaxNode->pLchild != NULL)
			{
				pLeftMaxNode->pLchild->pParent = pLeftMaxNode->pParent;
			}
			//让最大值结点左右指针指向根节点的左右子树
			pLeftMaxNode->pLchild = pRoot->pLchild;
			pLeftMaxNode->pRchild = pRoot->pRchild;
		}

		pRoot = pLeftMaxNode;
	}
	else
	{

		if (pLeftMaxNode == pDelNode->pLchild)
		{
			pLeftMaxNode->pRchild = pDelNode->pRchild;
			//更新待删除结点的右子树的父节点
			pDelNode->pRchild->pParent = pLeftMaxNode;

			if (pDelNode->pParent->pLchild == pDelNode)
			{
				pDelNode->pParent->pLchild = pLeftMaxNode;
			}
			else
			{
				pDelNode->pParent->pRchild = pLeftMaxNode;
			}

		}
		else
		{
			pLeftMaxNode->pParent->pRchild = pLeftMaxNode->pLchild;
			if (pLeftMaxNode->pLchild != NULL)
			{
				pLeftMaxNode->pLchild->pParent = pLeftMaxNode->pParent;
			}

			pLeftMaxNode->pLchild = pDelNode->pLchild;
			pLeftMaxNode->pRchild = pDelNode->pRchild;

			if (pDelNode->pParent->pLchild == pDelNode)
			{
				pDelNode->pParent->pLchild = pLeftMaxNode;
			}
			else
			{
				pDelNode->pParent->pRchild = pLeftMaxNode;
			}
		}

	}
}