avl_tree.cpp

avl树的插入删除调整等等基本操作及具体实现

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

struct AVL_node
{
	int value;	//节点的值
	int balance_factor;	//右子树高度-左子树高度
	int depth;	//结点的高度
	AVL_node* parent;	//父节点
	AVL_node* left_child ;		//左子结点
	AVL_node* right_child;		//右子结点
};

typedef struct AVL_node AVL_node;

int search_node(int, AVL_node*, AVL_node** ,AVL_node**);	//查找值为value的节点，当没有找到结点时，保存寻找的最后一个结点

int depth(int, AVL_node*);

void adjust_node(AVL_node*, AVL_node*, AVL_node*, AVL_node**);	//调整插入的结点，使其满足AVL树的要求

int insert_node(int, AVL_node*, AVL_node**);	//插入一个结点，返回插入后AVL树的根

int delete_node(int, AVL_node*, AVL_node**);	//删除一个结点，

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)	//根节点为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型双旋转
		{
			temp = child->right_child;
			temp->parent = parent->parent;	//原来的最低结点上升为最高结点
			child->right_child = temp->left_child;//最低结点的子结点分部成为最高和中间结点的子结点
			if (temp->left_child != NULL)
				 temp->left_child->parent = child;//原来的中间节点成为最低节点的子结点
			parent->left_child = temp->right_child;//最低结点的子结点分部成为最高和中间结点的子结点
			
			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型单旋转
		{
			
			child->parent = parent->parent;//中间节点成为最高节点
			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型双旋转
		{
			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型单旋转
		{
			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)				//插入根节点
	{
		insert->parent = NULL;
		*ret = insert;
		return 1;
	}
	else
	if (tmp = search_node(value, root, &node, &parent))	//有重复结点，不插入,保存最后一个找到的结点，供后续插入使用
	{
		*ret = root;
		return 0;
	}
	else
	{
//============== 插入结点 ===============
		insert->parent = parent;	
		if (value < parent->value)
		{
			parent->left_child = insert;
			child = parent->left_child;	//保存插入的结点
		}
		else
		{
			parent->right_child = insert;
			child = parent->right_child;
		}

//======== 寻找需要调整的最小子树=========
		stop = 0;
		while ((parent != NULL))
		{
			//更新父节点的balance_factor:
			if (child == parent->left_child)					//新节点在父节点左面
				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;
				}
			else										//新节点在父节点右边
				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)								//不需要调整
		{
			*ret = root;
			return 1;
		}
		adjust_AVL_tree(root, parent, child, ret);			//不平衡时要调整
		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
	{
		//确定要删除结点
	    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;
		
		//如果要删除的结点有子结点，则将要删除的结点内容与其中序遍历时的前驱相交换，如此迭代，直到找到一个没有子结点的结点为止
		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;

		//调节删除后的不平衡
		while ((parent != NULL)) //查找需要调整的最小子树
		{
			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;
		}
	}
}