avltree.cpp

AVL平衡二叉树。原本在这里下载了其他人的平衡二叉树

	node = Child->parent;
	while(node)
	{
		switch(RotateType)
		{
		case L_CHILD:
			/* the direct parent of the inserted node, which the balance factor is 0 or -1. */
			node->bf++;	
			break;
		case LR_CHILD:
			if(node->bf == 1)
				return l_avlLRRotate(pTree, node);
			node->bf++;
			break;
		case LL_CHILD:
			if(node->bf == 1)
				return l_avlLLRotate(pTree, node);
			node->bf++;
			break;
		case R_CHILD:
			/* the direct parent of the inserted node, which the balance factor is 0 or 1. */
			node->bf--;
			break;
		case RL_CHILD:
			if(node->bf == -1)
				return l_avlRLRotate(pTree, node);
			node->bf--;
			break;
		case RR_CHILD:
			if(node->bf == -1)
				return l_avlRRRotate(pTree, node);
			node->bf--;
			break;
			
		}	/* switch(RotateType) */
		
		/* just return if the height of the current node is greater than or equal to the new height. */
		if(node->height >= height)	
			return AVLTRUE;
		node->height = height++;	/* the height is increased */
		
		/* return if reach the root node. */
		if(!node->parent)	
			return AVLTRUE;

		/* detect the type of son and grandson. */
		if((RotateType == L_CHILD)||(RotateType == LR_CHILD)||(RotateType == LL_CHILD))
		{
			if(node->parent->left == node)
				RotateType = LL_CHILD;
			else
				RotateType = RL_CHILD;
		}
		else
		{
			if(node->parent->left == node)
				RotateType = LR_CHILD;
			else
				RotateType = RR_CHILD;
		}

		node = node->parent;		/* go back to the parent */
	}	/* while(node) */

	return AVLTRUE;
}


/* Find a node with the specified weight. */
static PAVL_NODE l_avlFind(AVL_TREE *pTree, int w)
{
	PAVL_NODE child;
	int nComparison;

	if ( NULL==pTree )
		return NULL;

	child = pTree->pRoot;
	while( child != NULL )
	{
		if(w == child->weight)
			return child;

		nComparison = l_avlCompare(w, child->weight);
		if(nComparison == 0)
			return child;
		else if (nComparison > 0)
		{
			/* the new node is greater, check whether the right sub-tree is empty or not */
			child = child->right;
		}
		else if (nComparison < 0)
		{
			/* the new node is smaller, check whether the left subtree is empty or not */
			child = child->left;
		}
	}
	return NULL;
}

/*  */
static AVLBOOL l_avlBalanceAfterRemove(AVL_TREE *pTree, PAVL_NODE Node)
{
	int height = Node->height;
	PAVL_NODE parent = Node->parent;
	AVLBOOL bLeft = ((parent)&&(parent->left == Node))?AVLTRUE:AVLFALSE; 
	
	if((Node->left)&&(Node->right))
	{
		Node->bf = Node->left->height - Node->right->height;
		Node->height = (Node->left->height >= Node->right->height)
			? (Node->left->height+1) : (Node->right->height+1);
	}
	else if(Node->left)
	{
		Node->bf = Node->left->height+1;
		Node->height = Node->left->height+1;
	}
	else if(Node->right)
	{
		Node->bf = -1 - Node->right->height;
		Node->height = Node->right->height+1;
	}
	else
	{
		Node->bf = 0;
		Node->height = 0;
	}
	
	if(Node->bf == 2)
	{
		if(Node->left->bf == 1)
			l_avlLLRotate(pTree, Node);
		else
			l_avlLRRotate(pTree, Node);
	}
	else if(Node->bf == -2)
	{
		if(Node->right->bf == -1)
			l_avlRRRotate(pTree, Node);
		else
			l_avlRLRotate(pTree, Node);
	}
	
	if(parent)
	{
		if(bLeft)
		{
			if(height == parent->left->height)
				return AVLTRUE;
		}
		else
		{
			if(height == parent->right->height)
				return AVLTRUE;
		}
	}
	else 
	{ 
		return AVLTRUE; 
	}
	return l_avlBalanceAfterRemove(pTree, parent);
}

/* just remove the node without balancing the tree. */
static AVLBOOL l_avlRemoveNodeFromTree(AVL_TREE *pTree, PAVL_NODE Node)
{
	PAVL_NODE parent, child;

	parent = Node->parent;
	child = Node->left ? Node->left : Node->right;

	if(child) child->parent = parent;

	if ( !parent )
		pTree->pRoot = child;
	else if(parent->left == Node)
		parent->left = child;
	else
		parent->right = child;

	return AVLTRUE;
}

static AVLBOOL l_avlRelease(AVL_TREE *pTree, PAVL_NODE Node)
{
	memset(Node, 0, sizeof(AVL_NODE));
	Node->left = pTree->pFreeNodeLink;
	pTree->pFreeNodeLink = Node;
	return AVLTRUE;
}

/* ------------------------------- 接口函数 ----------------------------*/

/* 创建一个AVL 平衡二叉树
*/
AVL_TREE_TYPE avlCreate()
{
	AVL_TREE	*pTree;
	pTree = (AVL_TREE *)malloc(sizeof(AVL_TREE));
	if ( pTree )
	{
		pTree->pRoot = NULL;
		pTree->pFreeNodeLink = NULL;
		pTree->pTreeBuffer = NULL;
		pTree->pCurrentTreeBuffer = NULL;
		pTree->dataBeforeInsert = 0;
	}
	return (AVL_TREE_TYPE)pTree;
}

/* 销毁一个AVL 平衡二叉树
*/
void avlDestroy(AVL_TREE_TYPE tree)
{
	AVL_TREE	*pTree;
	pTree = (AVL_TREE *)tree;
	if ( pTree )
	{
		/* release tree buffer */
		pTree->pCurrentTreeBuffer = pTree->pTreeBuffer;
		while(pTree->pTreeBuffer)
		{
			pTree->pCurrentTreeBuffer = pTree->pTreeBuffer->Next;
			free(pTree->pTreeBuffer);
			pTree->pTreeBuffer = pTree->pCurrentTreeBuffer;
		}
	}
	free(pTree);
}

/* 插入一个结点
参数：w : 新结点的序号
      data : 新结点的数据
返回值：0 - 失败
        1 - 插入成功, 且树中原来没有该序号
		2 - 插入成功, 且树中原来有该序号
说明：如果树中原来有该序号的结点，则使用新的数据替换原来的数据
the bi-tree's weight is increased from left to right
*/
int avlInsert(AVL_TREE_TYPE tree, int w, unsigned long data)
{
	AVL_TREE	*pTree = (AVL_TREE *)tree;
	PAVL_NODE	node, child;
	int			nComparison;
	int			nResult = 1;

	if ( 0 == tree )
		return 0;
	pTree->dataBeforeInsert = 0;
	
	if(!pTree->pFreeNodeLink)
	{
		/* alloc extra memory to contain new node. */
		if(!l_avlAllocate(pTree, 1))
			return 0;
	}

	/* get a free node from queue */
	node = pTree->pFreeNodeLink;
	pTree->pFreeNodeLink = node->left;

	/* construct data of node */
	memset(node, 0, sizeof(PAVL_NODE));
	node->height = 0;
	node->bf = 0;
	node->weight = w;
	node->data = data;

	if(pTree->pRoot == NULL)
	{
		/* insert root node */
		pTree->pRoot = node;
	}
	else
	{
		child = pTree->pRoot;
		while(1)
		{
			nComparison = l_avlCompare(w, child->weight);
			if(nComparison == 0)
			{
				/* 找到了权值相等的结点，替换原来的数据 */
				pTree->dataBeforeInsert = child->data;
				child->data = data;
				nResult = 2;
				break;
			}
			else if (nComparison > 0)
			{
				/* the new node is greater, check whether the right sub-tree is empty or not */
				if(child->right == NULL)
				{
					child->right = node;
					node->parent = child;
					l_avlBalance(pTree, node, R_CHILD, 1);
					break;
				}
				else
				{
					child = child->right;
				}
			}
			else if (nComparison < 0)
			{
				/* the new node is smaller, check whether the left subtree is empty or not */
				if(child->left == NULL)
				{
					child->left = node;
					node->parent = child;
					l_avlBalance(pTree, node, L_CHILD, 1);
					break;
				}
				else
				{
					child = child->left;
				}
			}
		}
	}
	return nResult;
}

/* 如果 avlInsert 插入的结点的序号与原来的某个结点序号相同，则返回原结点的数据；
否则返回0
*/
unsigned long avlGetDataBeforeInsert(AVL_TREE_TYPE tree)
{
	AVL_TREE	*pTree = (AVL_TREE *)tree;
	if ( pTree )
		return pTree->dataBeforeInsert;
	return 0;
}

/* 从树中删除一个结点
参数：w : 要删除的结点的序号
返回值：0 - 失败，没有找到该结点
        1 - 成功
*/
int avlRemove(AVL_TREE_TYPE tree, int w)
{
	AVL_TREE	*pTree = (AVL_TREE *)tree;
	PAVL_NODE	child, parent, node;
	int			nComparison;

	if ( 0 == tree )
		return 0;

	child = pTree->pRoot;

	/* firstly, find out the node. */
	while(child && child->weight != w)
	{
		nComparison = l_avlCompare(w, child->weight);
		if(nComparison == 0) break;
		else if (nComparison > 0)
		{
			/* the new node is greater, check whether the right sub-tree is empty or not */
			if(child->right == NULL)
				return AVLFALSE;	/* not found */
			else
				child = child->right;
		}
		else if (nComparison < 0)
		{
			/* the new node is smaller, check whether the left subtree is empty or not */
			if(child->left == NULL)
				return AVLFALSE;	/*  not found */
			else
				child = child->left;
		}
	}

	/* secondly, remove the node and re-balance the tree. */
	parent = child->parent;
	if((child->left == NULL)||(child->right == NULL))
	{
		l_avlRemoveNodeFromTree(pTree, child);		/* just remove the node, without thinking balance. */
		if(parent)
			l_avlBalanceAfterRemove(pTree, parent);	/* balance the tree. */
		l_avlRelease(pTree, child);					/* release the memory for the node. */
	}
	else
	{
		/* replace the removed node with the lowest node in the right-subtree. */
		node = child->right;
		while(node->left) node = node->left;
		l_avlRemoveNodeFromTree(pTree, node);		/* just remove the node, without thinking balance. */
		if(node->parent)
			l_avlBalanceAfterRemove(pTree, node->parent);	/* balance the tree. */
		child->weight = node->weight;
		node->weight = w;
		l_avlRelease(pTree, node);					/* release the memory for the node. */
	}
	return AVLTRUE;
}

/* 查找某序号的结点
参数：w - 结点序号；
pData - 输出参数，用于获取结点的数据
返回值：0 - 没有找到；1 - 找到了
*/
int avlFind(AVL_TREE_TYPE tree, int w, unsigned long *pData)
{
	AVL_TREE	*pTree = (AVL_TREE *)tree;
	PAVL_NODE	node;
	node = l_avlFind(pTree, w);
	if ( node != NULL )
	{
		*pData = node->data;
		return 1;
	}
	return 0;
}


/*-------------------------------------*/

PAVL_NODE avlGetRootNode(AVL_TREE_TYPE tree)
{
	AVL_TREE	*pTree = (AVL_TREE *)tree;
	if ( tree == 0 )
		return 0;
	return pTree->pRoot;
}