성대아싸의 멍충한 프로그래밍

알고리즘2009. 9. 17. 00:05

red_black_tree (func)

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

enum COLOR {RED,BLACK};
typedef enum COLOR COLOR;
typedef int 		DATA;

struct rbtree
{
	DATA 			key;
	COLOR			color;
	struct rbtree 	*left;
	struct rbtree 	*right;
	struct rbtree	*p;
};
typedef struct rbtree 	ELEM_RB;
typedef ELEM_RB 		*RBTREE;

RBTREE left_rotate(RBTREE tree, RBTREE base, RBTREE nil)
{
	RBTREE y = base -> right;
	base -> right = y -> left;

if (y -> left != nil)
		y -> left -> p = base;

y -> p = base -> p;

if (base -> p == nil)
		tree = y;
	else if (base == base -> p -> left)
		base -> p -> left = y;
	else
		base -> p -> right = y;

y -> left = base;
	base -> p = y;

return tree;
}
RBTREE right_rotate(RBTREE tree, RBTREE base, RBTREE nil)
{
	RBTREE y = base -> left;
	base -> left = y -> right;

if (y -> right != nil)
		y -> right -> p = base;

y ->p = base -> p;

if (base -> p == nil)
		tree = y;
	else if (base == base -> p -> right)
		base -> p -> right = y;
	else
		base -> p -> left = y;

y -> right = base;
	base -> p = y;

return tree;
}

RBTREE RB_insert_fixup(RBTREE tree, RBTREE input, RBTREE nil)
{
	RBTREE y;
	
	while ( input -> p -> color == RED)
	{
		if( (input -> p) == (input -> p -> p -> left))
		{
			y = input -> p -> p -> right;
			if (y -> color == RED)
			{
				input -> p -> color = BLACK;
				y -> color = BLACK;
				input -> p -> p -> color = RED;
				input = input -> p -> p;
			}
			else 
			{
				if ( input == input -> p -> right)
				{
					input = input -> p;
					tree = left_rotate(tree,input,nil);
				}
				input -> p -> color = BLACK;
				input -> p -> p -> color = RED;
				tree = right_rotate(tree,input->p->p,nil);
			}
		}
		else
		{
			y = input -> p -> p -> left;
			if (y -> color == RED)
			{
				input -> p -> color = BLACK;
				y -> color = BLACK;
				input -> p -> p -> color = RED;
				input = input -> p -> p;
			}
			else 
			{
				if ( input == input -> p -> left)
				{
					input = input -> p;
					tree = right_rotate(tree,input,nil);
				}
				input -> p -> color = BLACK;
				input -> p -> p -> color = RED;
				tree = left_rotate(tree,input->p->p,nil);
			}
		}
	}
	tree -> color = BLACK;
	return tree;
}

RBTREE RB_insert(RBTREE tree, RBTREE input, RBTREE nil)
{
	RBTREE y = nil;
	RBTREE x = tree;

while (x != nil)
	{
		y = x;
		if ((input -> key) < (x -> key))
			x = x -> left;
		else
			x = x -> right;
	}
	input -> p = y;

if (y == nil)
		tree = input;
	else if ((input -> key) < (y -> key))
		y -> left = input;
	else
		y -> right = input;
	
	input -> left = nil;
	input -> right = nil;
	input -> color = RED;

return RB_insert_fixup(tree,input,nil);
}

RBTREE make_node(DATA input ,RBTREE nil)
{
	RBTREE tmp;
	tmp =  (RBTREE)malloc(sizeof(ELEM_RB));
	tmp ->key = input;
	tmp ->left = nil;
	tmp -> right = nil;
	tmp ->p = nil;
	return tmp;
}
RBTREE make_nil()
{
	RBTREE tmp;
	tmp = (RBTREE)malloc(sizeof(ELEM_RB));
	tmp -> key = 0;
	tmp ->left = NULL;
	tmp -> right = NULL;
	tmp ->p = NULL;
	tmp ->color = BLACK;
	return tmp;
}

void inorder(RBTREE root, RBTREE nil)
{
	if (root != nil)
	{
		inorder(root -> left,nil);
		printf("l:%2d |%2d| %2d:r  >p:%2d  >< %4s\n",root->left->key,root->key,root->right->key,root->p->key,(root->color==RED)?"red":"black");
		inorder(root -> right,nil);
	}
}
RBTREE tree_minimum(RBTREE root, RBTREE nil)
{
	RBTREE tmp = root;

while (tmp -> left != nil)
	{
		tmp = tmp -> left;
	}
	return tmp;
}

RBTREE tree_successor(RBTREE root, RBTREE nil)
{
	RBTREE tmp;
	if (root -> right != nil)
		return tree_minimum(root -> right,nil);
	
	tmp = root->p;
	
	while((tmp != nil) && (root == tmp->right))
	{
		root = tmp;
		tmp = tmp -> p;
	}
	return tmp;
}
RBTREE RB_delete_fixup(RBTREE tree, RBTREE put, RBTREE nil)
{
	RBTREE w;
	while((put != tree) &&(put -> color == BLACK))
	{
		if(put == put -> p -> left)
		{
			w = put -> p -> right;
			if (w -> color == RED)
			{
				w -> color = BLACK;
				put -> p -> color = RED;
				tree = left_rotate(tree,put->p,nil);
				w = put -> p -> right;
			}
			if ((w->left->color == BLACK)&&(w->right->color == BLACK))
			{
				w -> color = RED;
				put = put -> p;
			}
			else 
			{
				if(w -> right -> color == BLACK)
				{
					w->left->color = BLACK;
					w-> color = RED;
					tree = right_rotate(tree,w,nil);
					w = put->p->right;
				}
				w -> color = put -> p -> color;
				put -> p -> color = BLACK;
				w -> right -> color = BLACK;
				tree = left_rotate(tree,put->p,nil);
				put = tree;
			}
		}
		else
		{
			w = put -> p -> left;
			if (w -> color == RED)
			{
				w -> color = BLACK;
				put -> p -> color = RED;
				tree = right_rotate(tree,put->p,nil);
				w = put -> p -> left;
			}
			if ((w->right->color == BLACK)&&(w->left->color == BLACK))
			{
				w -> color = RED;
				put = put -> p;
			}
			else 
			{
				if(w -> left -> color == BLACK)
				{
					w->right->color = BLACK;
					w-> color = RED;
					tree = left_rotate(tree,w,nil);
					w = put->p->left;
				}
				w -> color = put -> p -> color;
				put -> p -> color = BLACK;
				w -> left -> color = BLACK;
				tree = right_rotate(tree,put->p,nil);
				put = tree;
			}
		}
	}
	put -> color = BLACK;
	return tree;
}

RBTREE RB_delete(RBTREE tree, RBTREE put, RBTREE nil)
{
	RBTREE y;
	RBTREE x;
	if ((put -> left == nil)||(put->right == nil))
		y = put;
	else
		y = tree_successor(put,nil);
	if(put -> left != nil)
		x = y -> left;
	else
		x = y -> right;

x->p = y->p;

if (y -> p == nil)
		tree = x;
	else 
	{
		if (y == y -> p -> left)
			y -> p -> left = x;
		else
			y -> p -> right = x;
	}
	if ( y != put)
		put -> key = y -> key;
	if (y -> color == BLACK)
		tree = RB_delete_fixup(tree,x,nil);

return tree;
}
RBTREE tree_search(RBTREE tree, DATA d,RBTREE nil)
{
	RBTREE root;
	root = tree;
	
	while ((root != nil) && (d != root -> key))
	{
		if (d < root -> key)
			root = root -> left;
		else
			root = root -> right;
	}
	return root;
}

int main(void)
{
	RBTREE tree;
	RBTREE val;
	RBTREE nil;
		
	int i;
	int arr[] ={4,7,3,2,8,9,10,1,6,5};

nil = make_nil();
	tree = nil;

for (i=0; i<10; i++)
	{
		val = make_node(arr[i],nil);
		tree = RB_insert(tree,val,nil);
	}
	inorder(tree,nil);

for (i=1; i<11; i++)
	{
		printf("del = %d\n", i);
		val = tree_search(tree,i,nil);
		tree = RB_delete(tree,val,nil);

inorder(tree,nil);
		printf("\n=============\n");
	}
	
	return 0;

}

저작자표시

'알고리즘' 카테고리의 다른 글

RB_tree (동적순서통계) (0)	2009.09.17
red_black_tree (과정분석) (0)	2009.09.17
red_black_tree (func) (0)	2009.09.17
red_black_tree (concept) (0)	2009.09.17
BST (평가) (0)	2009.09.16
BST (func) (0)	2009.09.16

Posted by 멍충한아싸

Trackback 0 Comment 0

댓글을 달아 주세요

«이전 1 ··· 212 213 214 215 216 217 218 219 220 ··· 240 다음»

일	월	화	수	목	금	토
					1	2
3	4	5	6	7	8	9
10	11	12	13	14	15	16
17	18	19	20	21	22	23
24	25	26	27	28	29	30
31

성대아싸의 멍충한 프로그래밍

red_black_tree (func)

'알고리즘' 카테고리의 다른 글

TRACKBACK

댓글을 달아 주세요

카테고리

공지사항

태그목록

최근에 올라온 글

최근에 달린 댓글

최근에 받은 트랙백

글 보관함

달력

링크