c++ AVLTree(高度平衡的搜索二叉树)

#pragma once

#include <iostream>

using namespace std;


#define	NEG  -1
#define	ZERO  0
#define	POS 1

template <class K,class V>


struct AVLTreeNode//树的节点
{
	K _key;
	V _value;
	AVLTreeNode* _left;
	AVLTreeNode* _right;
	AVLTreeNode* _parent;
	int _bf;

	AVLTreeNode(const K& key,const V& value)
		:_key(key)
		, _value(value)
		, _left(NULL)
		, _right(NULL)
		, _parent(NULL)
		, _bf(0)//平衡因子 取值 -1 0 1 （左高1  相等 右高1）
	{}
	
};

template<class K,class V>

class AVLTree
{
	typedef AVLTreeNode<K, V> Node;
public:
	AVLTree()
		:_root(NULL)
	{}
	~AVLTree(){}

	bool Insert(const K& key,const V& value)//插入
	{
		if (_root == NULL)
		{
			_root = new Node(key,value);//空树 直接插入
			return true;
		}
		Node* cur = _root, *prev = NULL;//当前 与 之前 节点指针
		while (cur){
			if (cur->_key < key)//插入key 比当前节点 key大 跳到右
			{
				if (cur->_right){//右不为空继续
					prev = cur;
					cur = cur->_right;
					if (cur->_bf == ZERO)//如果节点的bf为0，说明插入（如果成功），会改变prev->bf的值
						prev->_bf++;
				}
				else
				{//如果右为空 到达插入节点位置，插入cur->bf ++
					cur->_right = new Node(key,value);
					cur->_right->_parent = cur;
					cur->_bf++;
					break;
				}
			}
			else if (cur->_key>key)//同理 向左 插入
			{
				if (cur->_left){
					prev = cur;
					cur = cur->_left;
					if (cur->_bf == ZERO)
						prev->_bf--;
				}
				else
				{
					cur->_left = new Node(key, value);
					cur->_left->_parent = cur;

					cur->_bf--;
					break;
				}
			}
			else//key相等，插入失败，依次将改变的平衡因子 改回来
			{
				while (prev&&cur->_bf == ZERO)
				{
					if (prev->_left == cur)
						prev->_bf++;
					else
						prev->_bf--;
					cur = prev;
					prev = prev->_parent;
				}
				return false;

			}
		}
		//插入结束 对整棵树进行调节 使其继续平衡
		//高度不变
		if (cur->_bf == ZERO)
			return true;
		else//高度改变
		{
			//找高度变为-2 或 2的节点旋转
			while (prev)
			{
				if (prev->_bf < -1)//左高2
				{
					if (cur->_bf <= -1)//右旋
					{
						_RotateR(prev);
						cout << "右旋"<<endl;
						break;
					}
					else//左右旋
					{
						_RotateL(cur);
						_RotateR(prev);
						cout << "左右旋" << endl;

						break;
					}
				}
				else if (prev->_bf > 1)//右高2
				{
					if (cur->_bf >= 1)//左旋
					{
						_RotateL(prev);
						cout << "左旋" << endl;

						break;
					}
					else//右左旋
					{
						_RotateR(cur);
						_RotateL(prev);
						cout << "右左旋" << endl;
						break;
					}
				}
				cur = prev;
				prev = prev->_parent;
			}
		}
		return true;

	}

	

	bool IsBalance()
	{
		if (_root == NULL)
			return true;
		return _Isbalance(_root);
	}

	Node* Find(const K& key)
	{
		Node * cur = _root;
		while (cur){
			if (cur->_key > key)
				cur = cur->_left;
			else if (cur->_key < key)
				cur = cur->_right;
			else
				return cur;

		}
		return NULL;
	}
	
	bool Remove(const K& key)
	{
		if (_root == NULL)
		{
			return false;//空树删除失败
		}
		Node* cur = _root, *prev = NULL;
		while (cur){
			if (cur->_key < key)//删除位置在cur 右
			{
				if (cur->_right){//右非空，继续找
					prev = cur;
					cur = cur->_right;
				}
				else//右空，未找到删除节点 返回
					return false;
			}
			else if (cur->_key>key)//删除位置在左
			{
				if (cur->_left){
					prev = cur;
					cur = cur->_left;
				}
				else
					return false;				
			}
			else
			{
				Node* parent = cur->_parent;//记录删除节点的 父
				if (cur->_left == NULL)//删除节点 左空，直接使其右与prev相连
				{
						
					if (prev == NULL){//prev为空，删除根节点，根节点改变
						_root = cur->_right;
						delete cur;
						
						return true;
					}
					if (prev->_right == cur){//prev右为cur，cur的右连到prev右
						prev->_bf--;//平衡因子 减少
						prev->_right = cur->_right;
						if (cur->_right)
							cur->_right->_parent = prev;
					}
					if (prev->_left == cur){//prev左为 cur
						prev->_left = cur->_right;
						prev->_bf++;
						if (cur->_right)
							cur->_right->_parent = prev;
					}
					delete cur;//释放节点
					cur = prev;//将cur prev指向有效节点
					prev = cur->_parent;
				
				}
				else if (cur->_right == NULL)//同上 cur右为空
				{
					if (prev == NULL){
						_root = cur->_left;
						delete cur;
						
						return true;
					}
					if (prev->_right == cur){
						prev->_bf--;
						prev->_right = cur->_left;
						if (cur->_left)
							cur->_left->_parent = prev;
					}
					if (prev->_left == cur){
						prev->_left = cur->_left;
						prev->_bf++;
						if (cur->_left)
							cur->_left->_parent = prev;
					}
					delete cur;
					cur = prev;
					prev = cur->_parent;
			
				}
				else
				{//cur左右都非空，为了避免换当前root的复杂操作，替换为删除cur左孩子 最右 节点 ，或者cur右孩子的 最左 节点，将其内容拷贝给cur
					Node* tmp = cur;
					prev = cur;
					cur = cur->_right;
					
					while (cur->_left)//找右树最左
					{		
						prev = cur;
						cur = cur->_left;
					}
					tmp->_key = cur->_key;
					tmp->_value = cur->_value;//拷贝值
	
					if (cur == prev->_left)//调节prev bf并将 cur右树连接到prev                              
						prev->_bf++;
						prev->_left = cur->_right;
						
					}
					if (cur == prev->_right)//同上
					{
						prev->_bf--;
						prev->_right = cur->_right;

					}
					tmp = cur;//记录删除位置
					cur = prev;
					parent = cur;//cur prev 指向有效节点
					prev = cur->_parent;
					
					delete tmp;//删除tmp
				
				}
				while (prev &&cur->_bf == ZERO)//删除节点 父树高度可能改变，依次确认并修改 bf （cur bf为0 说明是 -1 或 1 变来 高度发生改变  需修改父节点 bf）
				{
					if (cur == prev->_left){
						prev->_bf++;
					}
					if (cur == prev->_right)
					{
						prev->_bf--;
					}
					
					cur = prev;
					prev = prev->_parent;
				}
				
				prev = parent;//prev指向 实际删除节点的父节点
				if (prev->_bf < ZERO)
					cur = prev->_left;
				if (prev->_bf > ZERO)
					cur = prev->_right;
				if (prev->_bf == ZERO){
					cur = prev;
					prev = prev->_parent;
				}
				break;
			}
		}
	
			//找高度变为-2 或 2的节点旋转
		while (prev)
		{
			if (prev->_bf < -1)//左高2
			{
				cur = prev->_left;//因为删除一侧节点可能需要另一侧旋转，因此需要对 cur重新赋值
				if (cur && (cur->_bf <= -1 || cur->_bf == ZERO))//右旋
				{
					_RotateR(prev);
					if (prev->_left&&prev->_right == NULL)//判断旋转后 prev的bf
						prev->_bf--;
					cout << "右旋" << endl;

				}
				else//左右旋
				{
					_RotateL(cur);
					_RotateR(prev);
					cout << "左右旋" << endl;
				}
				cur = prev->_parent;
				prev = cur->_parent;
				while (prev&&cur->_bf == ZERO)//依次修改旋转完毕的prev的bf
				{
					if (cur == prev->_left)
						prev->_bf++;
					else
						prev->_bf--;
					cur = prev;
					prev = prev->_parent;
				}
			}
			else if (prev->_bf > 1)//右高2
			{
				cur = prev->_right;
				if (cur && (cur->_bf >= 1 || cur->_bf == ZERO))//左旋
				{
					_RotateL(prev);
					cout << "左旋" << endl;
					if (prev->_right&&prev->_left == NULL)
						prev->_bf++;
				}
				else//右左旋
				{
					_RotateR(cur);
					_RotateL(prev);
					cout << "右左旋" << endl;
				}
				cur = prev->_parent;
				prev = cur->_parent;
				while (prev&&cur->_bf == ZERO)
				{
					if (cur == prev->_left)
						prev->_bf++;
					else
						prev->_bf--;
					cur = prev;
					prev = prev->_parent;
				}
			}
			cur = prev;
			if (prev)
				prev = prev->_parent;
		}
		return true;	
	}

private:
	Node* _root;

	int _height(Node* root)
	{
		if (root == NULL)
			return 0;
		int left = 1, right =1;
		left += _height(root->_left);
		right += _height(root->_right);
		return left > right ? left : right;
	}

	bool _Isbalance(Node* root)//判断 数是否平衡 bf是否匹配
	{
		if (root == NULL)
			return true;
		/*if (root ->_left==NULL&&root->_right==NULL)
			return true;*/
		bool left = _Isbalance(root->_left);
		bool right = _Isbalance(root->_right);

		int num1 = 1;
		num1+=_height(root->_left);
		int num2 = 1;
		num2+=_height(root->_right);
		if (left == false || right == false)
		{
			cout << "not balace!" << " key: " << root->_key << "bf: " << root->_bf << endl;
			return false;
		}
		if (num2-num1!=root->_bf)
		{
			cout << "bf error!" << "key:" << root->_key << "bf: " << root->_bf << "a-b:" << num1-num2 << endl;
			return false;
		}

		if (abs(num1-num2) <= 1)
			return true;
		return false;

	}
	//旋转后 bf 调节总结：左旋 bf 减小 右旋 bf 增加；sub=2 ，parent变化 3，sub变化 2；sub=1，parent 变化2，sub变化 1；
	void _RotateR(Node* parent)//右旋
	{
		Node* subL = parent->_left;
		Node* subLR = subL->_right;
		Node* ppNode=parent->_parent;

		subL->_right = parent;
		parent->_parent = subL;
		parent->_left = subLR;
		if (subLR)
			subLR->_parent = parent;
		if (ppNode)
		{
			if (ppNode->_left == parent)
				ppNode->_left = subL;
			else
				ppNode->_right = subL;

		}
		else
			_root = subL;
		subL->_parent = ppNode;//旋转
		//修改 bf
		if (subL->_bf == -2){
			parent->_bf = 1;
			subL->_bf=0;
		}
		else
		{
			subL->_bf++;
			parent->_bf = 0;
		}
		
	}

	void _RotateL(Node* parent)//左旋
	{
		Node* subR= parent->_right;
		Node* subRL = subR->_left;
		Node* ppNode = parent->_parent;

		subR->_left = parent;
		parent->_parent = subR;
		parent->_right = subRL;
		if (subRL)
			subRL->_parent = parent;
		if (ppNode)
		{
			if (ppNode->_left == parent)
				ppNode->_left = subR;
			else
				ppNode->_right = subR;

		}
		else
			_root = subR;
		subR->_parent = ppNode;//以上为左旋转
		
		//以下下修改 bf 值
		if (subR->_bf == 2)//右孩子的高度为2 说明旋转前 高度差在右孩子的下方，旋转后parent 右支 没有可以连接的，高度会降3 从2变为-1
		{
			parent->_bf = -1;
			subR->_bf = 0;
		}
		else{ //右孩子高度为1，旋转后高度将2 buf为 0，而右孩子  高度将1；
			parent->_bf = 0;
			subR->_bf--;
		}
	}
};