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

codice:
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