Drzewa czerwono-czarne

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

#define TRUE 1
#define FALSE 0

struct node
{
 enum { BLACK, RED } color;
 unsigned int value;
 struct node *left, *right, *parent;
};


void dopisz();
struct node* newNode(int tValue, char tColor);
void print(struct node *tmp,unsigned h,unsigned long long M);
void rotateLeft(struct node *x);
void rotateRight(struct node *x);
void insertFixup(struct node *x);
int findNode(unsigned int value);
struct node *insertNode(unsigned int value);


struct node *root = 0;

int main()
{
    int isEnd = FALSE;
	char answer[100];
	while(!isEnd)
	{
		printf("\n\t\tMENU\n");
		printf("[0] - zakonczenie programu\n");
                printf("[1] - dopisanie\n");
                printf("[2] - usuniecie\n");
                printf("[3] - wyswietlenie zawartosci drzewa\n");
		scanf("%s", answer);

                switch(answer[0])
                {
                        case '0':
                                printf("Zakonczenie!\n");
                                isEnd=TRUE;
                                break;
                        case '1':
                                dopisz();
                                break;
                        case '2':
                                //bedzie potem
                                break;
                        case '3':
                                print(root, 0, 0);
                                break;
                        default:
                                printf("Bledny wybor...\n");
                }
	}
	return 0;
}

struct node *insertNode(unsigned int value)
{
    struct node *current, *parent, *x;
    current = root;
    parent = NULL;
    while (current != NULL)
    {
        if (value == current->value) return (current);
            parent = current;
        current = (value > current->value) ?
            current->left : current->right;
    }

    if ((x = malloc (sizeof(*x))) == 0)
    {
        printf ("Brak pamieci\n");
        exit(1);
    }

    x->value = value;
    x->parent = parent;
    x->left = NULL;
    x->right = NULL;
    x->color = RED;

    if(parent)
    {
        if(value > parent->value)
            parent->left = x;
        else
            parent->right = x;
    }
    else
    {
        root = x;
    }

    insertFixup(x);
    return x;
}

void insertFixup(struct node *x)
{


    while (x != root && x->parent->color == RED)
    {
        if (x->parent == x->parent->parent->left)
        {
            struct node *y = x->parent->parent->right;
            if (y->color == RED)
            {
                x->parent->color = BLACK;
                y->color = BLACK;
                x->parent->parent->color = RED;
                x = x->parent->parent;

            }
            else
            {
                if (x == x->parent->right)
                {
                    x = x->parent;
                    rotateLeft(x);
                }
                x->parent->color = BLACK;
                x->parent->parent->color = RED;
                rotateRight(x->parent->parent);
            }
        }
        else
        {
            struct node *y = x->parent->parent->left;
            if (y->color == RED)
            {
                x->parent->color = BLACK;
                y->color = BLACK;
                x->parent->parent->color = RED;
                x = x->parent->parent;
            }
            else
            {
                if (x == x->parent->left)
                {
                    x = x->parent;
                    rotateRight(x);
                }
                x->parent->color = BLACK;
                x->parent->parent->color = RED;
                rotateLeft(x->parent->parent);
            }
        }
    }
    root->color = BLACK;
}

void rotateLeft(struct node *x)
{

    struct node *y = x->right;
    x->right = y->left;
    if (y->left != NULL) y->left->parent = x;

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

void rotateRight(struct node *x)
{
    struct node *y = x->left;

    x->left = y->right;
    if (y->right != NULL) y->right->parent = x;

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

void dopisz()
{
    unsigned int tValue;
    printf("Wartosc: ");
    scanf("%d", &tValue);
    if(findNode(tValue))
    {
        insertNode(tValue);
        printf("Dodano!\n");
    }
    else printf("Blad, podany klucz juz istnieje!");
}


int findNode(unsigned int value)
{
    struct node *current = root;
    while(current != NULL)
    if(value == current->value)
        return FALSE;
    else
        current = (value > current->value) ?
        current->left : current->right;
    return TRUE;
}

void print(struct node *tmp,unsigned h,unsigned long long M)
{
	unsigned int i;
    if(tmp->left) print(tmp->left,h+1,M<<1);
        for(i=h-2;i<h;--i)
        {
            unsigned long long m=(M>>i)&3;
            if((m==0)||(m==3)) printf(" "); else printf("\xB3");
            printf(" ");
        }
    if(h)
    {
        if(M&1) printf("\xC0"); else printf("\xDA");
            printf("\xC4");
    }
    printf("\xDB%d", tmp->value);
    if(tmp->color == RED) printf("R\n");
    else printf("B\n");
    if(tmp->right) print(tmp->right,h+1,(M<<1)|1);
}

Nie wiem czemu, ale sypie mi się dla danych malejących, np: 3, 2, 1. Jak daję zróżnicowane wartości, to wszystko super śmiga. Czy ktoś z Was może mi powiedzieć co tu jest nie tak?
Podejrzewam te długie tasiemce:

x->parent->parent->left

Tylko w jaki sposób to zastąpić, jeżeli faktycznie jest to przyczyną problemu?

Nikt nie ma żadnego pomysłu?
Patrzyłem jak jest to napisane w Cormenie, ale tam w funkcji insertu jest jakiś 'y', który nie jest w ogóle opisany. : |

Mało czasu dajesz myślisz, że wszyscy tu siedzą non stop? Co do Cormena to nie mam pod ręką, ale tam założeń przed kodem nie ma np., że gdy nie istnieje node to przyjmujesz jaki kolor ma? Sprawdź funkcję fixup, w szczególności linie zawierajace

if (y->color == RED)

bo zapewne y = NULL.

W wikipedii jest

Każdy liść jest czarny (Można traktować nil jako liść).

No tak, sypie się w fixupie, właśnie z tym y, a dokładniej z przypisywaniem mu wskaźników na coś, co nie istnieje. I tu jest problem, na co to zamienić, aby działało.

if ((y)&&(y->color == RED))

Teraz działa, fakt. :) Ciekawe tylko, czy algorytm jest poprawnie skonstruowany. Ma ktoś z Was jakiegoś linka do gotowej implementacji, najlepiej graficznej, gdzie można się sprawdzić? Choć wygląda poprawnie, tzn spełnia te najważniejsze założenia drzewa.