[C] Implementazione albero red-black (BST)

[Krahos]

Avrei bisogno di aiuto nell'implementazione di un BST, il codice non presenta errori di sintassi ma errori logici in quanto appena cerco di inserire dei valori l'albero risulta sempre vuoto. C'è qualcuno che ha la pazienza di capire dov'è l'errore nella funzione di inserimento? o che abbia una implementazione con la quale possa confrontare? Grazie.

il codice che ho scritto è:

Bst.c

#include <stdlib.h>
#include "BST.h"

typedef struct STnode *link;

#define BST_INSERT_COLLISION 1

struct STnode {
    char red;
    Item item;
    Key key;
    link l, r;
};

struct bst {
    link head;
    int count;
};

link newNode(Item item, Key key, char red) {
    link local = malloc(sizeof(*local));
    if ((local) == NULL) {
        return NULL;
    }

    local->item = item;
    local->key = key;
    local->red = red;
    local->l = NULL;
    local->r = NULL;

    return local;
}

Bst newBst() {
    Bst local = malloc(sizeof(*local));
    if (local == NULL) {
        return NULL;
    }

    local->count = 0;

    local->head = NULL;

    return local;
}

int bstCount(Bst this) {
    return this->count;
}

Item bstSearchR(link this, Key key) {
    char comparison;

    if (this == NULL) {
        return nullItem;
    }

    if (!(comparison = keyCompare(this->key, key))) {
        return this->item;
    }
    else if (comparison == 1 && (this->r) != NULL) {
        return bstSearchR(this->r, key);
    }
    else if (comparison == 2 && (this->l) != NULL) {
        return bstSearchR(this->l, key);
    }
}

Item bstSearch(Bst this, Key key) {
    return bstSearchR(this->head, key);
}

link rotR(link this) {
    link x = this->l;
    this->l = x->r;
    x->r = this;
    return x;
}

link rotL(link this) {
    link x = this->r;
    this->r = x->l;
    x->l = this;
    return x;
}

int RBinsert(link *thisP, Item item, Key key, char red) {
    int comparison;
    link this = (*thisP);

    if (this == NULL) {
        if ((this = newNode(item, key, 'r')) == NULL) {
            (*thisP) = this;
            return 0;
        }
        else return -1;
    }

    //(going down in the recursion)divides the 4-nodes
    if (this->r != NULL && this->l != NULL) {
        if (((this->r->red) == 'r') && ((this->l->red) == 'r')) {
            this->red = 'r';
            this->r->red = 'b';
            this->l->red = 'b';
        }
    }

    //goes left if the key to insert is less
    //and if the insertion is successful
    //(going back to the root)controls if rotations are needed
    if ((comparison = keyCompare(key, this->key)) == 1) {
        if (!RBinsert(this->l, item, key, 'b')) {
            if (this->red == 'r' && red == 'r') {
                this = rotR(this);
            }

            if (this->red == 'r' && this->l->l->red == 'r') {
                this = rotR(this);
                this->red = 'b';
                this->red = 'r';
            }
        }
    }
    //goes right otherwise & (going back to the root)same controls
    else if (comparison == 2) {
        if (!RBinsert(this->r, item, key, 'r')) {
            if (this->r != NULL) {
                if (this->red == 'r' && this->r->red == 'r' && red == 'b') {
                    this = rotL(this);
                }
            }

            if ((this->r) != NULL){
                if (this->r->red == 'r' && this->r->r->red == 'r') {
                    this = rotL(this);
                    this->red = 'b';
                    this->l->red = 'r';
                }
            }
        }
    }
    else if (comparison == 0) {
        return BST_INSERT_COLLISION;
    }

    return 0;
}

int bstInsert(Bst this, Item item, Key key) {
    if (!(RBinsert(&(this->head), item, key, 0))) {
        this->head->red = '0';
        (this->count)++;
        return 0;
    }
    else {
        return 1;
    }
}

int STinsertR(link *this, Item item, Key key) {
    int comparison;
    link local = (*this);

    if (local == NULL) {
        local = newNode (item, key, 'r');
        (*this) = local;
        return 0;
    }
    else if ((comparison = keyCompare(local->key, key) == 1)) {
        STinsertR(&(local->r), item, key);
    }
    else if (comparison == 2) {
        STinsertR(&(local->l), item, key);
    }
    return BST_INSERT_COLLISION;
}

void bstVisitR(link this) {
    if (this == NULL) {
        return;
    }

    bstVisitR(this->l);
    itemVisit(this->item);
    bstVisitR(this->r);
}

void bstVisit(Bst this) {
    bstVisitR(this->head);
    return;
}

Bst.h

#ifndef BST_H
#define BST_H
#include "Item.h"

typedef struct bst *Bst;

Bst  newBst();
int  bstInsert(Bst, Item, Key);
int  bstCount(Bst this);
Item bstSearch(Bst this, Key key);
void bstVisit(Bst this);

#endif

Item.h

#ifndef ITEM_H
#define ITEM_H

#define nullItem NULL
#define nullKey NULL

typedef char* Item;
typedef char* Key;

int keyCompare(Key, Key);
void itemVisit(Item);

#endif

Item.c

#include <string.h>
#include "Item.h"

int keyCompare(char *str1, char *str2) {
    int tmp = strcmp(str1, str2);

    switch (tmp) {
    case 1: return 2;
    case -1: return 1;
    case 0: return 0;
    }
}

void itemVisit(char *str) {
    printf("%s", str);
    return;
}

Test.c

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

#define N 30

int main(void) {
    char uno[4] = "blab";
    char due[7] = "blabla";
    char tre[N] = "askis";
    char quattro[N] = "disas";
    char cinque[N] = "guaus";
    char sei[N] = "grssac";
    Bst bst = newBst();

    bstInsert(bst, uno, uno);
    bstInsert(bst, due, due);
    bstInsert(bst, tre, tre);
    bstInsert(bst, quattro, quattro);
    bstInsert(bst, cinque, cinque);
    bstInsert(bst, sei, sei);

    printf ("%d\n", bstCount(bst));

    bstVisit(bst);

    system("PAUSE");
    return 0;
}

[M.A.W. 1968]

Sfortunatamente non dispongo del tempo necessario alla revisione e correzione del tuo codice, ma ti segnalo una delle più diffuse reference implementation, basata quasi pedissequamente sugli algoritmi del CLRS. Anche se ingegneristicamente migliorabile sotto vari aspetti, è ottima per impieghi studenteschi.

[Krahos]

Grazie mille del supporto, conoscevo già questa implementazione ma l'avevo scartata perchè molto più complicata rispetto al mio codice (creato prendendo spunto da "Algoritmi in C" diRobert Sedgewick). Sto comunque cercando di capirci qualcosa.

[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;
}

[Vincenzo1968]

Parte seconda:

void TreeSuccessor(Tree *current, Tree **result)
{
    Tree *nodo = current;

    *result = pNil;

    if ( nodo == pNil )
        return;

    if ( nodo->right != pNil )
    {
        nodo = nodo->right;
        while ( nodo != pNil )
        {
            *result = nodo;
            nodo = nodo->left;
        }
    }
    else
    {
        *result = nodo->father;
        while ( *result != pNil && nodo == (*result)->right )
        {
            nodo = *result;
            *result = (*result)->father;
        }
    }
}

void TreePredecessor(Tree *current, Tree **result)
{
    Tree *nodo = current;

    *result = pNil;

    if ( nodo == pNil )
        return;

    if ( nodo->left != pNil )
    {
        nodo = nodo->left;
        while ( nodo != pNil )
        {
            *result = nodo;
            nodo = nodo->right;
        }
    }
    else
    {
        *result = nodo->father;
        while ( *result != NULL && nodo == (*result)->left )
        {
            nodo = *result;
            *result = (*result)->father;
        }
    }
}

void ReverseInOrder(Tree *head)
{
    Tree *temp;

    Tree *stack[MAX_STACK];
    int top;
    top = -1;

    if ( head == pNil )
        return;

    temp = head;

    while ( 1 )
    {
        if ( temp != pNil )
        {
            if ( top < MAX_STACK ) 
            {
                stack[++top] = temp; /* Push */
                temp = temp->right;
            }
            else
            {
                printf("Errore: lo stack e' pieno.\n");
                return;
            }
        }
        else
        {
            if ( top >= 0 )
            {
                temp = stack[top--]; /* Pop */
                printf("%d\n", temp->data);            
                temp = temp->left;
            }
            else
            {
                break;
            }
        }
    }
}

void InOrder(Tree *head)
{
    Tree *temp;

    Tree *stack[MAX_STACK];
    int top;
    top = -1;

    if ( head == pNil )
        return;

    temp = head;

    while ( 1 )
    {
        if ( temp != pNil )
        {
            if ( top < MAX_STACK ) 
            {
                stack[++top] = temp; /* Push */
                temp = temp->left;
            }
            else
            {
                printf("Errore: lo stack e' pieno.\n");
                return;
            }
        }
        else
        {
            if ( top >= 0 )
            {
                temp = stack[top--]; /* Pop */
                printf("%d\n", temp->data);            
                temp = temp->right;
            }
            else
            {
                break;
            }
        }
    }
}

void PreOrder(Tree *head)
{
    Tree *temp;

    Tree *stack[MAX_STACK];
    int top;
    top = 0;

    if ( head == pNil )
        return;

    temp = head;

    stack[top++] = temp; /* Push */

    while ( top != 0 )
    {
        temp = stack[--top]; /* Pop */

        printf("%d\n", temp->data);

        if ( temp->right != pNil )
            stack[top++] = temp->right;
        if ( temp->left != pNil )
            stack[top++] = temp->left;
    } 
}

void PostOrder(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; /* Push */

        while ( (temp1 != pNil) && (temp1->right == pNil || temp1->right == temp2) )
        {
            printf("%d\n", temp1->data);
            temp2 = temp1;
            if ( top == 0 )
                return;
            temp1 = stack[--top]; /* Pop */
        }

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

void SearchFirst(Tree *head, Tree **result, int key)
{
    Tree *node;

    *result = pNil;
    node = head;

    if ( head == pNil )
        return;

    while( 1 )
    {
        if ( key < node->data )
        {
            if ( node->left == pNil )
                break;
            node = node->left;
        }
        else if ( key > node->data )
        {
            if ( node->right == pNil )
                break;
            node = node->right;
        }
        else /* key == node->data */
        {
            *result = node;
            break;
        }
    }
}

void SearchNext(Tree *head, Tree **result, int key)
{
    Tree *node;

    *result = pNil;

    if ( head == pNil )
        return;

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

    while( 1 )
    {
        if ( key < node->data )
        {
            if ( node->left == pNil )
                break;
            node = node->left;
        }
        else if ( key > node->data )
        {
            if ( node->right == pNil )
                break;
            node = node->right;
        }
        else /* key == node->data */
        {
            *result = node;
            break;
        }
    }
}

void TreeMinimum(Tree *head, Tree **result)
{
    Tree *nodo = head;

    *result = pNil;

    if ( nodo == pNil )
        return;

    *result = nodo;

    while ( nodo != pNil )
    {
        *result = nodo;
        nodo = nodo->left;
    }
}

void TreeMaximum(Tree *head, Tree **result)
{
    Tree *nodo = head;

    *result = pNil;

    if ( nodo == pNil )
        return;

    *result = nodo;

    while ( nodo != pNil )
    {
        *result = nodo;
        nodo = nodo->right;
    }
}

int TreeSize(Tree *head)
{
    Tree *temp;
    int sizeLeft, sizeRight;

    Tree *stack[MAX_STACK];
    int top;
    top = -1;

    if ( !head )
        return 0;

    sizeLeft = sizeRight = 0;

    temp = head;

    while ( 1 )
    {
        if ( temp != pNil )
        {
            if ( top < MAX_STACK ) 
            {
                stack[++top] = temp; /* Push */
                temp = temp->left;
            }
            else
            {
                printf("Errore: lo stack e' pieno.\n");
                return - 1;
            }
        }
        else
        {
            if ( top >= 0 )
            {
                temp = stack[top--]; /* Pop */
                if ( temp->data < head->data )
                {
                    ++sizeLeft;
                }
                else 
                {
                    ++sizeRight;
                }
                temp = temp->right;
            }
            else
            {
                break;
            }
        }
    }

    return (sizeLeft + sizeRight);
}

int isTriangular(Tree *head)
{
    static int isTriang = 1;
    static int lDepth = 0; 
    static int rDepth = 0;

    if ( !head )
    {
        return 0;
    }
    else 
    {
        if ( (head->left && !(head->right)) || (head->right && !(head->left)) )
            isTriang = 0;

        isTriangular(head->left); 
        isTriangular(head->right);

        if (lDepth > rDepth)
        {
            lDepth++;
            return isTriang;
        }
        else
        {
            rDepth++;
            return isTriang;
        }
    } 
}

int TreeDepth(Tree *head)
{
    Tree *temp1, *temp2;

    int Conta;

    Tree *stack[MAX_STACK];
    int top;

    top = 0;
    Conta = 0;
 
    if ( head == pNil )
    {
        return -1;
    }

    temp1 = temp2 = head;

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

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

        stack[top++] = temp1;
        temp1 = temp1->right;
        if ( Conta < top )
            Conta = top;
    }

    return Conta + 1;
}

int main()
{
    int k;
    int SearchKey;

    int size;

    int depth;

    Tree *pSearch = NULL;
    Tree *pSuccessor = NULL;
    Tree *pPredecessor = NULL;
    Tree *pTree = NULL;

    InitNil(&pNil);


    pTree = pNil;
    pSearch = pNil;
    pSuccessor = pNil;
    pPredecessor = pNil;

    pTree = InsertNode(pTree, 47);
    pTree = InsertNode(pTree, 59);
    pTree = InsertNode(pTree, 14);
    pTree = InsertNode(pTree, 15);

    printf("\nstampa in ordine crescente(inorder):\n");
    InOrder(pTree);

    printf("\nstampa in PreOrder:\n");
    PreOrder(pTree);

    printf("\nstampa in PostOrder:\n");
    PostOrder(pTree);

    printf("\nstampa in ordine decrescente:\n");
    ReverseInOrder(pTree);

    size = TreeSize(pTree);
    printf("\nLa dimensione dell'albero e' -> %d\n", size);

    depth = TreeDepth(pTree);
    printf("\nL'altezza dell'albero e' -> %d\n", depth);


    k = -1;
    SearchKey = 8;
    SearchFirst(pTree, &pSearch, SearchKey);
    if ( pSearch != pNil )
        ++k;
    while ( pSearch != pNil )
    {
        SearchNext(pSearch, &pSearch, SearchKey);
        ++k;
    }
    if ( k < 0)
        k = 0;
    printf("\nTrovate %d occorrenze della chiave %d\n", k, SearchKey);


    pSearch = pNil;
    TreeMinimum(pTree, &pSearch);
    if ( pSearch )
        printf("\nIl valore minimo e' uguale a %d\n", pSearch->data);


    pPredecessor = pNil;
    TreePredecessor(pSearch, &pPredecessor);
    if ( pPredecessor != pNil )
        printf("\nIl predecessore del nodo con chiave %d, e' il nodo con chiave %d\n", pSearch->data, pPredecessor->data);
    else
        printf("\nIl nodo con chiave %d non ha predecessore.\n", pSearch->data);

    pSuccessor = pNil;
    TreeSuccessor(pSearch, &pSuccessor);
    if ( pSuccessor != pNil )
        printf("\nIl successore del nodo con chiave %d, e' il nodo con chiave %d\n", pSearch->data, pSuccessor->data);
    else
        printf("\nIl nodo con chiave %d non ha successore.\n", pSearch->data);

    pSearch = pNil;
    TreeMaximum(pTree, &pSearch);
    if ( pSearch )
        printf("\nIl valore massimo e' uguale a %d\n", pSearch->data);


    pPredecessor = pNil;
    TreePredecessor(pSearch, &pPredecessor);
    if ( pPredecessor != pNil )
        printf("\nIl predecessore del nodo con chiave %d, e' il nodo con chiave %d\n", pSearch->data, pPredecessor->data);
    else
        printf("\nIl nodo con chiave %d non ha predecessore.\n", pSearch->data);

    pSuccessor = pNil;
    TreeSuccessor(pSearch, &pSuccessor);
    if ( pSuccessor != pNil )
        printf("\nIl successore del nodo con chiave %d, e' il nodo con chiave %d\n", pSearch->data, pSuccessor->data);
    else
        printf("\nIl nodo con chiave %d non ha successore.\n", pSearch->data);


    SearchKey = 55;
    pSearch = pNil;
    SearchFirst(pTree, &pSearch, SearchKey);

    if ( pSearch != pNil )
    {
        printf("\nIl valore della radice, prima della cancellazione, e' -> %d\n", pTree->data);

        printf("Cancellazione della radice %d\n", pTree->data);
        pTree = DeleteNode(pTree, pTree);

        printf("\nIl valore della radice, dopo la cancellazione, e' -> %d\n", pTree->data);
    }


    size = TreeSize(pTree);
    printf("\nLa dimensione dell'albero, dopo le operazioni precedenti, e' -> %d\n", size);

    depth = TreeDepth(pTree);
    printf("\nL'altezza dell'albero, dopo le operazioni precedenti, e' -> %d\n", depth);

    printf("\nstampa in ordine crescente(inorder):\n");
    InOrder(pTree);

    if ( isTriangular(pTree) )
        printf("\nL'albero e' triangolare!\n");
    else
        printf("\nL'albero non e' affatto triangolare!!!\n");

    FreeTree(pTree);
    FreeTree(pNil);

    return 0;
}

[Vincenzo1968]

Questo è l'output:

[vincenzo]$ ls
RedBlackTrees.c

[vincenzo]$ gcc -Wall -W -pedantic -O2 RedBlackTrees.c -o rbt

[vincenzo]$ ./rbt

Inserisco la radice -> 47
Inserisco 59 a destra di 47
Inserisco 14 a sinistra di 47
Inserisco 15 a destra di 14

stampa in ordine crescente(inorder):
14
15
47
59

stampa in PreOrder:
47
14
15
59

stampa in PostOrder:
15
14
59
47

stampa in ordine decrescente:
59
47
15
14

La dimensione dell'albero e' -> 4

L'altezza dell'albero e' -> 2

Trovate 0 occorrenze della chiave 8

Il valore minimo e' uguale a 14

Il nodo con chiave 14 non ha predecessore.

Il successore del nodo con chiave 14, e' il nodo con chiave 15

Il valore massimo e' uguale a 59

Il predecessore del nodo con chiave 59, e' il nodo con chiave 47

Il nodo con chiave 59 non ha successore.

La dimensione dell'albero, dopo le operazioni precedenti, e' -> 4

L'altezza dell'albero, dopo le operazioni precedenti, e' -> 2

stampa in ordine crescente(inorder):
14
15
47
59

L'albero e' triangolare!

[Vincenzo1968]

Ho modificato il main per illustrare l'eliminazione dei nodi:

int main()
{
    int k;
    int SearchKey;

    int size;

    int depth;

    Tree *pSearch = NULL;
    Tree *pSuccessor = NULL;
    Tree *pPredecessor = NULL;
    Tree *pTree = NULL;

    InitNil(&pNil);


    pTree = pNil;
    pSearch = pNil;
    pSuccessor = pNil;
    pPredecessor = pNil;

    pTree = InsertNode(pTree, 5);
    pTree = InsertNode(pTree, 4);
    pTree = InsertNode(pTree, 3);
    pTree = InsertNode(pTree, 8);
    pTree = InsertNode(pTree, 34);
    pTree = InsertNode(pTree, 21);
    pTree = InsertNode(pTree, 89);
    pTree = InsertNode(pTree, 8);
    pTree = InsertNode(pTree, 8);
    pTree = InsertNode(pTree, 55);
    pTree = InsertNode(pTree, 8);

    printf("\nstampa in ordine crescente(inorder):\n");
    InOrder(pTree);

    printf("\nstampa in PreOrder:\n");
    PreOrder(pTree);

    printf("\nstampa in PostOrder:\n");
    PostOrder(pTree);

    printf("\nstampa in ordine decrescente:\n");
    ReverseInOrder(pTree);

    size = TreeSize(pTree);
    printf("\nLa dimensione dell'albero e' -> %d\n", size);

    depth = TreeDepth(pTree);
    printf("\nL'altezza dell'albero e' -> %d\n", depth);


    printf("\nIl valore della radice, prima della cancellazione e' -> %d\n", pTree->data);
    SearchKey = 21;
    /* SearchKey = 5; */
    SearchFirst(pTree, &pSearch, SearchKey);
    if ( pSearch != pNil )
    {
        pTree = DeleteNode(pTree, pSearch);
        printf("\nIl valore della radice, dopo la cancellazione e' -> %d\n", pTree->data);
    }

    depth = TreeDepth(pTree);
    printf("\nL'altezza dell'albero e' -> %d\n", depth);

    k = -1;
    SearchKey = 8;
    SearchFirst(pTree, &pSearch, SearchKey);
    if ( pSearch != pNil )
        ++k;
    while ( pSearch != pNil )
    {
        SearchNext(pSearch, &pSearch, SearchKey);
        ++k;
    }
    if ( k < 0)
        k = 0;
    printf("\nTrovate %d occorrenze della chiave %d\n", k, SearchKey);


    pSearch = pNil;
    TreeMinimum(pTree, &pSearch);
    if ( pSearch )
        printf("\nIl valore minimo e' uguale a %d\n", pSearch->data);

    pPredecessor = pNil;
    TreePredecessor(pSearch, &pPredecessor);
    if ( pPredecessor != pNil )
        printf("\nIl predecessore del nodo con chiave %d, e' il nodo con chiave %d\n", pSearch->data, pPredecessor->data);
    else
        printf("\nIl nodo con chiave %d non ha predecessore.\n", pSearch->data);

    pSuccessor = pNil;
    TreeSuccessor(pSearch, &pSuccessor);
    if ( pSuccessor != pNil )
        printf("\nIl successore del nodo con chiave %d, e' il nodo con chiave %d\n", pSearch->data, pSuccessor->data);
    else
        printf("\nIl nodo con chiave %d non ha successore.\n", pSearch->data);

    pSearch = pNil;
    TreeMaximum(pTree, &pSearch);
    if ( pSearch )
        printf("\nIl valore massimo e' uguale a %d\n", pSearch->data);


    pPredecessor = pNil;
    TreePredecessor(pSearch, &pPredecessor);
    if ( pPredecessor != pNil )
        printf("\nIl predecessore del nodo con chiave %d, e' il nodo con chiave %d\n", pSearch->data, pPredecessor->data);
    else
        printf("\nIl nodo con chiave %d non ha predecessore.\n", pSearch->data);

    pSuccessor = pNil;
    TreeSuccessor(pSearch, &pSuccessor);
    if ( pSuccessor != pNil )
        printf("\nIl successore del nodo con chiave %d, e' il nodo con chiave %d\n", pSearch->data, pSuccessor->data);
    else
        printf("\nIl nodo con chiave %d non ha successore.\n", pSearch->data);

    SearchKey = 89;
    pSearch = pNil;
    SearchFirst(pTree, &pSearch, SearchKey);
    pTree = DeleteNode(pTree, pSearch);
    printf("\nstampa in ordine crescente dopo la cancellazione del nodo con chiave %d :\n", SearchKey);
    InOrder(pTree);

    SearchKey = 5;
    pSearch = pNil;
    SearchFirst(pTree, &pSearch, SearchKey);
    pTree = DeleteNode(pTree, pSearch);
    printf("\nstampa in ordine crescente dopo la cancellazione del nodo con chiave %d :\n", SearchKey);
    InOrder(pTree);

    SearchKey = 55;
    pSearch = pNil;
    SearchFirst(pTree, &pSearch, SearchKey);

    if ( pSearch != pNil )
    {
        printf("\nIl valore della radice, prima della cancellazione, e' -> %d\n", pTree->data);

        printf("Cancellazione della radice %d\n", pTree->data);
        pTree = DeleteNode(pTree, pTree);

        printf("\nIl valore della radice, dopo la cancellazione, e' -> %d\n", pTree->data);
    }


    size = TreeSize(pTree);
    printf("\nLa dimensione dell'albero, dopo le operazioni precedenti, e' -> %d\n", size);

    depth = TreeDepth(pTree);
    printf("\nL'altezza dell'albero, dopo le operazioni precedenti, e' -> %d\n", depth);

    printf("\nstampa in ordine crescente(inorder):\n");
    InOrder(pTree);

    FreeTree(pTree);
    FreeTree(pNil);

    return 0;
}

Output:

[vincenzo]$ gcc -Wall -W -pedantic -O2 RedBlackTrees.c -o rbt

[vincenzo]$ ./rbt

Inserisco la radice -> 5
Inserisco 4 a sinistra di 5
Inserisco 3 a sinistra di 4
Inserisco 8 a destra di 5
Inserisco 34 a destra di 8
Inserisco 21 a sinistra di 34
Inserisco 89 a destra di 34
Inserisco 8 a sinistra di 21
Inserisco 8 a destra di 8
Inserisco 55 a sinistra di 89
Inserisco 8 a sinistra di 21

stampa in ordine crescente(inorder):
3
4
5
8
8
8
8
21
34
55
89

stampa in PreOrder:
8
4
3
5
34
8
8
21
8
89
55

stampa in PostOrder:
3
5
4
8
8
21
8
55
89
34
8

stampa in ordine decrescente:
89
55
34
21
8
8
8
8
5
4
3

La dimensione dell'albero e' -> 11

L'altezza dell'albero e' -> 4

Il valore della radice, prima della cancellazione e' -> 8

Il valore della radice, dopo la cancellazione e' -> 8

L'altezza dell'albero e' -> 3

Trovate 3 occorrenze della chiave 8

Il valore minimo e' uguale a 3

Il nodo con chiave 3 non ha predecessore.

Il successore del nodo con chiave 3, e' il nodo con chiave 4

Il valore massimo e' uguale a 89

Il predecessore del nodo con chiave 89, e' il nodo con chiave 55

Il nodo con chiave 89 non ha successore.

stampa in ordine crescente dopo la cancellazione del nodo con chiave 89 :
3
4
5
8
8
8
8
34
55

stampa in ordine crescente dopo la cancellazione del nodo con chiave 5 :
3
4
8
8
8
8
34
55

Il valore della radice, prima della cancellazione, e' -> 8
Cancellazione della radice 8

Il valore della radice, dopo la cancellazione, e' -> 8

La dimensione dell'albero, dopo le operazioni precedenti, e' -> 7

L'altezza dell'albero, dopo le operazioni precedenti, e' -> 3

stampa in ordine crescente(inorder):
3
4
8
8
8
34
55