avl.c

常用数据结构算法代码库

				p->bal = (b2 == LH) ? LH : BAL;
				p1->bal = (b2 == RH) ? RH : BAL;
				p2->bal = BAL;
				p = p2;
				}
		}
	*pp = p;
	return subtree_shrank;
}

PRIVATE bool descend(AVL_BUCKET **rootp, AVL_BUCKET **pp)
/****************************************************************************
*
* Function:		descend
* Parameters:	rootp	- Pointer to pointer to tree to descend
*				pp		- Pointer to pointer to node to replace
* Returns:		True if the subtree just shrank, false if not.
*
* Description:	Routine to descend to the rightmost node of the left
*				subtree. When we get there, we move it up into the position
*				occupied by pp (retaining pp's balance factor) and delete
*				this node. On the way back we rebalance the tree if
*				necessary.
*
****************************************************************************/
{
	AVL_BUCKET	*p = *rootp;
	bool		has_shrunk,was_left = 0;

	if (p->right) {

		/* Continue to descend the right subtree, until we can go no
		 * further. On the way back up the recursion, if the tree has
		 * shrunk, we rebalance it.
		 */

		if (rootp == &(*pp)->left)
			was_left = true;
		has_shrunk = descend(&p->right,pp);
		if (was_left)
			rootp = &(*pp)->left;
		return has_shrunk ? balance_right(rootp) : 0;
		}
	else {
		*rootp = p->left;			/* Kill the old link to p			*/

		p->bal = (*pp)->bal;		/* Retain the old balance factor	*/
		p->left = (*pp)->left;		/* and links						*/
		p->right = (*pp)->right;
		Node = *pp;					/* Free the node					*/
		*pp = p;					/* Replace with p					*/
		return true;				/* Subtree has shrunk - rebalance	*/
		}
}

PRIVATE bool delete(AVL_BUCKET **pp)
/****************************************************************************
*
* Function:		delete
* Parameters:	pp	- Pointer to pointer to root of subtree to delete from
* Returns:		True if the subtree shrunk in size, false if not.
*
* Description:	Internal recursive routine to delete a node from an
*				AVL tree. Expects the global variables Tree, and Node
*				to be set up. If the node is not found, we set the global
*				Notfound to true.
*
****************************************************************************/
{
	AVL_BUCKET	*p = *pp;
	int			relation;

	if (p == NULL) {

		/* We could not locate the node in the tree, so set Notfound to
		 * true.
		 */

		Notfound = true;
		return false;
		}
	else if ((relation = Tree->cmp(AVL_USERSPACE(p),
			AVL_USERSPACE(Node))) == 0) {

		/* We have found the node, so delete it from the tree.
		 */

		if (p->right == NULL) {

			/* There is only a single left node in the tree, so move this
			 * node up to where p used to be, and then delete p.
			 */

			*pp = p->left;
			Node = p;
			return true;
			}
		else if (p->left == NULL) {

			/* There is only a single right node in the tree, so move this
			 * node up to where p used to be, and then delete p.
			 */

			*pp = p->right;
			Node = p;
			return true;
			}
		else if (descend(&p->left,pp))
			return balance_left(pp);
		}
	else if (relation > 0) {

		/* If relation is > 0, then the current node p is greater than
		 * Node, so we delete node from the left subtree. If the left
		 * subtree has shrunk in size, we rebalance the tree and return
		 * the result of this rebalance (tree shrunk, or stayed the same
		 * size).
		 */

		if (delete(&p->left))
			return balance_left(pp);
		}
	else {

		/* If relation is < 0, then the current node p is less than
		 * Node, so we delete node from the right subtree. If the right
		 * subtree has shrunk in size, we rebalance the tree and return
		 * the result of this rebalance (tree shrunk, or stayed the same
		 * size).
		 */

		if (delete(&p->right))
			return balance_right(pp);
		}
	return false;
}

PUBLIC void *avl_delete(AVL_TREE *tree, void *node)
/****************************************************************************
*
* Function:		avl_delete
* Parameters:	tree	- Tree to delete node from
*				node	- Node to delete from tree
* Returns:		Pointer to the node if successful, NULL of failure
*
* Description:	Deletes a node from an AVL tree. The node is removed from
*				the tree, but it's memory is not released. You must call
*				avl_freenode() to free the nodes memory.
*
****************************************************************************/
{
	Tree = tree;
	Node = AVL_HEADER(node);
	Notfound = false;

	delete(&tree->root);
	if (!Notfound)	tree->count--;

	return Notfound ? NULL : AVL_USERSPACE(Node);
}

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

PRIVATE void pre_order(AVL_BUCKET *p)
{
	if (p) {
		Visit(Params,AVL_USERSPACE(p));
		pre_order(p->left);
		pre_order(p->right);
		}
}

PRIVATE void in_order(AVL_BUCKET *p)
{
	if (p) {
		in_order(p->left);
		Visit(Params,AVL_USERSPACE(p));
		in_order(p->right);
		}
}

PRIVATE void post_order(AVL_BUCKET *p)
{
	if (p) {
		post_order(p->left);
		post_order(p->right);
		Visit(Params,AVL_USERSPACE(p));
		}
}

PUBLIC void avl_traverse(AVL_TREE *tree, int order, void (*visit)(void*, void*),
	void *params)
/****************************************************************************
*
* Function:		avl_preorder
* Parameters:	tree	- Tree to traverse
*
* Description:	Traverses the AVL tree in a pre-order fashion, visiting
*				the node first, then the left and then the right subtree.
*
*				The function visit() must accept two parameters. The second
*				is a pointer to the node to visit, while the first is the
*				params argument passed to avl_traverse.
*
****************************************************************************/
{
	Visit = visit;
	Params = params;
	switch (order) {
		case PREORDER:
			pre_order(tree->root);
			break;
		case INORDER:
			in_order(tree->root);
			break;
		case POSTORDER:
			post_order(tree->root);
		}
}

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

/* Macro to test if the depth bit for level c is set	*/

#define testbit(level)	(Map[level >> 3] & (1 << (level & 0x07)))

#ifdef DEBUG
#define  PAD()    fprintf(Out,"   ");
#define  PBAL(r)  fprintf(Out,"(%c)", r->bal == BAL ? 'B' : r->bal==LH ? 'L' : 'R');
#else
#define  PAD()
#define  PBAL(r)
#endif

PRIVATE void setbit(int level, bool set_it)
/****************************************************************************
*
* Function:		setbit
* Parameters:	depth	- Depth of bit to set
*				set_it	- True to set bit, false to reset it
*
* Description:	Sets or resets the depth bit for a level. If this bit is
*				set, we we draw a vertical line at that depth level.
*
****************************************************************************/
{
	if (set_it)
		Map[level >> 3] |= 1 << (level & 0x07);
	else
		Map[level >> 3] &= ~(1 << (level & 0x07));
}

PRIVATE void print_tree(AVL_BUCKET *root, int left_subtree)
/****************************************************************************
*
* Function:		print_tree
* Parameters:	root			- Root of subtree to display
*				left_subtree	- True if this is a left subtree
*
* Description:	Dumps the contents of subtree 'root' to the file Out.
*
****************************************************************************/
{
	static int	depth = -1;			/* Current depth within subtree		*/
	int			i;

	if (root) {
		depth++;

		if(root->right)
			print_tree(root->right,false);
		else
			setbit(depth+1,true);

		for(i = 1; i <= depth; i++) {
			Prnt(Out,NULL);
			PAD();

			if (i == depth)
				fprintf(Out,"  %s", left_subtree ? Cset[2] : Cset[1]);
			else if(testbit(i))
				fprintf(Out,"  %s  ", Cset[0]);
			else
				fprintf(Out,"     ");
			}

		Prnt(Out,AVL_USERSPACE(root));
		PBAL(root);
		fprintf(Out,"%s\n",root->left ? (root->right ? Cset[3] : Cset[5]) :
			(root->right ? Cset[4] : ""));

		setbit(depth,left_subtree ? false : true);

		if(root->left)
			print_tree(root->left,true);
		else
			setbit(depth+1,false);
		depth--;
		}
}

PUBLIC void avl_print(FILE *out, AVL_TREE *tree, void (*prnt)(FILE*, void*),
	bool graph_chars)
/****************************************************************************
*
* Function:		avl_print
* Parameters:	out				- Stream to print to
*				tree			- Tree to print out
*				prnt			- Routine to print each node
*				graph_chars		- True if we print with graphics characters
*
* Description:	Dumps the contents of the AVL tree to the specified file.
*				If graph_chars is true, the structure of the tree is
*				printed using IBM graphics characters, otherwise it is
*				printed using standard ASCII characters. If show_balance
*				is true, the balance factors are displayed.
*
*				The routine prnt() takes a pointer to a file to print the
*				node to, and a pointer to the node to print. It must print
*				every node in a field of the same width, and when passed
*				a null pointer for the node it should print a blank field
*				the same width as the nodes. This provides correct
*				formatting for the printed tree.
*
*				The tree can have a maximum height of 64 levels. If the
*				tree is taller than this, the result is undefined. A
*				balanced AVL tree with 64 levels would have in the order
*				of 1e19 nodes!
*
****************************************************************************/
{
	Tree = tree;
	Out = out;
	Prnt = prnt;
	Cset = graph_chars ? Graph_chars : Norm_chars;
	print_tree(tree->root,false);
}

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

PUBLIC void *avl_findsym(AVL_TREE *tree, void *node)
/****************************************************************************
*
* Function:		avl_findsym
* Parameters:	tree	- Tree to search for the symbol
*				node	- Node containing key to search for
* Returns:		Pointer to the node if found, NULL if not.
*
* Description:	Searches the AVL tree for the specified node and returns
*				it if it is found.
*
****************************************************************************/
{
	AVL_BUCKET	*p;
	int			relation;

	p = tree->root;

	while (p) {
		if ((relation = tree->cmp(node,AVL_USERSPACE(p))) == 0)
			return AVL_USERSPACE(p);
		else if (relation > 0)
			p = p->right;
		else
			p = p->left;
		}
	return NULL;
}

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

PRIVATE void range_search(AVL_BUCKET *root)
/****************************************************************************
*
* Function:		range_search
* Parameters:	root	- Root of subtree to range search
*
* Description:	Recursive routine to range search a subtree.
*
****************************************************************************/
{
	if (root) {
		if (Tree->cmp(AVL_USERSPACE(root),Lower) < 0) {
			/* If the root node is smaller than the lower bound, then recurse
			 * down the right subtree.
			 */

			range_search(root->right);
			}
		else if (Tree->cmp(AVL_USERSPACE(root),Upper) > 0) {
			/* If the root node is larger than the lower bound, then recurse
			 * down the left subtree.
			 */

			range_search(root->left);
			}
		else {
			/* We are within the range so recurse down the left subtree,
			 * visit the node and then recurse down the right subtree.
			 */

			range_search(root->left);
			Visit(Params,AVL_USERSPACE(root));
			range_search(root->right);
			}
		}
}

PUBLIC void avl_range(AVL_TREE *tree, void *lower, void *upper,
	void (*visit)(void*, void*), void *params)
/****************************************************************************
*
* Function:		avl_range
* Parameters:	tree	- Tree to range search
*				lower	- Lower bound of range search (inclusive)
*				upper	- Upper bound of range search (inclusive)
*				visit	- Function to visit each node in range
*				params	- Parameters for the visit routine.
*
* Description:	Calls visit for every node in the range [lower,upper]
*				for the AVL tree 'tree'. Visit must accept two parameters.
*				The first is the params argument passed to this function,
*				while the second is a pointer to the node to visit.
*
****************************************************************************/
{
	Tree = tree;
	Visit = visit;
	Params = params;
	Lower = lower;
	Upper = upper;
	range_search(tree->root);
}

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

int delmin(AVL_BUCKET **pp)
/****************************************************************************
*
* Function:		delmin
* Parameters:	root	- Root of subtree to delete from
* Returns:		True if the subtree shrank.
*
* Description:	Recursive routine to delete the smallest node from an
*				AVL tree.
*
****************************************************************************/
{
	AVL_BUCKET	*p = *pp;

	if (p->left)
		return delmin(&p->left) ? balance_left(pp) : 0;
	else {
		*pp = p->right;		/* Delete the node		*/
		Node = p;
		return true;		/* Subtree just shrank	*/
		}
}

PUBLIC void *avl_delmin(AVL_TREE *tree)
/****************************************************************************
*
* Function:		avl_delmin
* Parameters:	tree	- Tree to delete node from
* Returns:		Pointer to the node found, or NULL on error.
*
* Description:	Deletes (removes) the smallest node from an AVL tree. The
*				tree is rebalanced if need be. Note that the node is not
*				freed. You will need to call avl_freenode() to do this.
*
****************************************************************************/
{
	Node = NULL;
	delmin(&tree->root);
	if (Node)	tree->count--;
	return Node ? AVL_USERSPACE(Node) : NULL;
}

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

int delmax(AVL_BUCKET **pp)
/****************************************************************************
*
* Function:		delmax
* Parameters:	root	- Root of subtree to delete from
* Returns:		True if the subtree shrank.
*
* Description:	Recursive routine to delete the largest node from an
*				AVL tree.
*
****************************************************************************/
{
	AVL_BUCKET	*p = *pp;

	if (p->right)
		return delmax(&p->right) ? balance_right(pp) : 0;
	else {
		*pp = p->left;		/* Delete the node		*/
		Node = p;
		return true;		/* Subtree just shrank	*/
		}
}

PUBLIC void *avl_delmax(AVL_TREE *tree)
/****************************************************************************
*
* Function:		avl_delmax
* Parameters:	tree	- Tree to delete node from
* Returns:		Pointer to the node found, or NULL on error.
*
* Description:	Deletes (removes) the largest node from an AVL tree. The
*				tree is rebalanced if need be. Note that the node is not
*				freed. You will need to call avl_freenode() to do this.
*
****************************************************************************/
{
	Node = NULL;
	delmax(&tree->root);
	if (Node)	tree->count--;
	return Node ? AVL_USERSPACE(Node) : NULL;
}

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