avltree.cpp

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

#include "stdafx.h"


#include "AvlTree.h"


#define L_CHILD		1
#define R_CHILD		2
#define LR_CHILD	3
#define LL_CHILD	4
#define RL_CHILD	5
#define RR_CHILD	6


/* 
To avoid too many memory fragments, we allocate memory which is a multiple
of 4096 bytes for node one time, and don't free until the process is terminated.
*/
typedef struct _AVL_BUFFER{
	struct _AVL_BUFFER *Next;
	unsigned long dwBufferSize;
}AVL_BUFFER, *PAVL_BUFFER;



/* AVL_TREE_TYPE 所指的实际数据类型
*/
typedef struct _AVL_TREE
{
	PAVL_NODE	pRoot;				/* the root node. */
	PAVL_NODE	pFreeNodeLink;		/* free nodes linkage. */
	
	PAVL_BUFFER	pTreeBuffer;		/* point the root tree buffer */
	PAVL_BUFFER	pCurrentTreeBuffer;	/* point the current tree buffer */
	unsigned long dataBeforeInsert;	/* 如果一个插入的结点的序号与原来的某个结点序号相同，则这里保存原结点的数据 */
} AVL_TREE;


typedef int AVLBOOL;

#define AVLTRUE		1
#define AVLFALSE	0

#ifndef NULL
	#define NULL	0
#endif


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

/* l_avlAllocate buffer for node. */
static AVLBOOL l_avlAllocate(AVL_TREE *pTree, int NodeNums)
{
	int					i;
	PAVL_NODE			node, next;
	AVL_BUFFER			*treeBuffer;
	char				*buffer;
	unsigned long		bufferSize;

	bufferSize = NodeNums*sizeof(AVL_NODE);
	bufferSize += 4095;
	bufferSize >>= 12;
	bufferSize <<= 12;
	NodeNums = (bufferSize-sizeof(AVL_BUFFER)) / sizeof(AVL_NODE);

	/* alloc buffer for nodes */
	if(!(buffer = (char *)malloc(bufferSize)))
		return AVLFALSE;
	memset(buffer, 0, bufferSize);

	/* fill free nodes linkage */
	node = (PAVL_NODE)(buffer+sizeof(AVL_BUFFER));
	next = node + 1;
	pTree->pFreeNodeLink = node;
	for(i=0;i<NodeNums;i++)
	{
		node->left = next;
		node = next++;
	}

	/* record tree buffer */
	treeBuffer = (PAVL_BUFFER)buffer;
	treeBuffer->dwBufferSize = bufferSize;
	if(!pTree->pTreeBuffer)
	{
		pTree->pTreeBuffer = pTree->pCurrentTreeBuffer = treeBuffer;
	}
	else
	{
		pTree->pCurrentTreeBuffer->Next = treeBuffer;
		pTree->pCurrentTreeBuffer = treeBuffer;
	}

	return AVLTRUE;
}

/* compare two nodes. */
static int l_avlCompare(int Weight1, int Weight2)
{
	if(Weight1 > Weight2)
		return 1;
	else if (Weight1 == Weight2)
		return 0;
	else
		return -1;
}

/* 
LL rotate. We assumed that A node has a left-son named B and a right-son; and the B has 
a left-son and a right-son named C, which described as following:

          A                     B
         / \                  /   \
        B   Ar              Bl      A
       / \       ====>    /  \     / \
      Bl  C             Bll  Blr  C   Ar
     / \
    Bll Blr
*/
static AVLBOOL l_avlLLRotate(AVL_TREE *pTree, PAVL_NODE Node)
{
	PAVL_NODE b_node = Node->left;
	PAVL_NODE c_node = b_node->right;

	/* firstly, replace A with B. */
	if(Node->parent)
	{
		if(Node->parent->left == Node)
			Node->parent->left = b_node;
		else
			Node->parent->right = b_node;
	}
	else pTree->pRoot = b_node;

	b_node->parent = Node->parent;
	
	/* secondly, replace the right-son of B with A */
	b_node->right = Node;
	Node->parent = b_node;

	/* thirdly, replace the left-son of A with C */
	Node->left = c_node;
	if(c_node) c_node->parent = Node;

	/* at last, update the height and the balance factor of A and B */
	if(c_node)	
	{
		Node->height = (c_node->height >= Node->right->height)
			? (c_node->height+1) : (Node->right->height+1);
		Node->bf = c_node->height - Node->right->height;
	}
	else 
	{
		if(Node->right)
		{
			Node->height = 1;
			Node->bf = -1;
		}
		else
		{
			Node->height = 0;
			Node->bf = 0;
		}
	}

	b_node->height = (b_node->left->height >= Node->height)
		? (b_node->left->height+1) : (Node->height+1);
	b_node->bf = b_node->left->height - Node->height;

	return AVLTRUE;
}

/* 
LR rotate. We assumed A node has a left-son named B and a right-son; and the B has a 
left-son and a right-son named C, also, C has a left-son named D and right-son named E.

			A					 C
		   / \				   /   \	
		  B   Ar			  B	    A
		 / \		===>	 / \   / \
		Bl 	C				Bl  D E   Ar
        / \
		  D   E
*/
static AVLBOOL l_avlLRRotate(AVL_TREE *pTree, PAVL_NODE Node)
{
	PAVL_NODE b_node = Node->left;
	PAVL_NODE c_node = b_node->right;
	PAVL_NODE d_node = c_node->left;
	PAVL_NODE e_node = c_node->right;
	
	/* firstly, replace A with C. */
	if(Node->parent)
	{
		if(Node->parent->left == Node)
			Node->parent->left = c_node;
		else
			Node->parent->right = c_node;
	}
	else pTree->pRoot = c_node;
	c_node->parent = Node->parent;
	
	/* secondly, replace the left-son of C with B, and the right-son with A */
	c_node->left = b_node;
	c_node->right = Node;
	b_node->parent = Node->parent = c_node;
	
	/* thirdly, replace the left-son of A with E, the right-son of B with D */
	Node->left = e_node;
	if(e_node) e_node->parent = Node;
	b_node->right = d_node;
	if(d_node) d_node->parent = b_node;
	
	/* update the height and the balance factor of A, B and C */

	/* update b_node... */
	if(d_node)
	{
		b_node->height = (b_node->left->height >= d_node->height)
			? (b_node->left->height+1) : (d_node->height+1);
		b_node->bf = b_node->left->height - d_node->height;
	}
	else
	{
		if(b_node->left)
		{
			b_node->height = 1;
			b_node->bf = 1;
		}
		else
		{
			b_node->height = 0;
			b_node->bf = 0;
		}
	}

	/* update a_node... */
	if(e_node)
	{
		Node->height = (e_node->height >= Node->right->height)
			? (e_node->height+1) : (Node->right->height+1);
		Node->bf = e_node->height - Node->right->height;
	}
	else
	{
		if(Node->right)
		{
			Node->height = 1;
			Node->bf = -1;
		}
		else
		{
			Node->height = 0;
			Node->bf = 0;
		}
	}

	/* update c_node... */
	c_node->height = (b_node->height >= Node->height)
		? (b_node->height+1) : (Node->height+1);
	c_node->bf = b_node->height - Node->height;

	return AVLTRUE;
}

/* 
RL rotate. We assume that the tree is looked like as the following:

          A                        C
         / \                     /   \
        Al  B                   A     B
           / \       ====>     / \   / \
          C   Br              Al  D E   Br
         / \
        D   E
*/
static AVLBOOL l_avlRLRotate(AVL_TREE *pTree, PAVL_NODE Node)
{
	PAVL_NODE b_node = Node->right;
	PAVL_NODE c_node = b_node->left;
	PAVL_NODE d_node = c_node->left;
	PAVL_NODE e_node = c_node->right;
	
	/* firstly, replace A with C. */
	if(Node->parent)
	{
		if(Node->parent->left == Node)
			Node->parent->left = c_node;
		else
			Node->parent->right = c_node;
	}
	else pTree->pRoot = c_node;
	c_node->parent = Node->parent;
	
	/* secondly, replace the left-son of C with A, and the right-son with B */
	c_node->left = Node;
	c_node->right = b_node;
	Node->parent = b_node->parent = c_node;
	
	/* thirdly, replace the right-son of A with D, the left-son of B with E */
	Node->right = d_node;
	if(d_node) d_node->parent = Node;
	b_node->left = e_node;
	if(e_node) e_node->parent = b_node;
	
	/* update the height and the balance factor of A, B and C */

	/* update a_node... */
	if(d_node)
	{
		Node->height = (Node->left->height >= d_node->height)
			? (Node->left->height+1) : (d_node->height+1);
		Node->bf = Node->left->height - d_node->height;
	}
	else
	{
		if(Node->left)
		{
			Node->height = 1;
			Node->bf = 1;
		}
		else
		{
			Node->height = 0;
			Node->bf = 0;
		}
	}

	/* update b_node... */
	if(e_node)
	{
		b_node->height = (e_node->height >= b_node->right->height)
			? (e_node->height+1) : (b_node->right->height+1);
		b_node->bf = e_node->height - b_node->right->height;
	}
	else
	{
		if(b_node->right)
		{
			b_node->height = 1;
			b_node->bf = -1;
		}
		else
		{
			b_node->height = 0;
			b_node->bf = 0;
		}
	}
	
	/* update c_node... */
	c_node->height = (Node->height >= b_node->height)
		? (Node->height+1) : (b_node->height+1);
	c_node->bf = Node->height - b_node->height;

	return AVLTRUE;
}

/* 
RR rotate. We assume that the tree is looked like as the following:

          A                        B
         / \                     /   \
        Al  B                   A     Br
           / \       ====>     / \   / \
          C   Br              Al  C Brl Brr
             / \
           Brl Brr
*/
static AVLBOOL l_avlRRRotate(AVL_TREE *pTree, PAVL_NODE Node)
{
	PAVL_NODE b_node = Node->right;
	PAVL_NODE c_node = b_node->left;
	
	/* firstly, replace A with B. */
	if(Node->parent)
	{
		if(Node->parent->left == Node)
			Node->parent->left = b_node;
		else
			Node->parent->right = b_node;
	}
	else pTree->pRoot = b_node;
	b_node->parent = Node->parent;
	
	/* secondly, replace the left-son of B with A */
	b_node->left = Node;
	Node->parent = b_node;
	
	/* thirdly, replace the right-son of A with C */
	Node->right = c_node;
	if(c_node) c_node->parent = Node;
	
	/* at last, update the height and the balance factor of A and B */
	/* c_node => Node->left is valid */
	if(c_node)
	{
		Node->height = (Node->left->height >= c_node->height)
			? (Node->left->height+1) : (c_node->height+1);
		Node->bf = Node->left->height - c_node->height;
	}
	else
	{
		if(Node->left)
		{
			Node->height = 1;
			Node->bf = 1;
		}
		else
		{
			Node->height = 0;
			Node->bf = 0;
		}
	}

	b_node->height = (Node->height >= b_node->right->height)
		? (Node->height+1) : (b_node->right->height+1);
	b_node->bf = Node->height - b_node->right->height;
	
	return AVLTRUE;
}

/* balance the bi-tree */
static AVLBOOL l_avlBalance(AVL_TREE *pTree, PAVL_NODE Child, unsigned long RotateType, int height)
{
	PAVL_NODE node;