[C] drzewo czerwono-czarne (implementacja w c)

Napisalem sobie dzis drzewo czerwono czarne, jednak przy dodawaniu nowego elementu rzuca segmentation fault, wiekszosc kodu jest ok, bo wczoraj pisalem zwykle drzewo bst i dzialalo ok.

#include <stdio.h>
#include <stdlib.h> //dla exit
#define RED 0
#define BLACK 1
typedef struct t_node
{
	int key;
	struct t_node *left;
	struct t_node *right;
	struct t_node *p;
	int kolor;
} node;

node *TN=NULL;

void l_rotate(node **head, node** x);
void r_rotate(node** head, node** x);
void rb_insert(node **head, int k);
void rb_insert_fixup(node** head, node** z);
void node_out(int level, node *nd);
void inorder_tree_walk(int level, node *head);
//void tree_insert(node **head, int k);
node* tree_search(node *temp, int k);
node* iterative_tree_search(node *head, int k);
node* tree_minimum(node* head);
node* tree_maximum(node *head);
node* tree_succesor(node *h);

//node* tree_delete(node *h, int k);


void menu();


node *head=NULL;
node *h=NULL;


.
.
.


void rb_insert(node **head, int k)
{
	node *z=(node *)malloc(sizeof(node));
	z->key=k;
	z->left=NULL;
	z->right=NULL;

	node* y=NULL;
	node* x=(*head);
	while (x!=NULL)
	{
		y=x;
		if (z->key < x->key)
			x=x->left;
		else
			x=x->right;
	}

	z->p=y;

	if (y==NULL)
		*(head)=z;
	else if (z->key < y->key)
		y->left=z;
		else
			y->right=z;

	z->left = TN;
	z->right = TN;
	z->kolor = RED;
	rb_insert_fixup(head, &z);
}
////////////////////////////////////////////////////////////////////////////////////////
void l_rotate(node** head, node** x)   //x i head moga byc tu modyfikowane wiec koniecznie trzeba wskaznik na wskaznik, prawda? ;)
{
	node *y = (*x)->right;
	(*x)->right=y->left;
	y->left->p =(*x);
	y->p =(*x)->p;

	if ((*x)->p == TN)
		(*head)=y;
	else if ((*x) == (*x)->p->left)
		(*x)->p->left = y;
		else
			(*x)->p->right = y;
	y->left = (*x);
	(*x)->p = y;
}
///////////////////////////////////////////////////////////////////////////////
void r_rotate(node** head, node** x)
{
	node *y = (*x)->left;
	(*x)->left=y->right;
	y->right->p =(*x);
	y->p =(*x)->p;

	if ((*x)->p == TN)
		(*head)=y;
	else if ((*x) == (*x)->p->right)
		(*x)->p->right = y;
		else
			(*x)->p->left = y;
	y->right = (*x);
	(*x)->p = y;
}
/////////////////////////////////////////////////////////////////////////////////////
void rb_insert_fixup(node** head, node** z) //podobnie koniecznie **    ?
{
	node *y=NULL;
	while ((*z)->p->kolor == RED)
	{
		if ((*z)->p==(*z)->p->p->left)
		{
			y=(*z)->p->p->right;
			if (y->kolor == RED)
			{
				(*z)->p->kolor = BLACK;
				y->kolor = BLACK;
				(*z)->p->p->kolor = RED;
				*z = (*z)->p->p;
			}
			else if (*z==(*z)->p->right)
			{
				*z = (*z)->p;
				l_rotate(head, z);
				(*z)->p->kolor = BLACK;
				(*z)->p->p->kolor = RED;
				r_rotate(head, &(*z)->p->p);
			}
			else
			{
				*z = (*z)->p;
				r_rotate(head, z);
				(*z)->p->kolor = BLACK;
				(*z)->p->p->kolor = RED;
				l_rotate(head, &(*z)->p->p);	
			}
		}
	}
	(*head)->kolor=BLACK;
}

hmm, tak jesli chcesz mofyfikowac to na co poakzuje wskaznik we funckji musisz skorzystac ze wskaznika na wskaznik...

co do drugiego pytania, nie wiem dlaczego to nie dziala, ale moze jeszcze ktos na to spojrzy i bedzie mial jakis pomysl ;)

ok, no wiesz, sam tez nie wiem juz czemu ten segmentation... xD

postanowilem sobie w tym miesiacu zaimplementowac w C wszystkie aalgorytmy z Cormena, a juz po 1/3 ksiazki sie zacialem xD

lekko poprawilem, nie wyrzuca segmentation, nawet dziala, ale po dodaniu kilku elementow, gdy dodaje kolejny jest tak:

podaj wartosc:
12 //tu podaje i zamiast po enterze zakonczyc (tak dzialalo dla wczensiejszych elementow)
.
. //nie przerywa tego tylko w kolo mozna podawac wartosci
.

Dlaczego sie tak dzieje?

i dlaczego w rotacjach i naprawieniu po dodaniu elementu nie trzeba korzystac z wskaznika na wskaznik, przeciez modyfikujemy wskazniki?

#include <stdio.h>
#include <stdlib.h> //dla exit
#define RED 0
#define BLACK 1
typedef struct t_node
{
	int key;
	struct t_node *left;
	struct t_node *right;
	struct t_node *p;
	int kolor;
} node;

node* TN=NULL;

void rb_insert(node **head, int k)
{
	node *z=(node *)malloc(sizeof(node));
	z->key=k;
	z->left=NULL;
	z->right=NULL;

	node* y=NULL;
	node* x=(*head);
	while (x!=NULL)
	{
		y=x;
		if (z->key < x->key)
			x=x->left;
		else
			x=x->right;
	}

	z->p=y;

	if (y==NULL)
		*(head)=z;
	else if (z->key < y->key)
		y->left=z;
		else
			y->right=z;

	z->left = TN;
	z->right = TN;
	z->kolor = RED;
	rb_insert_fixup(*head, z);
}
////////////////////////////////////////////////////////////////////////////////////////
void l_rotate(node* head, node* x)
{
	node *y = x->right;
	x->right=y->left;
	y->left->p =x;
	y->p =x->p;

	if (x->p == TN)
		head=y;
	else if (x == x->p->left)
		x->p->left = y;
		else
			x->p->right = y;
	y->left = x;
	x->p = y;
}
///////////////////////////////////////////////////////////////////////////////
void r_rotate(node* head, node* x)
{
	node *y = x->left;
	x->left=y->right;
	y->right->p =x;
	y->p =x->p;

	if (x->p == TN)
		head=y;
	else if (x == x->p->right)
		x->p->right = y;
		else
			x->p->left = y;
	y->right = x;
	x->p = y;
}
/////////////////////////////////////////////////////////////////////////////////////
void rb_insert_fixup(node* head, node* z)
{
	node *y=NULL;
	while (z!=head && z->p->kolor==RED)
	{
		if (z->p==z->p->p->left)
		{
			y=z->p->p->right;
			if (y->kolor == RED)
			{
				z->p->kolor = BLACK;
				y->kolor = BLACK;
				z->p->p->kolor = RED;
				z = z->p->p;
			}
			else if (z==z->p->right)
			{
				z = z->p;
				l_rotate(head, z);
				z->p->kolor = BLACK;
				z->p->p->kolor = RED;
				r_rotate(head, z);
			}
			else
			{
				z = z->p;
				r_rotate(head, z);
				z->p->kolor = BLACK;
				z->p->p->kolor = RED;
				l_rotate(head, z);	
			}
		}
	}
	head->kolor=BLACK;
}

skompilowalem sobie ten kod i dzienie to dziala

wersja 1 (rotacje i fix_up z ** w definicji w liscie parametrow)

• wydaje sie, ze tak powinno byc, tylko tak, ten program w ogóle nie dziala -> segmentation

wersja 2 (rotacje, i fix_up z * w def. listy parametrow)
-program dziala prawie ze idealnie, mozna dodawac nowe elementy, nie mozna dodac tylko:
po kolei 3 coraz mniejszyc elementow - segmentation
po kolei 3 coraz wiekszych elementow - program jakby przesaje odpowiadac, choc nie zawisza sie

inne kombinacje podawania elementow - wszystko ok...

ciekawe dlaczego tak sie dzieje (teoretycznie wersja ktora nie powinna dzialac - > dziala, a ta co powinna dzialac - > nie dziala xD)

owen - strasznie mnie to ciekawi, dlaczego sie tak dzieje, ale ja sam Ci wiecej juz nie pomoge, nie mam pomyslu...

moze ktos ma na tyle duza wiedze, by sie tu wypowiedziec? :)

tak się zastanawiam, czy może zaistnieć sytuacja, dla której fragment

z->p->p->left

nie sięga "za daleko" tzn. z->p

 wskazuje na root, który przecież nie ma rodzica?

no ok, ale wtedy chyba po prostu warunek if'a bedzie niespelniony i fix_up nie bdzie mial wiele pracy

takie coś

	node head;
	head.key = 1;
	head.kolor = BLACK;
	head.left = NULL;
	head.right = NULL;
	head.p = NULL;
	node* p_head = &head;
	rb_insert(&p_head, 10);
	rb_insert(&p_head, 11);

powoduje, że rb_insert_fixup nie wychodzi z while'a. Brakuje jakiegoś warunku.