[C] Implementazione albero red-black (BST)

[Vincenzo1968]

Questa è una mia implementazione in C dell'algoritmo illustrato nel libro Introduzione agli algoritmi e strutture dati di Cormen, Leiserson, Rivest e Stein:

Devo separare il codice in due post perché è troppo lungo e non me lo fa inserire:



Parte prima:

#include <stdio.h>
#include <malloc.h>

#define MAX_STACK 100

typedef struct tagTree
{
    int data;
    char color;
    struct tagTree *father;
    struct tagTree *left;
    struct tagTree *right;
} Tree;

Tree *pNil = NULL;

Tree *NewNode(int info);
Tree *InsertNode(Tree *node, int key);
void InsertFixup(Tree **head, Tree **z);
Tree *DeleteNode(Tree *root, Tree *z);
void DeleteFixup(Tree **head, Tree **x);
void FreeTree(Tree *head);

void InitNil(Tree **p);

Tree *TreeRotateLeft(Tree *head, Tree *node);
Tree *TreeRotateRight(Tree *head, Tree *node);
void TreeSuccessor(Tree *current, Tree **result);
void TreePredecessor(Tree *current, Tree **result);

void ReverseInOrder(Tree *head);
void InOrder(Tree *head);
void PreOrder(Tree *head);
void PostOrder(Tree *head);

void SearchFirst(Tree *head, Tree **result, int key);
void SearchNext(Tree *head, Tree **result, int key);
void TreeMinimum(Tree *head, Tree **result);
void TreeMaximum(Tree *head, Tree **result);

int TreeSize(Tree *head);
int TreeDepth(Tree *head);

int IsTriangular(Tree *head);

void InitNil(Tree **p)
{
    *p = NewNode(0);
    if ( *p )
    {
        (*p)->data = 0;
        (*p)->color = 'b';
        (*p)->left = NULL;
        (*p)->right = NULL;
        (*p)->father = NULL;
    }
    else
    {
        printf("Errore nell'inizializzazione di pNil.\n");
    }
}

Tree *NewNode(int info)
{
    Tree *r;

    r = (Tree *) malloc(sizeof(Tree));

    if( !r )
    {
        printf("Memoria insufficiente.\n");
        return pNil;
    }

    r->data = info;
    r->color = 'b'; /* 'b' = Black; 'r' = Red */
    r->father = pNil;
    r->left = pNil;
    r->right = pNil;

    return r;
}

Tree *InsertNode(Tree *node, int key)
{
    Tree *z = pNil;
    Tree *y = pNil;
    Tree *pRadice = pNil;

    z = NewNode(key);
    if ( z == pNil )
        return pNil;

    pRadice = node;

    while ( pRadice != pNil )
    {
        y = pRadice;
        if ( z->data < pRadice->data )
            pRadice = pRadice->left;
        else
            pRadice = pRadice->right;
    }

    z->father = y;
    if ( y == pNil )
    {
        printf("Inserisco la radice -> %d\n", key);

        node = z;
    }
    else
    {
        if ( z->data < y->data )
        {
            printf("Inserisco %d a sinistra di %d\n", z->data, y->data);

            y->left = z;
        }
        else
        {
            printf("Inserisco %d a destra di %d\n", z->data, y->data);

            y->right = z;
        }
    }

    z->left = pNil;
    z->right = pNil;
    z->color = 'r'; /* Red */

    InsertFixup(&node, &z);

    return node;
}

void InsertFixup(Tree **head, Tree **z)
{
    Tree *y = pNil;

    while ( (*z)->father->color == 'r' )
    {
        if ( (*z)->father == (*z)->father->father->left )
        {
            y = (*z)->father->father->right;
            if ( y->color == 'r' )
            {
                (*z)->father->color = 'b';
                y->color = 'b';
                (*z)->father->father->color = 'r';
                *z = (*z)->father->father;
            }
            else 
            {
                if ( *z == (*z)->father->right )
                {
                    *z = (*z)->father;
                    *head = TreeRotateLeft(*head, *z);
                }
                (*z)->father->color = 'b';
                (*z)->father->father->color = 'r';
                *head = TreeRotateRight(*head, (*z)->father->father);
            }
        }
        else
        {
            y = (*z)->father->father->left;
            if ( y->color == 'r' )
            {
                (*z)->father->color = 'b';
                y->color = 'b';
                (*z)->father->father->color = 'r';
                *z = (*z)->father->father;
            }
            else 
            {
                if ( *z == (*z)->father->left )
                {
                    *z = (*z)->father;
                    *head = TreeRotateRight(*head, *z);
                }
                (*z)->father->color = 'b';
                (*z)->father->father->color = 'r';
                *head = TreeRotateLeft(*head, (*z)->father->father);
            }
        }
    }

    (*head)->color = 'b';
}

Tree *DeleteNode(Tree *root, Tree *z)
{
    Tree *y = pNil;
    Tree *x = pNil;

    if ( root == pNil || z == pNil )
        return root;

    if ( z->left == pNil || z->right == pNil )
        y = z;
    else
        TreeSuccessor(z, &y);

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

    x->father = y->father;

    if ( y->father == pNil )
    {
        root = x;
    }
    else
    {
        if ( y == y->father->left )
            y->father->left = x;
        else
            y->father->right = x;
    }

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

    if ( y->color == 'b' )
        DeleteFixup(&root, &x);

    free(y);

    return root;
}

void DeleteFixup(Tree **head, Tree **x)
{
    Tree *w = pNil;

    while ( *x != *head && (*x)->color == 'b' )
    {
        if ( *x == (*x)->father->left )
        {
            w = (*x)->father->right;
            if ( w->color == 'r' )
            {
                w->color = 'b';
                (*x)->father->color = 'r';
                *head = TreeRotateLeft(*head, (*x)->father);
                w = (*x)->father->right;
            }

            if ( w->left->color == 'b' && w->right->color == 'b' )
            {
                w->color = 'r';
                (*x) = (*x)->father;
            }
            else
            {
                if ( w->right->color == 'b' )
                {
                    w->left->color = 'b';
                    w->color = 'r';
                    *head = TreeRotateRight(*head, w);
                    w = (*x)->father->right;
                }

                w->color = (*x)->father->color;
                (*x)->father->color = 'b';
                w->right->color = 'b';
                *head = TreeRotateLeft(*head, (*x)->father);
                *x = *head;
            }
        }
        else
        {
            w = (*x)->father->left;
            if ( w->color == 'r' )
            {
                w->color = 'b';
                (*x)->father->color = 'r';
                *head = TreeRotateRight(*head, (*x)->father);
                w = (*x)->father->left;
            }

            if ( w->right->color == 'b' && w->left->color == 'b' )
            {
                w->color = 'r';
                (*x) = (*x)->father;
            }
            else
            {
                if ( w->left->color == 'b' )
                {
                    w->right->color = 'b';
                    w->color = 'r';
                    *head = TreeRotateLeft(*head, w);
                    w = (*x)->father->left;
                }

                w->color = (*x)->father->color;
                (*x)->father->color = 'b';
                w->left->color = 'b';
                *head = TreeRotateRight(*head, (*x)->father);
                *x = *head;
            }
        }
    }

    (*x)->color = 'b';
}

void FreeTree(Tree *head)
{
    Tree *temp1, *temp2;

    Tree *stack[MAX_STACK];
    int top;

    top = 0;
 
    if ( head == pNil )
        return;

    temp1 = temp2 = head;

    while ( temp1 != pNil )
    {
        for(; temp1->left != pNil; temp1 = temp1->left)
            stack[top++] = temp1;

        while ( (temp1 != pNil) && (temp1->right == pNil || temp1->right == temp2) )
        {
            temp2 = temp1;
            free(temp2);
            if ( top == 0 )
                return;
            temp1 = stack[--top];
        }

        stack[top++] = temp1;
        temp1 = temp1->right;
    }
}

Tree *TreeRotateLeft(Tree *head, Tree *node)
{
    Tree *y;

    if ( head == pNil || node == pNil )
        return head;

    if ( node->right == pNil )
        return head;

    y = node->right;
    node->right = y->left;

    if ( y->left != pNil )
    {
        y->left->father = node;
    }

    y->father = node->father;

    if ( node->father == pNil )
    {
        head = y;
    }
    else
    {
        if ( node == node->father->left )
        {
            node->father->left = y;
        }
        else
        {
            node->father->right = y;
        }
    }

    y->left = node;
    node->father = y;

    return head;
}

Tree *TreeRotateRight(Tree *head, Tree *node)
{
    Tree *y;

    if ( head == pNil || node == pNil )
        return head;

    if ( node->left == pNil )
        return head;

    y = node->left;
    node->left = y->right;

    if ( y->right != pNil )
    {
        y->right->father = node;
    }

    y->father = node->father;

    if ( node->father == pNil )
    {
        head = y;
    }
    else
    {
        if ( node == node->father->right )
        {
            node->father->right = y;
        }
        else
        {
            node->father->left = y;
        }
    }

    y->right = node;
    node->father = y;

    return head;
}