trees.cpp

对三种数据结构的分析.avl tree,splaytree和binary search tree的插入和删除的算法复杂度分析.

	else if(element < T->Element) /* element is smaller than the T->Element */
	{
		T->Left=A_Insert(element,T->Left); /* go to the left subtree */
		if(Height(T->Left) - Height(T->Right)==2) /* unbalance */
			if(element < T->Left->Element) /* LL rotation */
				T=A_SingleRotateWithLeft(T);
			else /* LR ratation */
				T=A_DoubleRotateWithLeft(T);
	}
	else if(element > T->Element) /* element is larger than the T->Element */
	{
		T->Right=A_Insert(element,T->Right); /* go to the right subtree */
		if(Height(T->Right) - Height(T->Left)==2) /* unbalance */
			if(element > T->Right->Element) /* RR rotation */
				T=A_SingleRotateWithRight(T);
			else /* RL ratation */
				T=A_DoubleRotateWithRight(T);
	}

	T->height=Max(Height(T->Left),Height(T->Right))+1;
	return T;
}

avltree A_Delete(int element,avltree T) /* delete the integers */
{
	avltree TmpCell;
	if(T==NULL) /* empty tree */
		printf("not found\n");
	else if(element < T->Element) /* smaller than T */
	{
		T->Left=A_Delete(element,T->Left); /* go to the left subtree*/
		if(Height(T->Right)-Height(T->Left)==2) /* unbalance */
			if(Height(T->Right->Left) > Height(T->Right->Right)) /* RL rotation */
				T=A_DoubleRotateWithRight(T);
			else /* RR rotation */
				T=A_SingleRotateWithRight(T);
	}
	else if(element > T->Element) /* larger than T */
	{
		T->Right=A_Delete(element,T->Right); /* go to the right subtree*/
		if(Height(T->Left)-Height(T->Right)==2) /* unbalance */
			if(Height(T->Left->Right) > Height(T->Left->Left)) /* LR rotation */  
				T=A_DoubleRotateWithLeft(T);
			else /* LL rotation */
				T=A_SingleRotateWithLeft(T);
	}
	else /*find the element */
		if(T->Left && T->Right) /* two children */
		{
			TmpCell=A_FindMin(T->Right);
			T->Element=TmpCell->Element;
			T->Right=A_Delete(TmpCell->Element,T->Right);
			if(Height(T->Left)-Height(T->Right)==2) /* unbalance */
			if(Height(T->Left->Right) > Height(T->Left->Left)) /* LR rotation */
				T=A_DoubleRotateWithLeft(T);
			else /* LL rotation */
				T=A_SingleRotateWithLeft(T);
		}
		else /* one or zero child */
		{
			TmpCell=T;
			if(T->Left==NULL)      
				T=T->Right;
			else
				T=T->Left;
			free(TmpCell);
		}

	if(T!=NULL)
		T->height=Max(Height(T->Left),Height(T->Right))+1; /* update the height */
	return T;
}

avltree A_SingleRotateWithLeft(avltree T) /* LL rotation */
{
	avltree A;

	A=T->Left; /* rotate */
	T->Left=A->Right;
	A->Right=T;

	A->height=Max(Height(A->Left),Height(A->Right))+1; /* change height */
	T->height=Max(Height(T->Left),Height(T->Right))+1;

	return A; /* new root */

}

avltree A_SingleRotateWithRight(avltree T) /* RR rotation */
{
	avltree A;

	A=T->Right; /* rotate */
	T->Right=A->Left;
	A->Left=T;

	A->height=Max(Height(A->Left),Height(A->Right))+1; /* change height */
	T->height=Max(Height(T->Left),Height(T->Right))+1;

	return A; /* new root */

}

avltree A_DoubleRotateWithLeft(avltree T) /* LR rotation */
{
	T->Left=A_SingleRotateWithRight(T->Left);/* rotate between the two desandents of T */
	return A_SingleRotateWithLeft(T);/* rotate between T and its son */
}

avltree A_DoubleRotateWithRight(avltree T) /* RL rotation */
{
	T->Right=A_SingleRotateWithLeft(T->Right); /*rotate between the two desandents of T */
	return A_SingleRotateWithRight(T);/* rotate between T and its son */
}

avltree A_FindMin(avltree T) /* find the mininum node in the tree*/
{
	if(T!=NULL)
		while(T->Left!=NULL)
			T=T->Left;

	return T;
}

int Max(int a,int b) /*return the larger number */
{
	if(a>b)
		return a;
	else
		return b;
}

int Height(avltree T) /* calculate the avltree's height */
{
	if(T==NULL)
		return -1;
	else
		return T->height;
}

/************************************ functions about Splay Tree *********************************/

splaytree Sp_Insert(int element,splaytree T) /* insert the integers */
{
	T=S_Insert(element,T); /*insert the integers in a binary search tree */
	T=splay(element,T); /* splay the element which needs to be inserted */

	return T;
}

splaytree Sp_Delete(int element,splaytree T) /* delete the integers */
{
	splaytree TmpCell,New;

	T=splay(element,T); /* splay the node which needs to be deleted */
	if(T->Left!=NULL)
	{
		TmpCell=FindMax(T->Left); /* find the maxmum from the left subtree */
		New=splay(TmpCell->Element,T->Left); /* splay the maxmum node of the left subtree */
		New->Right=T->Right; /* then the left subtree has a root which dosen't have right child so connect it with the right subtree*/
	}
	else
		New=T->Right;
	free(T); /*delete the node which needs to be deleted */

	return New;
}

splaytree FindMax(splaytree T) /* find the maxmum in a tree */
{
	if(T!=NULL)
		while(T->Right!=NULL)
			T=T->Right;

	return T;
}

splaytree splay(int element,splaytree T) /* splay at the node element */
{
	splaytree TmpCell; /* TmpCell points to the root */
	splaytree Father;  /* Father points to the father node of T */

	for(;T->Element!=element && T!=NULL;) /* splay until the root is the element */
	{
		if(T->Right!=NULL && T->Right->Element == element) /* the element is the right son of the root */
		{
			T=Sp_SingleRotateWithRight(T); /* right rotate */
			break;
		}
		else if(T->Left!=NULL && T->Left->Element == element) /* the element is the left son of the root */
		{
			T=Sp_SingleRotateWithLeft(T); /* left rotate */
			break;
		}
		else if(T->Right!=NULL && T->Right->Right!=NULL && T->Right->Right->Element == element) /* zig-zig */
		{
			T=Sp_SingleRotateWithRight(T);
			T=Sp_SingleRotateWithRight(T);
			break;
		}
		else if(T->Right!=NULL && T->Right->Left!=NULL && T->Right->Left->Element == element) /* zig-zag */
		{
			T=Sp_DoubleRotateWithRight(T); /* RL rotate */
			break;
		}
		else if(T->Left!=NULL && T->Left->Left!=NULL && T->Left->Left->Element == element) /* zig-zig */
		{
			T=Sp_SingleRotateWithLeft(T);
			T=Sp_SingleRotateWithLeft(T);
			break;
		}
		else if(T->Left!=NULL && T->Left->Right!=NULL && T->Left->Right->Element == element) /* zig-zag */
		{
			T=Sp_DoubleRotateWithLeft(T); /* LR rotate */
			break;
		}
		else /* the element is neither the son nor the grandson of the root */
			for(TmpCell=T;;) /* splay until the element is the son or the grandson of the root*/
			{
                if(TmpCell->Right!=NULL && TmpCell->Right->Right!=NULL && TmpCell->Right->Right->Element == element) /* zig-zig */
				{
					if(Father->Left!=NULL && Father->Left->Element == TmpCell->Element)
					{
						TmpCell=Sp_SingleRotateWithRight(TmpCell);
						Father->Left=Sp_SingleRotateWithRight(TmpCell);
					}
					else
					{
						TmpCell=Sp_SingleRotateWithRight(TmpCell);
						Father->Right=Sp_SingleRotateWithRight(TmpCell);
					}

					break;
				}

				else if(TmpCell->Right!=NULL && TmpCell->Right->Left!=NULL && TmpCell->Right->Left->Element == element)  /* zig-zag */
				{
					if(Father->Left!=NULL && Father->Left->Element == TmpCell->Element)
						Father->Left=Sp_DoubleRotateWithRight(TmpCell);
					else
						Father->Right=Sp_DoubleRotateWithRight(TmpCell);

					break;
				}
				else if(TmpCell->Left!=NULL && TmpCell->Left->Left!=NULL && TmpCell->Left->Left->Element == element) /* zig-zig */
				{
					if(Father->Left!=NULL && Father->Left->Element == TmpCell->Element)
					{
						TmpCell=Sp_SingleRotateWithLeft(TmpCell);
						Father->Left=Sp_SingleRotateWithLeft(TmpCell);
					}
					else
					{
						TmpCell=Sp_SingleRotateWithLeft(TmpCell);
						Father->Right=Sp_SingleRotateWithLeft(TmpCell);
					}

					break;
				}
				else if(TmpCell->Left!=NULL && TmpCell->Left->Right!=NULL && TmpCell->Left->Right->Element == element)  /* zig-zag */
				{
					if(Father->Left!=NULL && Father->Left->Element == TmpCell->Element)
						Father->Left=Sp_DoubleRotateWithLeft(TmpCell);
					else
						Father->Right=Sp_DoubleRotateWithLeft(TmpCell);

					break;
				}
				/* the element is neither the son nor the grandson of the root */
				else if(TmpCell->Element < element) /* the element in the right subtree of T*/
				{
					Father=TmpCell; /* reserve the father node of T */
					TmpCell=TmpCell->Right; /*move down the T to deep splay*/
				}
				else /* the element in the left subtree of T*/
				{
					Father=TmpCell; /* reserve the father node of T */
					TmpCell=TmpCell->Left; /*move down the T to deep splay*/
				}
			}
	}

	return T;
}

splaytree Sp_SingleRotateWithLeft(splaytree T) /* left rotate */
{
	splaytree A;

	A=T->Left; /* rotate */
	T->Left=A->Right;
	A->Right=T;

	return A; /* new root */
}

splaytree Sp_SingleRotateWithRight(splaytree T) /* right rotate */
{
	splaytree A;

	A=T->Right; /* rotate */
	T->Right=A->Left;
	A->Left=T;

	return A; /* new root */
}

splaytree Sp_DoubleRotateWithLeft(splaytree T) /* LR rotate */
{
	T->Left=Sp_SingleRotateWithRight(T->Left);/* rotate between the two desandents of T */
	return Sp_SingleRotateWithLeft(T);/* rotate between T and its son */
}

splaytree Sp_DoubleRotateWithRight(splaytree T) /* RL rotate */
{
	T->Right=Sp_SingleRotateWithLeft(T->Right);/* rotate between the two desandents of T */
	return Sp_SingleRotateWithRight(T);/* rotate between T and its son */
}