#include<iostream.h>
#include<iomanip.h>
#include<assert.h>

struct AVL_node
{
	int value;	//節(jié)點的值
	int balance_factor;	//右子樹高度-左子樹高度
	int depth;	//結(jié)點的高度
	AVL_node* parent;	//父節(jié)點
	AVL_node* left_child ;		//左子結(jié)點
	AVL_node* right_child;		//右子結(jié)點
};

typedef struct AVL_node AVL_node;

int search_node(int, AVL_node*, AVL_node** ,AVL_node**);	//查找值為value的節(jié)點，當(dāng)沒有找到結(jié)點時，保存尋找的最后一個結(jié)點

int depth(int, AVL_node*);

void adjust_node(AVL_node*, AVL_node*, AVL_node*, AVL_node**);	//調(diào)整插入的結(jié)點，使其滿足AVL樹的要求

int insert_node(int, AVL_node*, AVL_node**);	//插入一個結(jié)點，返回插入后AVL樹的根

int delete_node(int, AVL_node*, AVL_node**);	//刪除一個結(jié)點，

void AVL_pre_order(AVL_node*);	//前序遍歷AVL樹

void AVL_in_order(AVL_node*, int);	//中序遍歷AVL樹


int search_node(int value, AVL_node* root, AVL_node** node, AVL_node** parent)
{
	AVL_node* temp;
	int ret = 0;

	if (root == NULL)	//根節(jié)點為NULL時，返回-1
		ret = -1;
	else
	{
		*parent = NULL;
		temp = root;
		while (temp != NULL)
		{
			if (temp->value == value){
				*node = temp;
				ret = 1;
				break;
			}
			else{
				*parent = temp;
				if (temp->value > value)
					temp = temp->left_child; 
				else if (temp->value < value)
					temp = temp->right_child;
			}
		}
	}
	return ret;
}

int depth(int value, AVL_node* root)
{
	AVL_node* parent;
	AVL_node* node;
	if (search_node(value, root, &node, &parent))
	{
		return node->depth;
	}
	else return -1;
}


void adjust_AVL_tree(AVL_node* root, AVL_node* parent, AVL_node* child, AVL_node** ret)
{
	AVL_node* temp;
	assert((parent != NULL) && (child != NULL));
	switch (parent->balance_factor)
	{
		case -2:
		if (child->balance_factor == 1)	//LR型雙旋轉(zhuǎn)
		{
			temp = child->right_child;
			temp->parent = parent->parent;	//原來的最低結(jié)點上升為最高結(jié)點
			child->right_child = temp->left_child;//最低結(jié)點的子結(jié)點分部成為最高和中間結(jié)點的子結(jié)點
			if (temp->left_child != NULL)
				 temp->left_child->parent = child;//原來的中間節(jié)點成為最低節(jié)點的子結(jié)點
			parent->left_child = temp->right_child;//最低結(jié)點的子結(jié)點分部成為最高和中間結(jié)點的子結(jié)點
			
			if (temp->right_child != NULL)
				temp->right_child->parent = parent;
			temp->left_child = child;
			child->parent = temp;
			temp->right_child = parent;
			
			if (parent->parent != NULL)
				if (parent->parent->left_child == parent)	
					parent->parent->left_child = temp;
				else parent->parent->right_child = temp;
			else
				root = temp;
			parent->parent = temp;
			
			switch(temp->balance_factor)
			{
			case 0:
				parent->balance_factor = 0;
				child->balance_factor = 0;
				break;
			case 1:
				parent->balance_factor = 0;
				child->balance_factor = -1;
				break;
			default:
				parent->balance_factor = 1;
				child->balance_factor = 0;
				break;
			}
			temp->balance_factor = 0;
		}
		else //LL型單旋轉(zhuǎn)
		{
			
			child->parent = parent->parent;//中間節(jié)點成為最高節(jié)點
			parent->left_child = child->right_child;
			if (child->right_child != NULL)
				child->right_child->parent = parent;
			child->right_child = parent;
			if (parent->parent != NULL)
				if (parent->parent->left_child == parent)
					parent->parent->left_child = child;
				else parent->parent->right_child = child;
			else
				root = child;
			parent->parent = child;
			switch(child->balance_factor)
			{
			case -1:
				child->balance_factor = 0;
				parent->balance_factor = 0;
				break;
			default:
				child->balance_factor = 1;
				parent->balance_factor = -1;
				break;
			}
	    }	
		break;
   
		case 2:
		if (child->balance_factor == -1) //RL型雙旋轉(zhuǎn)
		{
			temp = child->left_child;
			temp->parent = parent->parent;
			child->left_child = temp->right_child;
			if (temp->right_child != NULL)
				temp->right_child->parent = child;
			parent->right_child = temp->left_child;
			if (temp->left_child != NULL)
				temp->left_child->parent = parent;
			temp->left_child = parent;
			temp->right_child = child;
			child->parent = temp;
			if (parent->parent != NULL)
				if (parent->parent->left_child == parent)
					parent->parent->left_child = temp;
				else parent->parent->right_child = temp;
			else
		        root = temp;
			parent->parent = temp;
			switch(temp->balance_factor)
			{
			case 0:
				parent->balance_factor = 0;
				child->balance_factor = 0;
				break;
			case -1:
				parent->balance_factor = 0;
				child->balance_factor = 1;
				break;
			default:
				parent->balance_factor = -1;
				child->balance_factor = 0;
				break;
			}
			temp->balance_factor = 0;
		}
		else  //RR型單旋轉(zhuǎn)
		{
			child->parent = parent->parent;
			parent->right_child = child->left_child;
			if (child->left_child != NULL)
				child->left_child->parent = parent;
		    child->left_child = parent;
			if (parent->parent != NULL)
				if (parent->parent->left_child == parent)
					parent->parent->left_child = child;
				else parent->parent->right_child = child;
			else
				root = child;
			parent->parent = child;
			switch(child->balance_factor)
			{
			case 1:
				child->balance_factor = 0;
				parent->balance_factor = 0;
				break;
			default:
				child->balance_factor = -1;
				parent->balance_factor = 1;
				break;
			}
		
		}
		break;
	}
	*ret = root;
}


int insert_node(int value, AVL_node* root, AVL_node** ret)
{
	AVL_node *parent = NULL, *insert = NULL, *child = NULL, *node;
	int tmp,stop;
	insert = new AVL_node;
	insert->value = value;
	insert->left_child = NULL;
	insert->right_child = NULL;
	insert->balance_factor = 0;
	if (root == NULL)				//插入根節(jié)點
	{
		insert->parent = NULL;
		*ret = insert;
		return 1;
	}
	else
	if (tmp = search_node(value, root, &node, &parent))	//有重復(fù)結(jié)點，不插入,保存最后一個找到的結(jié)點，供后續(xù)插入使用
	{
		*ret = root;
		return 0;
	}
	else
	{
//============== 插入結(jié)點 ===============
		insert->parent = parent;	
		if (value < parent->value)
		{
			parent->left_child = insert;
			child = parent->left_child;	//保存插入的結(jié)點
		}
		else
		{
			parent->right_child = insert;
			child = parent->right_child;
		}

//======== 尋找需要調(diào)整的最小子樹=========
		stop = 0;
		while ((parent != NULL))
		{
			//更新父節(jié)點的balance_factor:
			if (child == parent->left_child)					//新節(jié)點在父節(jié)點左面
				switch (parent->balance_factor)
				{
				case 1:
					parent->balance_factor = 0;			//平衡，不需要調(diào)整
					*ret = root;
					return 1;
				case -1:
					parent->balance_factor = -2;
					stop = 1;
					break;
				default:
					parent->balance_factor = -1;
					child = parent;
					parent = parent->parent;
					break;
				}
			else										//新節(jié)點在父節(jié)點右邊
				switch (parent->balance_factor)
				{	
				case -1:
					parent->balance_factor = 0;
					*ret = root;
					return 1;
				case 1:
					parent->balance_factor = 2;
					stop = 1;
					break;
				default:
					parent->balance_factor = 1;
					child = parent;
					parent = parent->parent;
					break;
				}
				if (stop) break;
			}
		
		if (parent == NULL)								//不需要調(diào)整
		{
			*ret = root;
			return 1;
		}
		adjust_AVL_tree(root, parent, child, ret);			//不平衡時要調(diào)整
		return 1;
	}
}

int delete_node(int value, AVL_node* root, AVL_node** ret)
{
	AVL_node *deleted_node = NULL, *parent = NULL, *child = NULL, *temp_parent = NULL, *node = NULL;
	int temp, flag;

	assert(root!=NULL);

	if (!search_node(value, root, &node, &parent)){
	    *ret = root;
		return 0;
	}
	else
	{
		//確定要刪除結(jié)點
	    if (parent == NULL)
			deleted_node = root;
		else if ((parent->left_child != NULL) && (parent->left_child->value == value))
			deleted_node = parent->left_child;
		else deleted_node = parent->right_child;

		child = deleted_node;
		
		//如果要刪除的結(jié)點有子結(jié)點，則將要刪除的結(jié)點內(nèi)容與其中序遍歷時的前驅(qū)相交換，如此迭代，直到找到一個沒有子結(jié)點的結(jié)點為止
		while ((child->left_child != NULL) || (child->right_child != NULL))
		{
			if (child->balance_factor == -1){
				if (deleted_node->left_child != NULL){
					child = deleted_node->left_child;	
					while (child->left_child != NULL)
						child = child->left_child;
				}
				else{
					child = deleted_node;
					while ((child->parent != NULL) && (child != child->parent->right_child));
						child = child->parent;
				}	
			}

			else{
				if (deleted_node->right_child != NULL){
					child = deleted_node->right_child;	
					while (child->right_child != NULL)
						child = child->right_child;
				}
				else{
					child = deleted_node;
					while ((child->parent != NULL) && (child != child->parent->left_child));
						child = child->parent;
				}
			}

			temp = child->value;
			child->value = deleted_node->value;
			deleted_node->value = temp;
			deleted_node = child;
		}

		//真正要刪除的點
		child = deleted_node;
		parent = deleted_node->parent;

		//調(diào)節(jié)刪除后的不平衡
		while ((parent != NULL)) //查找需要調(diào)整的最小子樹
		{
			if (child == parent->left_child)
			{
				if (parent->balance_factor == -1)
				{
					parent->balance_factor = 0;
					child = parent;
					parent = parent->parent;
				}
				else if (parent->balance_factor == 1)
				{
					parent->balance_factor = 2;
					child = parent->right_child;
					temp = parent->right_child->balance_factor;
					temp_parent = parent->parent;
					if (temp_parent == NULL)
						flag = 0;
					else
						if (parent == temp_parent->left_child)
							flag = 1;
						else flag = -1;
					
					adjust_AVL_tree(root, parent, child, &root);

					if (temp != 0)
					{
						switch(flag)
						{
						case 1:
							child = temp_parent->left_child;
							break;
						case -1:
							child = temp_parent->right_child;
							break;
						}
						parent = temp_parent;
					}
					else break;
				}
				else
				{
					parent->balance_factor = 1;
					break;
				}
			}
			else 
				if (parent->balance_factor == 1)
				{
					parent->balance_factor = 0;
					child = parent;
					parent = parent->parent;
				}
				else if (parent->balance_factor == -1)
				{
					parent->balance_factor = -2;
					child = parent->left_child;
					temp = parent->left_child->balance_factor;
					temp_parent = parent->parent;
					if (temp_parent == NULL)
						flag = 0;
					else
						if (parent == temp_parent->left_child)
							flag = 1;
						else flag = -1;

					adjust_AVL_tree(root, parent, child, &root);

					if (temp != 0)
					{
						if (flag == 1)
							child = temp_parent->left_child;
						else if (flag == -1)
							child = temp_parent->right_child;
						parent = temp_parent;
					}
					else break;
				}
				else
				{
					parent->balance_factor = -1;
					break;
				}
		}
	    if (deleted_node->parent != NULL)
			if (deleted_node != deleted_node->parent->left_child)
				deleted_node->parent->right_child = NULL;
			else deleted_node->parent->left_child = NULL;

		delete deleted_node;
		if (root == deleted_node)
			root = NULL;
		deleted_node = NULL;
		*ret = root;
		return 1;
	}
}

void AVL_pre_order(AVL_node* root) //前序遍歷
{
	if (root != NULL)
	{
		AVL_pre_order(root->left_child);
		if(root->parent != NULL)
			cout<<setw(3)<<root->value<<"  parent: "<<setw(3)<<root->parent->value;
		else
			cout<<setw(3)<<root->value<<"  root!      ";
		if(root->left_child!=NULL)
			cout<<"  left_child: "<<setw(3)<<root->left_child->value;
		else cout<<"  no left_child!";
		if(root->right_child!=NULL)
			cout<<"   right_child: "<<setw(3)<<root->right_child->value;
		else cout<<"   no rifht_child!";
		cout<<endl;
		AVL_pre_order(root->right_child);
	}
}

void AVL_in_order(AVL_node* root, int depth) //中序遍歷
{
	if (root != NULL)
	{
		if(root->parent != NULL)
			cout<<setw(3)<<root->value<<"  parent: "<<setw(3)<<root->parent->value;
		else
			cout<<setw(3)<<root->value<<"  root!      ";
		if(root->left_child!=NULL)
			cout<<"  left_child: "<<setw(3)<<root->left_child->value;
		else cout<<"  no left_child!";
		if(root->right_child!=NULL)
			cout<<"   right_child: "<<setw(3)<<root->right_child->value;
		else cout<<"   no rifht_child!";
		cout<<endl;
		root->depth = depth;
		AVL_in_order(root->left_child, depth + 1);
		AVL_in_order(root->right_child, depth + 1);
	}
}


void main(int argc, char *argv[])
{
	AVL_node* root = NULL;
	int data[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
	int i;
	
	for(i = 0; i < sizeof(data)/sizeof(int); i++)
	{
		if(insert_node(data[i], root, &root)){
			cout<<"                      AFTER ADDING NODE: "<<data[i]<<endl;
			cout<<"Pre_order:"<<endl;
			AVL_pre_order(root);
			cout<<endl;
			cout<<"In_order:"<<endl;
			AVL_in_order(root,0);
			cout<<endl;
		}
		else
		{
			cout<<"Inserting failed!"<<endl;
			break;
		}
	}

	for(i = 0; i < sizeof(data)/sizeof(int); i++)
	{
		if(delete_node(data[i], root, &root)){
			cout<<"                      AFTER DELETING NODE: "<<data[i]<<endl;
			cout<<"Pre_order:"<<endl;
			AVL_pre_order(root);
			cout<<endl;
			cout<<"In_order:"<<endl;
			AVL_in_order(root,0);
			cout<<endl;
		}
		else
		{
			cout<<"Deleting failed!"<<endl;
			break;
		}
	}
}