avl.c

常用数据结构算法代码库

/****************************************************************************
*
*					Copyright (C) 1991 Kendall Bennett.
*							All rights reserved.
*
* Filename:		$RCSfile: avl.c $
* Version:		$Revision: 1.3 $
*
* Language:		ANSI C
* Environment:	any
*
* Description:	Module to implement balanced AVL trees.
*
* $Id: avl.c 1.3 91/12/31 19:40:43 kjb Exp $
*
* Revision History:
* -----------------
*
* $Log:	avl.c $
* Revision 1.3  91/12/31  19:40:43  kjb
* Modified include file directories
* 
* Revision 1.2  91/09/27  03:10:00  kjb
* Added stuff keep track of the number of nodes in the tree.
* 
* Revision 1.1  91/09/27  02:50:49  kjb
* Initial revision
* 
****************************************************************************/

#include <stdio.h>
#include <malloc.h>
#include <signal.h>
#include "debug.h"
#include "avl.h"

/*--------------------------- Globals Variables ---------------------------*/

PRIVATE AVL_TREE	*Tree;		/* Pointer to tree we are working with	*/
PRIVATE	AVL_BUCKET	*Node;		/* Pointer to node we are working with	*/
PRIVATE void		*Conflicting;	/* Conflicting node 				*/
PRIVATE bool		Notfound;	/* Flags if a node cannot be found		*/
PRIVATE void 		(*Visit)(void*,void*);
PRIVATE void		(*Prnt)(FILE*,void*);
PRIVATE	void		*Params,*Lower,*Upper;
PRIVATE	FILE*		Out;
PRIVATE char		Map[MAXLEVEL / 8];
PRIVATE	char		*Graph_chars[] = { "|","+--","+--","--+","--+","--+"};
PRIVATE	char		*Norm_chars[] = { "|","+--","+--","--+","--+","--+"};
PRIVATE	char		**Cset;

/*----------------------------- Implementation ----------------------------*/

PUBLIC void *avl_newnode(int size)
/****************************************************************************
*
* Function:		avl_newnode
* Parameters:	size	- Amount of memory to allocate for node
* Returns:		Pointer to the allocated nodes user space.
*
* Description:	Allocates the memory required for a node, adding a small
*				header at the start of the node. We return a reference to
*				the user space of the node, as if it had be allocated via
*				malloc.
*
****************************************************************************/
{
	AVL_BUCKET	*n;

	if ( !(n = (AVL_BUCKET*)malloc(size+sizeof(AVL_BUCKET))) ) {
		fprintf(stderr,"Can't get memory for BUCKET\n");
		raise(SIGABRT);
		return NULL;
		}

	return AVL_USERSPACE(n);		/* Return pointer to user space		*/
}

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

PUBLIC void avl_freenode(void *node)
/****************************************************************************
*
* Function:		avl_freesym
* Parameters:	node	- Node to free
*
* Description:	Frees a node previously allocated with avl_newsym().
*
****************************************************************************/
{
	free(AVL_HEADER(node));
}

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

PUBLIC AVL_TREE *avl_init( int (*cmp_function)(void*, void*) )
/****************************************************************************
*
* Function:		avl_init
* Parameters:	cmp_function	- Function to compare the value of two nodes
*				prnt_function	- Function to print the value of a node
* Returns:		Pointer to the newly created AVL tree.
*
* Description:	Makes a new AVL tree with no elements and returns a pointer
*				to it.
*
****************************************************************************/
{
	AVL_TREE	*tree;

	if( (tree = (AVL_TREE*)malloc(sizeof(AVL_TREE))) != NULL) {
		tree->count = 0;
		tree->cmp = cmp_function;
		tree->root = NULL;
		}
	else {
		fprintf(stderr,"Insufficient memory for AVL tree\n");
		raise(SIGABRT);
		return NULL;
		}
	return tree;
}

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

PRIVATE void (*_freeNode)(void*);

PRIVATE void free_subtree(AVL_BUCKET *t)
/****************************************************************************
*
* Function:		free_subtree
* Parameters:	t	- Subtree to free
*
* Description:	Recursive routine to free the elements of a particular
*				subtree.
*
****************************************************************************/
{
	if (t) {
		free_subtree(t->left);
		free_subtree(t->right);
		_freeNode(AVL_USERSPACE(t));
		}
}

PUBLIC void avl_empty(AVL_TREE *t, void (*freeNode)(void*))
/****************************************************************************
*
* Function:		avl_empty
* Parameters:	t			- Tree to kill
*				freeNode	- Routine to free each node of the tree
*
* Description:	Deletes the entire AVL tree from memory including all the
*				nodes of the tree. We call the user supplied routine
*				freeNode() to free each node in the tree. This allows the
*				user program to perform any extra processing that is
*				required to kill each node (for example if they contain
*				pointers to other items on the heap). If no extra
*				processing is required, just pass the address of
*				avl_freenode(), ie:
*
*					avl_kill(myTree,avl_freenode);
*
****************************************************************************/
{
	_freeNode = freeNode;
	free_subtree(t->root);
	t->root = NULL;
}

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

PRIVATE void insert(AVL_BUCKET **pp)
/****************************************************************************
*
* Function:		insert
* Parameters:	pp	- Pointer to pointer to root of subtree to insert into
*
* Description:	Internal recursive routine to insert a node into an
*				AVL tree. Expects the global variables Tree, and Node
*				to be set up. If we encounter a duplicate key, we return
*				the address of this key in the global Conflicting;
*
****************************************************************************/
{
	AVL_BUCKET	*p = *pp;
	AVL_BUCKET	*p1,*p2;
	int			relation;	/* Relationship between root and Node		*/
	static bool	h = 0;			/* Set to indicate that subtree has grown	*/

	if (p == NULL) {

		/* We have found a valid spot for the node, so insert it and
		 * let the higher level recursions know that the tree has
		 * subsequently grown.
		 */

		p = Node;
		p->left = p->right = NULL;
		p->bal = BAL;
		h = true;
		}
	else if ((relation = Tree->cmp(AVL_USERSPACE(p),
			AVL_USERSPACE(Node))) == 0) {

		/* We have a node with a duplicate key that we cannot insert
		 * into the tree. We return the address of the user space for
		 * the node in the global Conflicting
		 */

		Conflicting = AVL_USERSPACE(p);
		h = false;
		}
	else if (relation > 0) {

		/* If relation is > 0, then the current node p is greater than
		 * Node, so we insert the node into the left subtree.
		 */

		insert(&p->left);

		if (h) {				/* The left subtree has grown in height	*/
			switch (p->bal) {
				case LH:

					/* The left subtree has grown taller than it is allowed,
					 * so we must perform a rebalance of the tree.
					 */

					p1 = p->left;
					if (p1->bal == LH) {

						/* Left subtree is LEFTHIGH, so we need to do a
						 * single right rotation to rebalance the subtree p.
						 */

						p->left = p1->right;
						p1->right = p;
						p->bal = BAL;
						p = p1;
						}
					else {

						/* Left subtree is RIGHTHIGH, so we need to do a
						 * double right rotation to rebalance the subtree p.
						 */

						p2 = p1->right;
						p1->right = p2->left;
						p2->left = p1;
						p->left = p2->right;
						p2->right = p;
						p->bal = (p2->bal == LH) ? RH : BAL;
						p1->bal = (p2->bal == RH) ? LH : BAL;
						p = p2;
						}
					p->bal = BAL;			/* Tree is now balanced		*/
					h = 0;
					break;
				case BAL:

					/* The subtree was previously balanced, so now it
					 * simply becomes LEFTHIGH.
					 */

					p->bal = LH;
					break;
				case RH:

					/* The subtree was previously RIGHTHIGH, so now it
					 * has become balanced. In this case the height of this
					 * particular subtree has not grown, so h is reset to
					 * false.
					 */

					p->bal = BAL;
					h = false;
				}
			}
		}
	else {

		/* Relation was < 0, indicating that the current node p is smaller
		 * than Node, so we insert the new node into the right subtree.
		 */

		insert(&p->right);

		if (h) {			/* The right subtree has grown in height	*/
			switch (p->bal) {
				case LH:

					/* The subtree was previously LEFTHIGH, so now it
					 * has become balanced. In this case the height of this
					 * particular subtree has not grown, so h is reset to
					 * false.
					 */

					p->bal = BAL;
					h = false;
					break;
				case BAL:

					/* The subtree was previously balanced, so now it
					 * simply becomes RIGHTHIGH.
					 */

					p->bal = RH;
					break;
				case RH:

					/* The right subtree has grown taller than it is allowed,
					 * so we must perform a rebalance of the tree.
					 */

					p1 = p->right;
					if (p1->bal == RH) {

						/* Right subtree is RIGHTHIGH, so we need to do a
						 * single left rotation to rebalance the subtree p.
						 */

						p->right = p1->left;
						p1->left = p;
						p->bal = BAL;
						p = p1;
						}
					else {

						/* Right subtree is LEFTHIGH, so we need to do a
						 * double left rotation to rebalance the subtree p.
						 */

						p2 = p1->left;
						p1->left = p2->right;
						p2->right = p1;
						p->right = p2->left;
						p2->left = p;
						p->bal = (p2->bal == RH) ? LH : BAL;
						p1->bal = (p2->bal == LH) ? RH : BAL;
						p = p2;
						}
					p->bal = BAL;			/* Tree is now balanced		*/
					h = 0;
				}
			}
		}

	/* Reset the root of this subtree to the new root p, since it may have
	 * changed during a rotate of the tree.
	 */

	*pp = p;
}

PUBLIC void *avl_insert(AVL_TREE *tree, void *node)
/****************************************************************************
*
* Function:		avl_insert
* Parameters:	tree	- Tree to insert the node into
*				node	- New node to insert into the tree
* Returns:		NULL on success, or a pointer to the conflicting node.
*
* Description:	Inserts a new node into an AVL tree. Duplicate keys are
*				currently not supported.
*
****************************************************************************/
{
	Tree = tree;
	Node = AVL_HEADER(node);
	Conflicting = NULL;

	insert(&tree->root);
	if (!Conflicting)	tree->count++;

	return Conflicting;
}

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

PRIVATE bool balance_left(AVL_BUCKET **pp)
/****************************************************************************
*
* Function:		balance_left
* Parameters:	pp	- Point to root of subtree to balance
* Returns:		True if the entire subtree shrank, false if not
*
* Description:	Routine to rebalance the subtree pointed to by pp when its
*				left subtree has just shrunk. We adjust the balance factors
*				and rebalance the subtree adjusting pp to point to the
*				new root of the subtree.
*
****************************************************************************/
{
	AVL_BUCKET	*p,*p1,*p2;
	short		b1,b2;
	bool		subtree_shrank = true;

	p = *pp;
	switch (p->bal) {
		case LH:

			/* The subtree was previously left high. Since the left subtree
			 * just shrank, this tree is now balanced while the overall
			 * height has been reduced.
			 */

			p->bal = BAL;
			break;
		case BAL:

			/* The subtree was previously balanced, so we simply make
			 * it right high, and signal that it did not shrink.
			 */

			p->bal = RH;
			subtree_shrank = false;
			break;
		case RH:

			/* The subtree was previously right high. In this case we must do
			 * either a single or double left rotation. If the right
			 * subtree was balanced or right high, we only need a single
			 * left rotation. We do a double left rotate if the right subtree
			 * was left high.
			 */

			p1 = p->right;
			b1 = p1->bal;
			if (b1 >= BAL) {
				p->right = p1->left;		/* Single left rotatation	*/
				p1->left = p;
				if (b1 == RH)
					p->bal = p1->bal = BAL;
				else {
					p->bal = RH;
					p1->bal = LH;
					subtree_shrank = false;
					}
				p = p1;					/* Right subtree is new root	*/
				}
			else {
				p2 = p1->left;				/* Double left rotation		*/
				b2 = p2->bal;
				p1->left = p2->right;
				p2->right = p1;
				p->right = p2->left;
				p2->left = p;
				p->bal = (b2 == RH) ? LH : BAL;
				p1->bal = (b2 == LH) ? RH : BAL;
				p2->bal = BAL;
				p = p2;
				}
		}
	*pp = p;
	return subtree_shrank;
}

PRIVATE bool balance_right(AVL_BUCKET **pp)
/****************************************************************************
*
* Function:		balance_right
* Parameters:	pp	- Point to root of subtree to balance
* Returns:		True if the entire subtree shrank, false if not
*
* Description:	Routine to rebalance the subtree pointed to by pp when its
*				right subtree has just shrunk. We adjust the balance factors
*				and rebalance the subtree adjusting pp to point to the
*				new root of the subtree.
*
****************************************************************************/
{
	AVL_BUCKET	*p,*p1,*p2;
	short		b1, b2;
	bool		subtree_shrank = true;

	p = *pp;
	switch (p->bal) {
		case RH:

			/* The subtree was previously right high. Since the right subtree
			 * just shrank, this tree is now balanced while the overall
			 * height has been reduced.
			 */

			p->bal = BAL;
			break;
		case BAL:

			/* The subtree was previously balanced, so we simply make
			 * it right high, and signal that it did not shrink.
			 */

			p->bal = LH;
			subtree_shrank = false;
			break;
		case LH:

			/* The subtree was previously left high. In this case we must do
			 * either a single or double right rotation. If the left
			 * subtree was balanced or left high, we only need a single
			 * right rotation. We do a double right rotate if the left
			 * subtree was right high.
			 */

			p1 = p->left;
			b1 = p1->bal;
			if (b1 <= BAL) {
				p->left = p1->right;		/* Single right rotation	*/
				p1->right = p;
				if (b1 == LH)
					p->bal = p1->bal = BAL;
				else {
					p->bal = LH;
					p1->bal = RH;
					subtree_shrank = true;
					}
				p = p1;
				}
			else {
				p2 = p1->right;				/* Double right rotation	*/
				b2 = p2->bal;
				p1->right = p2->left;
				p2->left = p1;
				p->left = p2->right;
				p2->right = p;