C++ - AVL平衡二叉树

struct AVLTreeNode
{
	AVLTreeNode(const T& data = T())
		: _pLeft(nullptr)
		, _pRight(nullptr)
		, _pParent(nullptr)
		, _data(data)
		, _bf(0)
	{}

	AVLTreeNode<T>* _pLeft;
	AVLTreeNode<T>* _pRight;
	AVLTreeNode<T>* _pParent;
	T _data;
	int _bf;   // 节点的平衡因子
};


// AVL: 二叉搜索树 + 平衡因子的限制
template<class T>
class AVLTree
{
	typedef AVLTreeNode<T> Node;
public:
    //功能...
    //我会写删除的，就在本篇一起写了
private:
	Node* _pRoot;
};

	bool Insert(const T& data){
		if(_pRoot == nullptr)
		{
			_pRoot = new Node(data);
			return true;
		}

		Node* parent = nullptr;
		Node* cur = _pRoot;

		while (cur)
		{
			if (data > cur->_data)
			{
				parent = cur;
				cur = cur->_pRight;
			}
			else if (data < cur->_data)
			{
				parent = cur;
				cur = cur->_pLeft;
			}
			else//不支持相同 
			{
				return false;
			}
		}

		cur = new Node(data);
		if (parent->_pLeft == cur)
			parent->_pLeft = cur;
		else
			parent->_pRight = cur;
		cur->_pParent = parent;

		//这里就插进去了 然后更新平衡因子
		while (parent)
		{
			if (parent->_pLeft == cur)
				parent->_bf--;
			else
				parent->_bf++;

			if (parent->_bf == 0)
			{
				break;
			}
			else if (parent->_bf == 1 || parent->_bf == -1)
			{
				//向上更新！
				cur = parent;
				parent = parent->_pParent;
			}
			else if (parent->_bf == 2 || parent->_bf == -2)
			{
				//旋转 分情况了
				break;
			}
			else
			{
				assert(false);
			}
		}
		return true;
	}

	AVLTree<pair<int, int>> A;
	A.Insert({ 8,1 });A.Insert({ 3,1 });A.Insert({ 10,1 });A.Insert({ 1,1 });A.Insert({ 6,1 });A.Insert({ 14,1 });

	void RotateR(Node* pParent){
		//我pParent是祖宗！
		Node* subL = pParent->_pLeft;//找到父亲
		Node* subLR = subL->_pRight;//找到右孩子
		
		//祖宗的左节点指向父亲的右节点
		pParent->_pLeft = subLR;//换孩子
		if (subLR)
			subLR->_pParent = pParent;//孩子不为空给孩子换个爹

		Node* parentParent = pParent->_pParent;

		subL->_pRight = pParent;//父亲的右节点指向祖宗
		pParent->_pParent = subL;//祖宗换个爹

		//给祖宗的爹换节点
		if (parentParent == nullptr)//这里要考虑是否是根节点 换根
		{
			_pRoot = subL;
			subL->_pParent = parentParent;//空爹也是爹
		}
		else
		{
			if (pParent == pParent->_pLeft)//原来左，还是左
				parentParent->_pLeft = subL;
			else
				parentParent->_pRight = subL;

			subL->_pParent = parentParent;//给爹换个爹
		}
		//左倾旋转完后更新平衡因子 都为0 
		pParent->_bf = subL->_bf = 0;
	}

	void RotateL(Node* pParent){
		//我pParent是祖宗！ X标记为更改处
		Node* subR = pParent->_pRight;//找到父亲 X
		Node* subRL = subR->_pLeft;//找到左边孩子 X
		//
		祖宗的右节点指向父亲的左节点
		pParent->_pRight = subRL;//换孩子 X
		if (subRL != nullptr)
			subRL->_pParent = pParent;//孩子不为空给孩子换个爹

		Node* parentParent = pParent->_pParent;

		subR->_pLeft = pParent;//父亲的右节点指向祖宗X
		pParent->_pParent = subR;//祖宗换个爹X

		//给祖宗的爹换节点
		if (parentParent == nullptr)//这里要考虑是否是根节点 换根
		{
			_pRoot = subR;
			subR->_pParent = parentParent;//空爹也是爹X
		}
		else
		{
			if (pParent == parentParent->_pLeft)//原来左，还是左X
				parentParent->_pLeft = subR;
			else
				parentParent->_pRight = subR;

			subR->_pParent = parentParent;//给爹换个爹
		}
		//左倾旋转完后更新平衡因子 都为0 
		pParent->_bf = subR->_bf = 0;
	}

	void RotateLR(Node* pParent){ //爷爷变右父亲了
		Node* subL = pParent->_pLeft;//记住原来的父亲节点 位置不变还是父亲
		Node* subLR = subL->_pRight;//记住原来的父亲节点的有右边的孩子节点  孙子变爷爷了
		int bf = subLR->_bf;//这里用于分情况记录平衡因子
		//先以父亲节点为祖宗左旋
		RotateL(pParent->_pLeft);
		//以祖宗节点右旋
		RotateR(pParent);

		//更新平衡因子
		if (bf == 0)
		{
			subL->_bf = 0;
			subLR->_bf = 0;
			pParent->_bf = 0;
		}
		else if (bf == -1)
		{
			subL->_bf = 0;
			subLR->_bf = 0;
			pParent->_bf = 1;
		}
		else if (bf == 1)
		{
			subL->_bf = -1;
			subLR->_bf = 0;
			pParent->_bf = 0;
		}
		else
		{
			assert(false);
		}
	}

	void RotateRL(Node* pParent){//爷爷变右父亲X
		Node* subR = pParent->_pRight;//记住原来的父亲节点 位置不变还是父亲
		Node* subRL = subR->_pLeft;//记住原来的父亲节点的有右边的孩子节点  孙子变爷爷了X
		int bf = subRL->_bf;//这里用于分情况记录平衡因子
		//先以父亲节点为祖宗右旋
		RotateR(pParent->_pRight);
		//以祖宗节点左旋
		RotateL(pParent);

		//更新平衡因子
		if (bf == 0)
		{
			subR->_bf = 0;
			subRL->_bf = 0;
			pParent->_bf = 0;
		}
		else if (bf == 1)
		{
			subR->_bf = 0;
			subRL->_bf = 0;
			pParent->_bf = -1;
		}
		else if (bf == -1)
		{
			subR->_bf = 1;
			subRL->_bf = 0;
			pParent->_bf = 0;
		}
		else
		{
			assert(false);
		}
	}

	Node* Find(const T& data)
	{
		Node* cur = _pRoot;
		while (cur)
		{
			if (cur->_data < data)
			{
				cur = cur->_pRight;
			}
			else if (cur->_data > data)
			{
				cur = cur->_pLeft;
			}
			else 
			{
				return cur;
			}
		}
		return nullptr;
	}

	bool _IsAVLTree(Node* pRoot)
	{
		if (pRoot == nullptr)
			return true;
		int LHigh = _Height(pRoot->_pLeft);
		int RHigh = _Height(pRoot->_pRight);
		int D = RHigh - LHigh;
		if (D < -1 || D > 1)
		{
			cout << pRoot->_data.first <<"高度异常" << endl;
			return false;
		}
		
		if (pRoot->_bf != D)
		{
			cout << pRoot->_data.first << "平衡因子异常" << endl;
		}

		return _IsAVLTree(pRoot->_pLeft) && _IsAVLTree(pRoot->_pRight);
	}
	size_t _Height(Node* pRoot){
		if (pRoot == nullptr)
			return 0;
		int LHigh = _Height(pRoot->_pLeft);
		int RHigh = _Height(pRoot->_pRight);

		return LHigh > RHigh ? LHigh + 1 : RHigh + 1;
	}