• Revista PROGRAMAR: Já está disponível a edição #53 da revista programar. Faz já o download aqui!

orium

[C] Red Black Tree

1 mensagem neste tópico

Boas!!! Sempre quis implementar e perceber uma red black tree, agora so' falta perceber...

O código que escrevi foi directamente "tradusido" do psedo-código do livro Introduction to Algorithms, 2nd Edition, por Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest e Clifford Stein, página ~240.

O tempo de insersao e remocao de elementos e' de O(lg(N)), onde N e' o numero de elementos na arvore, a red black tree assegura isto mantendo algumas propriadades, atravez de rotacao de arvores, etc...

Esta' um pequeno exemplo no fim.

Nota: O código foi pouco ou nada testado :\

O código depende ainda de xalloc, que ja foi postado por mim, de qq maneira a unica coisa que faz e' verificar o resultado das funções de alocação de memória.

rbtree.h:

/*
*  GPL
*
*  Written by Diogo Sousa aka orium
*  Copyright © 2008 Diogo Sousa
*
*  This program is free software: you can redistribute it and/or modify
*  it under the terms of the GNU General Public License as published by
*  the Free Software Foundation, either version 3 of the License, or
*  (at your option) any later version.
*
*  This program is distributed in the hope that it will be useful,
*  but WITHOUT ANY WARRANTY; without even the implied warranty of
*  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
*  GNU General Public License for more details.
*
*  You should have received a copy of the GNU General Public License
*  along with this program.  If not, see <http://www.gnu.org/licenses/>.
*/

#ifndef RBTREE_H_
#define RBTREE_H_

enum color
{
BLACK=1,
RED
};

struct rbtree_node
{
void *data;

enum color color;

struct rbtree_node *parent;

struct rbtree_node *left;
struct rbtree_node *right;
};

struct rbtree
{
struct rbtree_node *root;

struct rbtree_node *nil;
};

extern void rbtree_init(struct rbtree **);
extern int rbtree_insert(struct rbtree *, void *,
		 int (*)(const void *, const void *));
extern int rbtree_delete(struct rbtree *, void *,
		 int (*)(const void *, const void *));
extern void rbtree_walk(struct rbtree *,
		void (*)(void *));
extern void rbtree_free(struct rbtree *,
		void (*)(void *));
extern void *rbtree_search(struct rbtree *, void *,
		   int (*)(const void *, const void *));
extern int rbtree_height(struct rbtree *);

#endif

rbtree.c

/*
*  GPL
*
*  Written by Diogo Sousa aka orium
*  Copyright © 2008 Diogo Sousa
*
*  This program is free software: you can redistribute it and/or modify
*  it under the terms of the GNU General Public License as published by
*  the Free Software Foundation, either version 3 of the License, or
*  (at your option) any later version.
*
*  This program is distributed in the hope that it will be useful,
*  but WITHOUT ANY WARRANTY; without even the implied warranty of
*  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
*  GNU General Public License for more details.
*
*  You should have received a copy of the GNU General Public License
*  along with this program.  If not, see <http://www.gnu.org/licenses/>.
*/

#include <stdlib.h>
#include <assert.h>
#include "rbtree.h"
#include "xalloc.h"

/*
* This algorithms where directly translated from Introduction to Algorithms,
* 2nd Edition, by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest
* and Clifford Stein, page ~240.
*
*/

static struct rbtree_node *alloc_rbtree_node(void);
static void rotate_left(struct rbtree *, struct rbtree_node *);
static void rotate_right(struct rbtree *, struct rbtree_node *);
static void insert_fixup(struct rbtree *, struct rbtree_node *);
static struct rbtree_node *rbtree_minimum(struct rbtree *,
				  struct rbtree_node *);
static struct rbtree_node *rbtree_successor(struct rbtree *,
				    struct rbtree_node *);
static void delete_fixup(struct rbtree *, struct rbtree_node *);
static void rbtree_walk_recursive(struct rbtree *, struct rbtree_node *,
			  void (*)(void *));
static void rbtree_free_recursive(struct rbtree *, struct rbtree_node *,
			  void (*)(void *));
static struct rbtree_node *search_node(struct rbtree *, void *,
			       int (*)(const void *, const void *));
static int rbtree_height_recursive(struct rbtree *, struct rbtree_node *,
			   int);

void
rbtree_init(struct rbtree **rbtree)
{
*rbtree=xmalloc(sizeof(**rbtree));

(*rbtree)->nil=alloc_rbtree_node();
(*rbtree)->nil->color=BLACK;
(*rbtree)->nil->parent=(*rbtree)->nil;
(*rbtree)->nil->left=(*rbtree)->nil;
(*rbtree)->nil->right=(*rbtree)->nil;
(*rbtree)->nil->data=NULL;

(*rbtree)->root=(*rbtree)->nil;
}

static struct rbtree_node *
alloc_rbtree_node(void)
{
struct rbtree_node *r;

r=xmalloc(sizeof(*r));

return r;
}

/*
* Before rotate_left(X):
*
*         X
*       /   \
*      A     Y
*          /	\
*         B     K
*
* After rotate_left(X):
*
*         Y
*       /   \
*      X     K
*    /	  \
*   A     B
*
*/
static void
rotate_left(struct rbtree *rbtree, struct rbtree_node *x)
{
struct rbtree_node *y;

assert(x->right != rbtree->nil);

y=x->right;
x->right=y->left;

y->left->parent=x;
y->parent=x->parent;

if (x->parent == rbtree->nil)
	rbtree->root=y;
else
	if (x == x->parent->left)
		x->parent->left=y;
	else
		x->parent->right=y;

y->left=x;
x->parent=y;
}

/*
* Before rotate_right(Y):
*
*         Y
*       /   \
*      X     K
*    /	  \
*   A     B
*
* After rotate_right(Y):
*
*         X
*       /   \
*      A     Y
*          /	\
*         B     K
*
*/
static void
rotate_right(struct rbtree *rbtree, struct rbtree_node *x)
{
struct rbtree_node *y;

assert(x->left != rbtree->nil);

y=x->left;
x->left=y->right;

y->right->parent=x;
y->parent=x->parent;

if (x->parent == rbtree->nil)
	rbtree->root=y;
else
	if (x == x->parent->left)
		x->parent->left=y;
	else
		x->parent->right=y;

y->right=x;
x->parent=y;
}

int
rbtree_insert(struct rbtree *rbtree,
      void *data,
      int (*cmp)(const void *, const void *))
{
struct rbtree_node *node;
struct rbtree_node *y;
struct rbtree_node *x;
int d;

if (data == NULL) /* This may be used as a special value */
	return -1;

node=alloc_rbtree_node();
node->data=data;

node->color=RED;
node->left=rbtree->nil;
node->right=rbtree->nil;

x=rbtree->root;
y=rbtree->nil;

while (x != rbtree->nil)
{
	y=x;

	d=cmp(node->data,x->data);

	if (!d)
		return -1;

	if (d < 0)
		x=x->left;
	else
		x=x->right;
}

node->parent=y;

if (y == rbtree->nil)
	rbtree->root=node;
else
{
	/* Here d == cmp(node->data,y->data) */

	if (d < 0)
		y->left=node;
	else
		y->right=node;
}

insert_fixup(rbtree,node);

return 0;
}

static void
insert_fixup(struct rbtree *rbtree, struct rbtree_node *node)
{
struct rbtree_node *y;

while (node->parent->color == RED)
{
	if (node->parent == node->parent->parent->left)
	{
		y=node->parent->parent->right;

		if (y->color == RED)
		{
			node->parent->color=BLACK;
			y->color=BLACK;
			node->parent->parent->color=RED;
			node=node->parent->parent;
		}
		else
		{
			if (node == node->parent->right)
			{
				node=node->parent;
				rotate_left(rbtree,node);
			}

			node->parent->color=BLACK;
			node->parent->parent->color=RED;

			rotate_right(rbtree,node->parent->parent);
		}
	}
	else
	{
		y=node->parent->parent->left;

		if (y->color == RED)
		{
			node->parent->color=BLACK;
			y->color=BLACK;
			node->parent->parent->color=RED;
			node=node->parent->parent;
		}
		else
		{
			if (node == node->parent->left)
			{
				node=node->parent;
				rotate_right(rbtree,node);
			}

			node->parent->color=BLACK;
			node->parent->parent->color=RED;

			rotate_left(rbtree,node->parent->parent);
		}

	}
}

rbtree->root->color=BLACK;	
}

static struct rbtree_node *
rbtree_minimum(struct rbtree *rbtree,
       struct rbtree_node *node)
{
while (node->left != rbtree->nil)
	node=node->left;

return node;
}

static struct rbtree_node *
rbtree_successor(struct rbtree *rbtree,
	 struct rbtree_node *node)
{
struct rbtree_node *y;

if (node->right != rbtree->nil)
	return rbtree_minimum(rbtree,node->right);

y=node->parent;

while (y != rbtree->nil && node == y->right)
{
	node=y;
	y=y->parent;
}

return y;
}

int
rbtree_delete(struct rbtree *rbtree, void *needle,
      int (*cmp)(const void *, const void *))
{
struct rbtree_node *node;
struct rbtree_node *y;
struct rbtree_node *x;

node=search_node(rbtree,needle,cmp);

if (node == rbtree->nil)
	return -1;

if (node->left == rbtree->nil
    || node->right == rbtree->nil)
	y=node;
else
	y=rbtree_successor(rbtree,node);

if (y->left != rbtree->nil)
	x=y->left;
else
	x=y->right;

x->parent=y->parent;

if (y->parent == rbtree->nil)
	rbtree->root=x;
else
{
	if (y == y->parent->left)
		y->parent->left=x;
	else
		y->parent->right=x;
}

if (y != node)
	node->data=y->data;

if (y->color == BLACK)
	delete_fixup(rbtree,x);

free(y);

return 0;
}

static void
delete_fixup(struct rbtree *rbtree, struct rbtree_node *node)
{
struct rbtree_node *w;

while (node != rbtree->root && node->color == BLACK)
{
	if (node == node->parent->left)
	{
		w=node->parent->right;

		if (w->color == RED)
		{
			w->color=BLACK;
			node->parent->color=RED;
			rotate_left(rbtree,node->parent);
			w=node->parent->right;
		}

		if (w->left->color == BLACK
		    && w->right->color == BLACK)
		{
			w->color=RED;
			node=node->parent;
		}
		else
		{
			if (w->right->color == BLACK)
			{
				w->left->color=BLACK;
				w->color=RED;
				rotate_right(rbtree,w);
				w=node->parent->right;
			}

			w->color=node->parent->color;
			node->parent->color=BLACK;
			w->right->color=BLACK;
			rotate_left(rbtree,node->parent);
			node=rbtree->root;
		}
	}
	else
	{
		w=node->parent->left;

		if (w->color == RED)
		{
			w->color=BLACK;
			node->parent->color=RED;
			rotate_right(rbtree,node->parent);
			w=node->parent->left;
		}

		if (w->right->color == BLACK
		    && w->left->color == BLACK)
		{
			w->color=RED;
			node=node->parent;
		}
		else
		{
			if (w->left->color == BLACK)
			{
				w->right->color=BLACK;
				w->color=RED;
				rotate_left(rbtree,w);
				w=node->parent->left;
			}

			w->color=node->parent->color;
			node->parent->color=BLACK;
			w->right->color=BLACK;
			rotate_right(rbtree,node->parent);
			node=rbtree->root;
		}

	}
}

node->color=BLACK;
}

static void
rbtree_walk_recursive(struct rbtree *rbtree, struct rbtree_node *node,
	      void (*action)(void *))
{
if (node == rbtree->nil)
	return;

rbtree_walk_recursive(rbtree,node->left,action);
action(node->data);
rbtree_walk_recursive(rbtree,node->right,action);
}

void
rbtree_walk(struct rbtree *rbtree,
    void (*action)(void *))
{
rbtree_walk_recursive(rbtree,rbtree->root,action);
}

static void
rbtree_free_recursive(struct rbtree *rbtree, struct rbtree_node *node,
	      void (*action)(void *))
{
if (node == rbtree->nil)
	return;

if (action != NULL)
	action(node->data);

rbtree_free_recursive(rbtree,node->left,action);
rbtree_free_recursive(rbtree,node->right,action);

free(node);
}

void
rbtree_free(struct rbtree *rbtree, void (*action)(void *))
{
rbtree_free_recursive(rbtree,rbtree->root,action);
free(rbtree->nil);
free(rbtree);
}

static struct rbtree_node *
search_node(struct rbtree *rbtree, void *needle,
    int (*cmp)(const void *, const void *))
{
struct rbtree_node *node;
int d;

node=rbtree->root;

while (node != rbtree->nil)
{
	d=cmp(needle,node->data);

	if (!d)
		break;

	if (d < 0)
		node=node->left;
	else
		node=node->right;
}

return node;
}

void *
rbtree_search(struct rbtree *rbtree, void *needle,
      int (*cmp)(const void *, const void *))
{
struct rbtree_node *node;

node=search_node(rbtree,needle,cmp);

return (node == rbtree->nil) ? NULL : node->data;
}

static int
rbtree_height_recursive(struct rbtree *rbtree, struct rbtree_node *node,
		int depth)
{
int depth_right;
int depth_left;

if (node == rbtree->nil)
	return depth-1;

depth_left=rbtree_height_recursive(rbtree,node->left,depth+1);
depth_right=rbtree_height_recursive(rbtree,node->right,depth+1);

return (depth_left > depth_right) ? depth_left : depth_right;
}

int
rbtree_height(struct rbtree *rbtree)
{
return rbtree_height_recursive(rbtree,rbtree->root,0);
}

Exemplo:

/*
*  GPL
*
*  Written by Diogo Sousa aka orium
*  Copyright © 2008 Diogo Sousa
*
*  This program is free software: you can redistribute it and/or modify
*  it under the terms of the GNU General Public License as published by
*  the Free Software Foundation, either version 3 of the License, or
*  (at your option) any later version.
*
*  This program is distributed in the hope that it will be useful,
*  but WITHOUT ANY WARRANTY; without even the implied warranty of
*  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
*  GNU General Public License for more details.
*
*  You should have received a copy of the GNU General Public License
*  along with this program.  If not, see <http://www.gnu.org/licenses/>.
*/

#include <stdio.h>
#include <assert.h>

#include "rbtree.h"

struct integer
{
int n;
char *english;
};

int
my_cmp(const void *p1, const void *p2)
{
return ((struct integer *)p1)->n-((struct integer *)p2)->n;
}

void
my_twalk_action(void *data)
{
printf("%d %s\n",((struct integer *)data)->n,
       ((struct integer *)data)->english);
}

int
main(void)
{
struct rbtree *rbtree;
struct integer i1={1,"one"};
struct integer i2={2,"two"};
struct integer i3={3,"three"};	
struct integer i4={4,"four"};
struct integer i5={5,"five"};
struct integer lost={2,NULL};
struct integer *needle;

rbtree_init(&rbtree);

rbtree_insert(rbtree,&i1,my_cmp);
rbtree_insert(rbtree,&i2,my_cmp);
rbtree_insert(rbtree,&i3,my_cmp);
rbtree_insert(rbtree,&i4,my_cmp);
rbtree_insert(rbtree,&i5,my_cmp);

rbtree_walk(rbtree,my_twalk_action);

#if 1
rbtree_delete(rbtree,&lost,my_cmp);
putchar('\n');
rbtree_walk(rbtree,my_twalk_action);
putchar('\n');
#endif

needle=rbtree_search(rbtree,&lost,my_cmp);

if (needle == NULL)
{
	printf("Not found\n");
	rbtree_free(rbtree,NULL);
	return 0;
}

printf("%s\n",needle->english);

printf("height: %d\n",rbtree_height(rbtree));

rbtree_free(rbtree,NULL);

return 0;
}

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Crie uma conta ou ligue-se para comentar

Só membros podem comentar

Criar nova conta

Registe para ter uma conta na nossa comunidade. É fácil!


Registar nova conta

Entra

Já tem conta? Inicie sessão aqui.


Entrar Agora