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--;
		}
	}
};