my_red_black_tree.cpp

本程序中提供了对红黑树这一重要数据结构的完整实现以及各种操作

#include <stdio.h>
#include <stdlib.h>

#define BLACK 1
#define RED 0

struct Node {
	int key;
	bool color;
	Node *p, *l, *r;
};

Node *root, *NIL;

// -----------------------------------------
void init( ); 

void left_rotation( Node * );
void right_rotation( Node * );
void RB_insert( int );
void RB_insert_fixup( Node * );
void RB_delete( int );
void RB_delete_fixup( Node * );

Node* minimum( Node * );
Node* successor( Node * );
Node* search( int );
void construct( );
void preorder( );
void output(  Node *, void (*)( Node * ) );
// ----------------------------------------

void init( )
{
	NIL = (Node *) malloc ( sizeof( Node ) );
	NIL->color = BLACK;
	NIL->p = NIL->l = NIL->r = NULL;

	root = NIL;
}

void left_rotation( Node *x )
{
	Node *y = x->r;

	y->p = x->p;
	if( x->p == NIL ) 
		root = y;
	else {
		if( x == x->p->l )
			x->p->l = y;
		else
			x->p->r = y;
	}
	x->p = y;

	x->r = y->l;

	// 下面的这个if 非常重要，千万不能漏了
	// 在有的情况下这个条件必不可少，而且本身
	// 在这里改变NIL 的p 也是没有意义的
	// right_rotation 同理
	if( y->l != NIL )
		y->l->p = x;
	y->l = x;
}

void right_rotation( Node *x )
{
	Node *y = x->l;

	y->p = x->p;
	if( x->p == NIL )
		root = y;
	else {
		if( x == x->p->l )
			x->p->l = y;
		else
			x->p->r = y;
	}
	x->p = y;

	x->l = y->r;
	if( y->r != NIL )
		y->r->p = x;
	y->r = x;
}

void RB_insert( int k ) 
{
	Node *z = (Node *)malloc( sizeof( Node ) );
	z->key = k;
	z->color = RED;
	z->p = z->l = z->r = NIL;
	
	Node *x = root, *y = x;
	while( x != NIL ) {
		y = x;
		if( k < x->key )
			x = x->l;
		else
			x = x->r;
	}
	z->p = y;

	if( y == NIL )
		root = z;
	else
		if( k < y->key )
			y->l = z;
		else
			y->r = z;
	
	RB_insert_fixup( z );
}

void RB_insert_fixup( Node *x )
{
	while( x->p->color == RED ) {
		Node *t, *y; // y is the sibling of x->p

		if( x->p == x->p->p->l ) {

			y = x->p->p->r;

			if( y->color == RED ) {
				y->color = x->p->color = BLACK;
				x->p->p->color = RED;
				x = x->p->p;
			} else {
				if( x == x->p->r ) {
					t = x->p;
					left_rotation( t );
					x = x->l;
				} 
				x->p->color = BLACK;
				x->p->p->color = RED;
				t = x->p->p;
				right_rotation( t );
			}
		} else {
			
			y = x->p->p->l;

			if( y->color == RED ) {
				y->color = x->p->color = BLACK;
				x->p->p->color = RED;
				x = x->p->p;
			} else {
				if( x == x->p->l ) {
					t = x->p;
					right_rotation( t );
					x = x->r;
				}
				x->p->color = BLACK;
				x->p->p->color = RED;
				t = x->p->p;
				left_rotation( t );
			}
		}
	}
	root->color = BLACK;
}

void RB_delete( int k )
{
	Node *x = search( k ), *y;

	if( x->l == NIL || x->r == NIL )
		y = x;
	else
		y = successor( x );

	Node *z;
	if( y->l != NIL )
		z = y->l;
	else
		z = y->r;

	z->p = y->p;
	if( y->p == NIL )
		root = z;
	else 
		if( y->p->l == y )
			y->p->l = z;
		else
			y->p->r = z;

	if( y != x )
		x->key = y->key;

	if( y->color == BLACK )
		RB_delete_fixup( z );
}

void RB_delete_fixup( Node *x )
{
	while( x != root && x->color == BLACK ) {
		Node *w, *t; // w is the sibling of x;

		if( x == x->p->l ) {
			
			w = x->p->r;

			if( w->color == RED ) {
				x->p->color = RED;
				w->color = BLACK;
				t = x->p;
				left_rotation( t );
				w = x->p->r;
			} 
			if( w->r->color == BLACK && w->l->color == BLACK ) {
				w->color = RED;
				x = x->p;
				w = x->p->r;
			} else {
				if( w->r->color == BLACK ) {
					w->color = RED;
					w->l->color = BLACK;
					t = w;
					right_rotation( t );
					w = x->p->r;
				}
				w->color = x->p->color;
				x->p->color = BLACK;
				w->r->color = BLACK;
				t = x->p;
				left_rotation( t );
				x = root;
			}
		} else {

			w = x->p->l;

			if( w->color == RED ) {
				x->p->color = RED;
				w->color = BLACK;
				t = x->p;
				left_rotation( t );
				w = x->p->l;
			}
			if( w->r->color == BLACK && w->l->color == BLACK ) {
				w->color = RED;
				x = x->p;
				w = x->p->l;
			} else {
				if( w->l->color == BLACK ) {
					w->color = RED;
					w->r->color = BLACK;
					t = w;
					left_rotation( t );
					w = x->p->l;
				}
				w->color = x->p->color;
				x->p->color = BLACK;
				w->l->color = BLACK;
				t = x->p;
				right_rotation( t );
				x = root;
			}
		}
	}
	x->color = BLACK;
}

Node* minimum( Node *x )
{
	Node *y = x;
	while( y->l != NIL ) {
		y = y->l;
	}
	return y;
}

Node* successor( Node *x ) 
{
	if( x->l != NIL && x->r != NIL )
		return minimum( x->r );

	Node *y = x->p;
	while( y != NIL && x == y->r ) {
		x = y;
		y = y->p;
	}
	return y;
}

Node* search( int k )
{
	Node *x = root;

	while( x != NIL && x->key != k ) {
		if( k < x->key )
			x = x->l;
		else
			x = x->r;
	}

	return x;
}

void construct( )
{
	int k;

	while( scanf( "%d", &k ) != EOF ) {
		RB_insert( k );
	}
}

void preorder( Node *x )
{
	if( x != NIL ) {
		printf( "%-4d%s\n", x->key, (x->color == BLACK ? "BLACK" : "RED") );
		preorder( x->l );
		preorder( x->r );
	}
}

void output(  Node *x = root, void (*f)( Node * ) = preorder ) 
{
	putchar( '\n' );
	if( root != NIL )
		f( x );
	else
		printf( "NULL TREE!\n" );
	putchar( '\n' );
}

int main( )
{
	freopen( "test.in", "r", stdin );
	freopen( "test.out", "w", stdout );

	init( );
	construct( );
	RB_insert( 4 );
	output( );

	RB_delete( 5 );
	output( );

	RB_delete( 4 );
	output( );

	RB_delete( 2 );
	output( );

	RB_delete( 1 );
	output( );

	RB_delete( 11 );
	output( );

	RB_delete( 15 );
	output( );

	RB_delete( 8 );
	output( );

	RB_delete( 14 );
	output( );

	RB_delete( 7 );
	output( );

	return 0;
}