红黑树是一种二叉查找树，但在每个节点上增加一个存储位表示节点的颜色，可以是RED或BLACK，通过对任意一条从根到叶子的路径上各个节点着色方式的限制，红黑树确保没有一条路径会比其他路径长出两倍，因而是接近平衡的。

红黑树包含5个域：element,left,right,parent,color，如果某个节点没有一个字节点或者节点，则该节点相应的指针Parent为NIL。

红黑树的5个性质：

1、每个节点是红色或者黑色的;
2、根节点是黑色的;
3、每个叶节点NIL是黑的;
4、 如果一个节点是红的，则它的两个儿子都是黑的;
5、对每个节点，从该节点到其子孙节点的所有路径上包含相同数目的黑节点.

头文件_RBTree.h

#ifndef _RBTree_H

struct RBNode;
typedef struct AvlNode *Position;
typedef struct AvlNode *RBTree;

RBTree MakeEmpty( RBTree T );
Position Find( ElementType X, RBTree T );
Position FindMin( RBTree T );
RBTree Insert( ElementType X, RBTree T );
void InsertFixup( RBTree T, Position P );
RBTree Delete( ElementType X, RBTree T );
void DeleteFixup( RBTree T, Position P );

#endif /* _RBTree_H */

/* Place in the implementation file */
struct RBNode
{
	ElementType Element;
	RBTree Left;
	RBTree Right;
	RBTree Parent;
	char Color;
}

主要例程_RBTree.c

static Position NilPosition = CreateNilNode();
Position Find( ElementType X, RBTree T )
{
	if( T == NULL )
		return NULL;
	if( X > T->Element )
		return Find( X, T->Right );
	else
		if( X < T->Element )
			return Find( X, T->Left );
		else
			return T;
}

Position FindMin( RBTree T )
{
	if( T != NULL )
		while( T->Left != NULL )
			T = T->Left;
	
	return T;
}

RBTree Insert( ElementType X, RBTree T )
{
	Position P;

	if( T == NULL )
		T = CreateNode( ElementType X );
	else
	{
		P = T;
		/* while( P->Left != NilPosition && P->Right != NilPosition ) */
		while( 1 )
		{
			if( P->Element > X )
			{
				if( P->Left == NilPosition )
					break;
				P = P->Left;
			}
			else
				if( P->Element < X )
				{
					if( P->Right == NilPosition )
						break;
					P = P->Right;
				}
				/* Else element is in the tree, do nothing */
		}
		
		if( P->Element > X )
		{
			P->Left = CreateNode( ElementType X );
			P->Left->Parent = P;
			P = P->Left;
		}
		else
			if( P->Element < X )
			{
				P->Right = CreateNode( ElementType X );
				P->Right->Parent = P;
				P = P->Right;
			}

		InsertFixup( T, P );
	}
	
	return T;
}

/* 情况1:P的叔叔Y是红色的 */
/* 情况2:P的叔叔Y是黑色的，且P是右孩子 */
/* 情况3:P的叔叔Y是红色的，且P是左孩子 */
void InsertFixup( RBTree T, Position P )
{
	Position Y;
	while( P->Parent->Color == 'R' )
	{
		if( P->Parent == P->Parent->Parent->Left )
		{
			Y = P->Parent->Parent->Right;
			if( Y->Color == "R" )
			{
				P->Parent->Color = "B";
				Y->Color = "B";
				P->Parent->Parent->Color = "R";
				P = P->Parent->Parent;
			}
			else
			{
				if( P == P->Parent->Right )
				{
					P = P->Parent;
					SingleRotateWithRight( T, P );
				}
				else
				{
					P->Parent->Color = "B";
					P->Parent->Parent->Color = "R";
					SingleRotateWithLeft( P->Parent->Parent );
				}
			}
		}
		else
			if( P->Parent == P->Parent->Parent->Right )
			{
				Y = P->Parent->Parent->Left;
				if( Y->Colr == "R" )
				{
					P->Parent->Color = "B";
					Y->Color = "B";
					P->Parent->Parent->Color = "R";
					P = P->Parent->Parent;
				}
				else
				{
					if( P == P->Parent->Left )
					{
						P = P->Parent;
						SingleRotateWithLeft( T, P );
					}
					else
					{
						P->Parent->Color = "B";
						P->Parent->Parent->Color = "R";
						SingleRotateWithRight( P->Parent->Parent );
					}
				}
			}
	}
}

RBTree Delete( ElementType X, RBTree T )
{
	Position P, Y;
	P = Find( X, T );
	if( P->Left == NilPosition || P->Right = NilPosition )
		Y = P;
	else
		Y = FindMin( P->Right );

	if( Y->Left != NilPosition )
		W = Y->Left;
	else
		W = Y->Right;

	W->Parent = Y->Parent;

	if( Y->Parent == NilPosition )
		T = W;
	else
		if( Y == Y->Parent->Left )
			Y->Parent->Left = W;
		else
			Y->Parent->Right = W;

	if( Y != P )
		P->Element = Y->Element;

	if( Y->Color == "B" )
		DeleteFixup( W, T );

	return Y;
}

/* 情况1: P的兄弟W是红色的 */
/* 情况2: P的兄弟W是黑色的，且W的两个孩子都是黑色的 */
/* 情况3: P的兄弟W是黑色的，且W的左孩子是红色的，右孩子是黑色的 */
/* 情况4: P的兄弟W是黑色的，且W的右孩子是红色的 */
/* 以上4中情况针对 P = P->Parent->Left，P = P->Parent->Right反之 */
void DeleteFixup( Position P, RBTree T )
{
	Position W;
	while( P != T && P->Color == "B" )
	{
		if( P == P->Parent->Left )
		{
			W = P->Parent->Right;
			if( W->Color == "R" )
			{
				W->Color = "B" );
				P->Parent->Color = "R";
				SingleRotateWithRight( P->Parent );
			}

			if( W->Left->Color == "B" && W->Right->Color == "B" )
			{
				W->Color = "R";
				P = P->Parent;
			}
			else
				if( W->Right->Color == "B" )
				{
					W->Left->Color == "B";
					W->Color = "R";
					SingleRotateWithLeft( W );
					W = P->Parent->Right;
				}
				else
				{
					W->Color = P->Parent->Color;
					P->Parent->Color = "B";
					W->Right->Color = "B";
					SingleRotateWithRight( W->Parent );
				}

			P = T;
		}
		else
		{
			W = P->Parent->Left;
			if( W->Color == "R" )
			{
				W->Color = "B";
				P->Parent->Color = "R";
				SingleRotateWithLeft( P->Parent );
			}
			if( W->Right->Color == "B" && W->Left->Color == "B" )
			{
				W->Color = "R";
				P = P->Parent;
			}
			else
				if( W->Left->Color == "B" )
				{
					W->Right->Color = "B";
					W->Color = "R";
					SingleRotateWithRight( W );
					W = P->Parent->Left;
				}
				else
				{
					W->Color = P->Parent->Color;
					P->Parent->Color = "B";
					W->Left->Color = "B";
					SingleRotateWithLeft( W->Parent );
				}

			P = T;
		}
	}

	P->Color = "B";
}

Position CreateNode( ElementType X )
{
	Position P;
	P = malloc( sizeof( struct RBNode ) );
	if( P == NULL )
	{
		printf( "Out of space!!!" );
		exit( 1 )
	}
	else
	{
		P->Element = X;
		P->Left = P->Right = P->Parent = NilPosition;
		P->Color = "R";
	}
	return P;
}

Position CreateNilNode( void )
{
	Position P;

	P = malloc( sizeof( struct RBNode ) );
	if( P == NULL )
	{
		printf( "Out of space !!" );
		exit( 1 );
	}
	else
	{
		P->Element = 0;
		P->Left = P->Right = P->Parent = NULL;
		P->Color = "B";
	}
	return P;
}

/* This function can be called only if K2 has a left child */
/* Perform a rotate between a node (K2) and its left child */
/* Update heights,then return new root */
static Position SingleRotateWithLeft( Position K2 )
{
	Position K1;

	K1 = K2->Left;
	K2->Left = K1->Right;
	K1->Right = K2;

	return K1;/* New root */
}


/* This function can be called only if K1 has a right child */
/* Perform a rotate between a node (K1) and its right child */
/* Update heights,then return new root */
static Position SingleRotateWithRight( Position K1 )
{
	Position K2;

	K2 = K1->Right;
	K1->Right = K2->Left;
	K2->Left = K1;

	return K2; /* New root */
}