通用AVLTree

现在的位置: 首页 > 综合 > 正文

RSS

2013年10月16日 ⁄ 综合 ⁄ 共 7345字 ⁄ 字号小中大 ⁄ 评论关闭

算法描述：

在平衡的二叉排序树T上插入一个关键码为kx的新元素，递归算法可描述如下：

㈠若T为空树，则插入一个数据元素为kx的新结点作为T的根结点，树的深度增1；

㈡若kx和T的根结点关键码相等，则不进行插入；

㈢若kx小于T的根结点关键码，而且在T的左子树中不存在与kx有相同关键码的结点,则将新元素插入在T的左子树上，并且当插入之后的左子树深度增加1时，分别就下列情况进行处理：

⑴ T的根结点平衡因子为-1(右子树的深度大于左子树的深度)，则将根结点的平衡因子更改为0，T的深度不变；

⑵ T的根结点平衡因子为0(左、右子树的深度相等)，则将根结点的平衡因子更改为1，T的深度增加1；

⑶ T的根结点平衡因子为1(左子树的深度大于右子树的深度),则若T的左子树根结点的平衡因子为1,需进行单向右旋平衡处理并且在右旋处理之后，将根结点和其右子树根结点的平衡因子更改为0，树的深度不变；若T的左子树根结点平衡因子为-1，需进行先左后右双向旋转平衡处理，并且在旋转处理之后，修改根结点和其左、右子树根结点的平衡因子，树的深度不变。

㈣若kx大于T的根结点关键码，而且在T的右子树中不存在与kx有相同关键码的结点，则将新元素插入在T的右子树上并且当插入之后的右子树深度增加1时，分别就不同情况处理之。其处理操作和㈢中所述相对称。

动画演示：

http://www.cnblogs.com/abatei/archive/2008/11/17/1335031.html

牛人博客一篇，完美的对称化：

http://blog.csdn.net/happycock/article/details/20874

code:

/*
*设计思路：
1.通过void *表示任意类型的数据
2.通过为插入函数提供比较函数，实现任意数据的插入
3.本头文件实现的是适合任意类型的平衡二叉树的数据结构，目前仅支持字符串和整型数据的平衡二叉树；
若需要其他类型，定义相关的比较函数即可；
4.平衡二叉树构造的基本思想：节点的平衡因子只能是-1，0，1；在插入造成不平衡时，需要对距离插入节点最近的不平衡节点做旋转处理，上面的则不作处理；
5.插入的基本操作是左旋和右旋，左右旋和右左旋也能划分为这两种操作，关键在于旋转后平衡因子的确定
*/
#include <stdlib.h>
#include <string.h>

#define LH 1
#define EH 0
#define RH -1
typedef int (*COMPARE_FUNC)(void *, void *);

typedef struct avlnode{
	void *data;
	struct avlnode *lchild, *rchild;
	int bf;
}AVLNode, *AVLTree;

int compare_string(void *str1, void *str2)
{//call back func
	char *s1 = (char *)str1;
	char *s2 = (char *)str2;

	return strcmp(s1,s2);
}
int compare_int(void *var1, void *var2)
{
	int v1 = *(int *)var1;
	int v2 = *(int *)var2;

	return v1 - v2;
}
void R_Rotate(AVLTree *root)
{//向右旋转，适合LL型
	AVLTree lchild = (*root)->lchild;

	(*root)->lchild = lchild->rchild;
	lchild->rchild = *root;
	*root = lchild;
}
void L_Rotate(AVLTree *root)
{
	AVLTree rchild = (*root)->rchild;

	(*root)->rchild = rchild->lchild;
	rchild->lchild = *root;
	(*root) = rchild;
}
void RightBalance(AVLTree *root)
{//bf == -2
	AVLTree rchild = (*root)->rchild;
	AVLTree rlchild;

	switch(rchild->bf)
	{
	case RH:
		rchild->bf = EH;
		(*root)->bf = EH;
		L_Rotate(root);
		break;
	case LH:
		rlchild = rchild->lchild;
		switch(rlchild->bf)
		{
		case RH:
			(*root)->bf = LH;
			rchild->bf = EH;
			break;
		case EH:
			(*root)->bf = EH;
			rchild->bf = EH;
			break;
		case LH:
			(*root)->bf = EH;
			rchild->bf = RH;
			break;
		}
		rlchild->bf = EH;
		R_Rotate(&((*root)->rchild));
		L_Rotate(root);
	default:
		break;
	}
}
void LeftBalance(AVLTree *root)
{//bf == 2
	AVLTree lchild = (*root)->lchild;
	AVLTree lrchild;

	switch(lchild->bf)
	{
	case LH://LL型 root bf 2 lchild bf 1
		lchild->bf = EH;
		(*root)->bf = EH;
		R_Rotate(root);
		break;
	case RH://LR型
		lrchild = lchild->rchild;
		switch(lrchild->bf)
		{
		case LH:
			(*root)->bf = RH;
			lchild->bf = EH;
			break;
		case EH:
			(*root)->bf = EH;
			lchild->bf = EH;
			break;
		case RH:
			(*root)->bf = EH;
			lchild->bf = LH;
			break;
		}
		lrchild->bf = EH;
		L_Rotate(&((*root)->lchild));
		R_Rotate(root);
	default:
		break;
	}
}
int shorter = 0;
void RightBalanceD(AVLTree *root)
{
	AVLTree rchild = (*root)->rchild;
	AVLTree rlchild;

	switch(rchild->bf)
	{
		case RH:
			(*root)->bf = rchild->bf = EH;
			R_Rotate(root);
			break;
		case EH:
			(*root)->bf = RH;
			rchild->bf = RH;
			L_Rotate(root);
			shorter = 0;
			break;
		case LH:
			rlchild = rchild->lchild;
			switch(rlchild->bf)
			{
				case LH:
					(*root)->bf = LH;
					rchild->bf = EH;
					break;
				case EH:
					(*root)->bf = EH;
					rchild->bf = EH;
					break;
				case RH:
					(*root)->bf  = EH;
					rchild->bf = RH;
					break;
			}
			rlchild->bf = EH;
			R_Rotate(&((*root)->rchild));
			L_Rotate(root);
	}
}
void LeftBalanceD(AVLTree *root)
{
	AVLTree lchild = (*root)->lchild;
	AVLTree lrchild;

	switch(lchild->bf)
	{
		case LH:
			(*root)->bf = lchild->bf = EH;
			R_Rotate(root);
			break;
		case EH:
			(*root)->bf = LH;
			lchild->bf = RH;
			R_Rotate(root);
			break;
		case RH:
			lrchild = lchild->rchild;
			switch(lrchild->bf)
			{
				case RH:
					(*root)->bf = EH;
					lchild->bf = EH;
					shorter = 0;
					break;
				case EH:
					(*root)->bf = EH;
					lchild->bf = EH;
					shorter = 1;
					break;
				case LH:
					(*root)->bf  = RH;
					lchild->bf = EH;
					shorter = 1;
					break;
			}
			lrchild->bf = EH;
			L_Rotate(&((*root)->lchild));
			R_Rotate(root);
	}
}
int AVLDelete(AVLTree *root, void *data, COMPARE_FUNC compare)
{
	int success = 0;
	int ret;

	if(NULL != *root)
	{
		ret = compare(data, (*root)->data);
		if( ret == 0)
		{			
			if(NULL != (*root)->lchild && NULL != (*root)->rchild)
			{
				AVLTree q,r;
				void *temp;

				//将左子树的最下面的右子树作为其替身，然后删掉,递归进行
				q = (*root)->lchild;
				r = q;
				while(q)
				{
					r = q;
					q = q->rchild;
				}
				temp = (*root)->data;
				(*root)->data = r->data;
				r->data =temp;

				AVLDelete(&(*root)->lchild, data, compare);
				if(1 == shorter)
				{
					switch((*root)->bf)
					{
					case LH:
						(*root)->bf = EH;
						break;
					case EH:
						(*root)->bf = RH;
						break;
					case RH:
						RightBalanceD(root);
						break;
					}//switch
				}//if  shorter
			}//if NULL
			else
			{
				//至少有一个子树为空
				AVLTree p = *root;

				*root = ((*root)->lchild != NULL)?(*root)->lchild:(*root)->rchild;
				free(p->data);
				free(p);

				success = 1;
				shorter = 1;
			}
		}//if compare
		else if(ret < 0)
		{
			success = AVLDelete(&((*root)->lchild), data, compare);
			if(shorter == 1)
			{
				switch((*root)->bf)
				{
				case LH:
					(*root)->bf = EH;
					shorter = 0;
					break;
				case EH:
					(*root)->bf = RH;
					break;
				case RH:
					RightBalanceD(root);
					break;
				}//switch
			}//if
		}//else if
		else if(ret > 0)
		{
			success = AVLDelete(&((*root)->rchild), data, compare);
			if(shorter == 1)
			{
				switch((*root)->bf)
				{
				case LH:
					LeftBalanceD(root);
					break;
				case EH:
					(*root)->bf = LH;
					break;
				case RH:
					(*root)->bf = EH;
					shorter = 0;
					break;
				}//switch
			}//if
		}//else if
	}//if root
	return success;
}
/*
output:
return 1:success
return 0:already exist
return -1:unexpected err
input: 
root:这棵平衡二叉树的根节点；
data:欲插入的数据指针；
len:插入数据的大小；
compare:插入数据类型的比较函数；
*/
int taller= 0;
int  AVLInsert(AVLTree *root, void *data,int len, COMPARE_FUNC compare)
{
	int ret;
	if(NULL == (*root))
	{
		(*root) = (AVLTree)malloc(sizeof(AVLNode));

		if(NULL == (*root))
			return -1;
		(*root)->data = (void *)(char *)malloc(len);
		if(NULL == (*root)->data)
			return -1;
		memcpy((*root)->data, data, len);
		(*root)->lchild = NULL;
		(*root)->rchild = NULL;
		(*root)->bf = EH;
		taller = 1;
		return 1;
	}
	//the tree is not empty
	ret = compare(data, (*root)->data);
	//already exist
	if(0 == ret)
		return 0;
	else if(ret > 0)
	{
		ret = AVLInsert(&((*root)->rchild), data, len, compare);

		if(-1 == ret)
			return -1;
		else if( 0 == ret)
			return 0;
		if(taller != 0)
		{
			switch((*root)->bf)
			{
			case LH:
				(*root)->bf = EH;
				taller = 0;
				break;
			case  EH:
				(*root)->bf = RH;
				taller = 1;
				break;
			case RH:
				RightBalance(root);
				taller = 0;
				break;
			default:
				break;
			}
		}
	}
	else
	{
		ret = AVLInsert(&((*root)->lchild), data, len, compare);

		if(-1 == ret)
			return -1;
		else if( 0 == ret)
			return 0;
		if(taller != 0)
		{
			switch((*root)->bf)
			{
			case RH:
				(*root)->bf = EH;
				taller = 0;
				break;
			case EH:
				(*root)->bf = LH;
				taller = 1;
				break;
			case LH:
				LeftBalance(root);
				taller = 0;
				break;
			default:
				break;
			}
		}
	}
	return 1;
}
/*
 *free the tree
*/
void FreeTree(AVLTree *root)
{
	if(NULL != *root)
	{
		FreeTree(&((*root)->lchild));
		FreeTree(&((*root)->rchild));
		free((*root)->data);
		free(*root);
		*root = NULL;
	}
}
/*
search for the data in the avltree
input:
		root: root of the searching tree
		data:data to search
		compare:compare func for data
output:
		NULL:not find
		!NULL: find the result
*/
AVLNode *SearchAVLNode(AVLTree root, void *data, COMPARE_FUNC compare)
{
	int ret;

	if(NULL != root)
	{
		ret = compare(root->data, data);
		if(0 == ret)
			return root;
		else if(ret > 0)
			return SearchAVLNode(root->lchild, data, compare);
		else
			return SearchAVLNode(root->rchild, data, compare);
	}
	return NULL;
}
void in_order_tranverse(AVLTree root, int type)
{
	if(root)
	{
		in_order_tranverse(root->lchild, type);
		if(1 == type)//string
			printf("%s  %d\n",  (char *)(root->data), root->bf);
		else if(2 == type)
			printf("%d  %d\n",  *(int *)(root->data), root->bf);
		in_order_tranverse(root->rchild, type);
	}
}
void avltree_test()
{
	AVLTree string_root = NULL;
	AVLTree int_root = NULL;
	char *str[] = {"file", "edit", "view", "qt", "project", "build", "debug", "tools","window", "community", "help"};
	int num[]={34,24,67, 1, 56, 83, 27, 98};
	int  i;

	for(i = 0; i < sizeof(str)/sizeof(char *); i++)
		AVLInsert(&string_root, (void *)str[i], strlen(str[i]) +1, compare_string);
	for(i= 0; i< sizeof(num)/sizeof(int *); i++)
		AVLInsert(&int_root, (void *)(num + i), sizeof(int), compare_int);

	AVLDelete(&string_root, "qt", compare_string);

	in_order_tranverse(string_root, 1);
	in_order_tranverse(int_root, 2);
	if(SearchAVLNode(string_root, "project", compare_string))
		printf("Find project\n");
	else
		printf("Not find project\n");
	
	if(SearchAVLNode(string_root, "home", compare_string))
		printf("Find home\n");
	else
		printf("Not find home\n");

	if(SearchAVLNode(int_root, num + 3, compare_string))
		printf("Find %d\n", *(num + 3));
	else
		printf("Not find %d\n", *(num + 3));


	//FreeTree(&string_root);
	FreeTree(&int_root);
}

【上篇】high-performance server architecture
【下篇】Multimedia Application Programming Guide

作者: danqiu123

该日志由 danqiu123 于11年前发表在综合分类下，最后更新于 2013年10月16日.
转载请注明: 通用AVLTree | 学步园 +复制链接

抱歉!评论已关闭.

学步园

通用AVLTree

作者: danqiu123

书签

最新文章New

本站推荐

返回首页