end_rb_tree.c

Deleting a node of RB-Tree without recurrence

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

#define		MAX_DEPTH	10		//	Max depth of the stack for red-black tree

//	Color information of the node
typedef enum COLORS{RED, BLACK} node_color;

typedef struct Block{
	char	data;
	node_color		color;
	struct Block	*parent;
	struct Block	*left;
	struct Block	*right;
} *node;

//	NIL leaf
static struct Block NIL_node = { 0, BLACK, NULL, NULL, NULL};


//Declare Functions
node get_node( void );											//	Get a empty and allocated node
void return_node(node *free_node);					//	Release a unused node
node create_tree( void );										//	Create a root node for RB-Tree
void rotate_left(node n);										//	Rotate the RB-Tree to the left
void rotate_right(node n);									//	Rotate the RB-Tree to the right
node grandparent(node n);										//	Get the grandparent node of current node

void insert(node n, node tree);							//	Insert a new node to the RB-Tree

void delete_one_child(node n, node tree);		//	Delete a selected node from RB-Tree
void del_node_fix(node n, node tree);				//	Fix the RB-Tree after deleting the selected node

node Read_Tree(FILE *fp);										//	Read information from a file to RB-Tree
void PrintTree(node	t);											//	Print RB-Tree by 1-st method	without method recurrence
node Find(node n, char data);								//	Find a needed node in RB-Tree by known key
void PrintTreeII(node t, int n);						//	Print RB-Tree by 2-nd method with method recurrence
node Find_instead_node(node tree, char key);//	Find a node to instead the node, which needs to be deleted


//	Dynamic Allocator
//	Return: 	A pointer to a block of memory for empty and located node
node get_node( void ) {
  node tmp;
  tmp	=	(struct Block *)malloc(sizeof(struct Block));
  memset(tmp, 0, sizeof(struct Block));
  tmp->left = &NIL_node;
  tmp->right= &NIL_node;
  return	(tmp);
}
 
//	Release Memory
//	parament(in):	free_node - pointer to a unused node
void return_node(node *free_node) {
  free(free_node);
}


//	Build up an empty tree.the first insert bases on the empty tree.
//	Return:		pointer to the root node of RB-Tree
node create_tree( void ) {
	node	root;

	root = get_node();
	root->left = root->right = root->parent = &NIL_node;
	root->color = BLACK;
	root->data	= '/';
	NIL_node.left = root;
	return	(root);         
}


//	Left-Rotation Function
//	parament(in):	n - pointer to the node, round which the RB-Tree rotates to the left.
void rotate_left(node n) {
	node	tmp;
	char	tmp_data;
	node_color	tmp_color;
    
	tmp = n->right;
	n->right = tmp->right;
	if (n->right != &NIL_node)	n->right->parent = n;

	tmp->right = tmp->left;	//no need to change parent
	tmp->left  = n->left;
	if (tmp->left != &NIL_node)	tmp->left->parent = tmp;

	n->left = tmp;
	//tmp->parent = n;

	tmp_data  = n->data;
	tmp_color = n->color;
	n->data   = tmp->data;
	n->color  = tmp->color;
	tmp->data = tmp_data;
	tmp->color= tmp_color;

	n = n->left;
}
 
//	Right-Rotation Function
//	parament(in):	n - pointer to the node, round which the RB-Tree rotates to the right.
void rotate_right(node n) {
	node	tmp;
	char	tmp_data;
	node_color	tmp_color;

	tmp = n->left;
	n->left = tmp->left;
	if (n->left != &NIL_node)	n->left->parent = n;

	tmp->left = tmp->right;
	tmp->right = n->right;
	if (tmp->right != &NIL_node) tmp->right->parent = tmp;
	n->right = tmp;

	tmp_data  = n->data;
	tmp_color = n->color;
	n->data   = tmp->data;
	n->color  = tmp->color;
	tmp->data = tmp_data;
	tmp->color= tmp_color;

	n = n->right;
}



//	Insert Node to RB-Tree
//	parament(in):	n 		- pointer to a new node, which is just created.
//								tree	-	pointer to the RB-Tree root
void insert(node n, node tree) {
	node y;

	while(n->parent->color == RED) {
		if(n->parent == n->parent->parent->left) {
			y = n->parent->parent->right;
			y->parent = n->parent->parent; //	Set Parent
			if(y->color == RED) {	//	Case 1
				n->parent->color = BLACK;
				y->color = BLACK;
				n->parent->parent->color = RED;
				n = n->parent->parent;
			}// Case 1
			else {
				if(n == n->parent->right) {	//Case 2
					n = n->parent;
					rotate_left(n);
				}//	Case 2
				// Case 3
				n->parent->color = BLACK;
				n->parent->parent->color = RED;
				rotate_right(n->parent->parent);
			}//	Case 3
		}else {
			y = n->parent->parent->right;
			y->parent = n->parent->parent; //	Set Parent
			if(y->color == RED) {	//	Case 1
				n->parent->color = BLACK;
				y->color = BLACK;
				n->parent->parent->color = RED;
				n = n->parent->parent;
			}// Case 1
			else {
				if(n == n->parent->left) {	//Case 2
					n = n->parent;
					rotate_right(n);
				}//	Case 2
			// Case 3
				n->parent->color = BLACK;
				n->parent->parent->color = RED;
				rotate_left(n->parent->parent);
			}//	Case 3
		}
	}
	tree->color = BLACK;
}



//	Fix the Tree after deleting Node from RB-Tree
//	parament(in):	n	 - pointer to the node, which needs to be deleted.
//								t	 - pointer to the RB-Tree root
void del_node_fix(node n, node t) {
	node w, tree;
	
	tree = t;
if(n->color == BLACK) {
	while(n != tree && n->color == BLACK) {
		if(n == n->parent->left) {
			w = n->parent->right;
			w->parent = n->parent;	//set parent
			if(w->color == RED) {				//	Case 1
				w->color = BLACK;
				w->parent->color = RED;	
				rotate_left(n->parent);
				w = n->parent->right;
				w->parent = n->parent;	//set parent
				printf("----------------------case 1 - l\n");
				PrintTreeII(tree, 0);
			}//	Case 1

			//if(w == &NIL_node)	break;
		   	if(w->left->color == BLACK && w->right->color == BLACK ) {	//	Case 2	*/
				w->color = RED;
				n = n->parent;	//set parent
				printf("----------------------case 2 - l\n");
				PrintTreeII(tree, 0);
			}//	Case 2
			else {
				if(w->right->color == BLACK) {	//	Case 3
					w->left->color = BLACK;
					w->color = RED;
					rotate_right(w);
					w = n->parent->right;
					w->parent = n->parent;	//set parent
					printf("----------------------case 3 - l\n");
					PrintTreeII(tree, 0);
				}
				w->color = n->parent->color;
				n->parent->color = BLACK;
				w->right->color  = BLACK;
				rotate_left(n->parent);
				n = tree;//
				//n = n->parent;
				printf("----------------------case 4 - l\n");
				PrintTreeII(tree, 0);
			}

		}else {
			w = n->parent->left;
			w->parent = n->parent;	//set parent
			if(w->color == RED) {				//	Case 1
				w->color = BLACK;
				w->parent->color = RED;
				rotate_right(n->parent);
				w = n->parent->left;
				w->parent = n->parent;	//set parent
				printf("----------------------case 1 - r\n");
				PrintTreeII(tree, 0);
			}//	Case 1
		
			//if(w == &NIL_node)	break;
			if(w->left->color == BLACK && w->right->color == BLACK ) {	//	Case 2	*/
				w->color = RED;
				n = n->parent;
				printf("----------------------case 2 - r\n");
				PrintTreeII(tree, 0);
			}//	Case 2
			else {
				if(w->left->color == BLACK ) {	//	Case 3
					w->right->color = BLACK;
					w->color = RED;
					rotate_left(w);
					w = n->parent->left;
					printf("----------------------case 3 - r\n");
					PrintTreeII(tree, 0);
				}
				w->color = n->parent->color;
				n->parent->color = BLACK;
				w->left->color  = BLACK;
				rotate_right(n->parent);
				n = tree;
				printf("----------------------case 4 - r\n");
				PrintTreeII(tree, 0);
			}
		}
		//n->color = BLACK;
	}
	n->color = BLACK;
}

	if(n->color == RED) {
		if(n->left == &NIL_node && n->right == &NIL_node) {
			if(n == n->parent->left)	n->parent->left = &NIL_node;
			else	n->parent->right = &NIL_node;
		}else {
			if(n->left != &NIL_node) {
				if(n == n->parent->left) {
					n->parent->left = n->left;
					n->left->parent = n->parent;
				}
				else {
					n->parent->right = n->left;
					n->left->parent  = n->parent; 
				}
			}
			else {
				if(n == n->parent->left) {
					n->parent->left	 = n->right;
					n->right->parent = n->parent;
				}
				else {
					n->parent->right = n->right;
					n->right->parent  = n->parent; 
				}
			}
		}
	}

}


//	Delete Node from RB-Tree
//	parament(in):	n	 - pointer to the node, which needs to be deleted.
//								t	 - pointer to the RB-Tree root
void delete_one_child(node n, node tree) {
    /* Precondition: n has at most one non-null child */
    node	child;
	//char	tmp_data;

	if(n->parent == &NIL_node && n->left == &NIL_node && n->right == &NIL_node) {
		printf("This is the root of the tree, it must not be deleted!!!\n");
		getch();
		return;
	}

	if(n->left != &NIL_node || n->right != &NIL_node) {
		printf("The Node has two sons, so have to change place with someone.\n");
		child = Find_instead_node(tree, n->data);
		if(child == NULL) {
			printf("Can not find the instead node.");
			getch();
			return;
		}
	//	tmp_data = child->data;
	//	child->data = n->data;
	//	n->data = tmp_data;
		//n = child;
		n->data = child->data;

		printf("------------------ Change place\n");
		PrintTreeII(tree, 0);
		del_node_fix(child, tree);
		if(child->color != RED) {
			if(child == child->parent->left) child->parent->left = &NIL_node;
			else	child->parent->right = &NIL_node;
		}
		free(child);
	}else {
		del_node_fix(n, tree);
		if(n->color != RED) {
			if(n == n->parent->left) n->parent->left = &NIL_node;
			else	n->parent->right = &NIL_node;
		}
		free(n);
	}
}



//	Function to read the Tree-data from file
//	parament(in):	fp - pointer to the opened file
//	Return:	pointer to the RB-Tree root
node Read_Tree(FILE *fp) {
	char data;
	node root, pointer, n;
	
	root = create_tree();
	
	pointer = root;
	while( !feof(fp) ) {
		data = fgetc(fp);
		if (data >= 'a' && data <= 'z' ) {
			n = get_node();
			n->data 	= data;
			n->color	= RED;
			while(pointer->left != &NIL_node && pointer != NULL){
				pointer = pointer->left;	
			}
			pointer->left = n;
			n->parent = pointer;
			insert(n, root);
			pointer = root;

			printf("----------------\n");
			PrintTreeII(root, 0);
			//getch();
		}
	}

	return (root);
}


//	Print RB-Tree by 2-nd method with method recurrence
//	parament(in):	t	-	pointer to the RB-Tree root
//								n - counter for recurrence
void PrintTreeII(node t, int n)
{
	int i;
	if (t != &NIL_node && t != NULL) {
		PrintTreeII(t->right, n+1);
		for (i=0; i<5*n; i++) putchar(' ');
		printf("%c(%d)\n",t->data, t->color);
		PrintTreeII(t->left, n+1);
	}
	else if(t->parent == &NIL_node && t->left == &NIL_node && t->right == &NIL_node) {
		printf("The Tree is empty");
	}
}

node sibling(node n) {
	if(n == n->parent->left)	return n->parent->right;
	else	return n->parent->left;
}

node Find_instead_node(node t, char key)
{
	node st[MAX_DEPTH];
	int s =	0;
	
	s++; 
	st[s] = t;
	while(s) {
		t =	st[s]; 
		s--;
		while(t != &NIL_node) {
			if(t->left == &NIL_node && 
			   t->right == &NIL_node &&
			   t->data != key ) return t;
			s++; 
			st[s] =	t->right;
			t =	t->left;
		}// end while
	}// end while
	return NULL;
}

//	Print RB-Tree by 1-nd method without method recurrence
//	parament(in):	t	-	pointer to the RB-Tree root
void PrintTree(node	t) {
	node	st[MAX_DEPTH];
	int s = 0;
	
	s++; 
	st[s]=t;
	while (s) {
		t =	st[s]; 
		s--;
		while (t != &NIL_node) {
			printf("%c",t->data);
			s++;
			st[s] =	t->right;
			t =	t->left;
		}
	}
}

//	Find the needed node by known key
//	parament(in):	t		 -	pointer to the RB-Tree root
//								data - 	the key to the node
node Find(node t, char data) {
	node st[MAX_DEPTH];
	int s =	0;
	
	s++; 
	st[s] = t;
	while (s){
		t =	st[s]; 
		s--;
		while (t!=&NIL_node){
//			printf("%c",t->data);
			if(data == t->data)		return t;
			s++; 
			st[s] =	t->right;
			t =	t->left;
		}
	}
	
	return NULL;
}	


//	Main Function
void main( void )
{
	FILE *fp;
	node tree, pointer;
	char key;
	int	 done = 1;
		
	if( (fp=fopen("data.txt", "r+t")) == NULL ) {
		printf("Open file failed!\n");
		getch();
		return;
	}
	else	printf("Open file succeed.\n");

	tree = Read_Tree(fp);
	if( tree == NULL || tree == &NIL_node) {
		printf("Read Tree failed.\n");
		getch();
		return;
	}
	else	printf("Read Tree succeed.\n");


	while(done == 1){
		printf("Here is the tree. \n");
		PrintTreeII(tree, 0);

		printf("Please select a key to delete (a-z):\n");
		key = getche();
		printf("\n");

		if (key == '0') {
			done = 0;
			free(tree);			//	In the end we need to release the pointer to the RB-Tree root
			continue;
		}

		if(key <= 'a' && key >= 'z') {
			printf("Input Error!\n");
			getch();
			continue;
		}


		pointer = Find(tree, key);
		if(pointer == &NIL_node || pointer == NULL) {
			printf("\nNot such Key!\n");
			getch();
			continue;
		}

		printf("The Key is %c\nThe Color is %d\n", pointer->data, pointer->color);
		delete_one_child(pointer, tree);

		printf("----------------------\n");
		printf("\n");
		memset(&key, 0, sizeof(char));
	}
	
}