Lösung Aufgabe 17 (14 Programmierpunkte - Abgabe per email)

}/* aufgabe 17 */
#define FEHLER 1000
#include <stdio.h>
static insert_baum_000000_co();
static print_baum_000000_co();
static delete_baum_000000_co();

struct knoten {
         struct knoten *links;
         struct knoten *rechts;
         int wert;
         int rang;
         };

#define RECHTERNACHFOLGERSCHWARZ(a) \
                ( ((*a) -> rechts == NULL) || \
                  ((*a)->rechts->rang < ((*a)->rang)) )
#define LINKERNACHFOLGERSCHWARZ(a) \
                ( ((*a) -> links == NULL) || \
                  ((*a)->links->rang < ((*a)->rang)) )

struct knoten *new_knoten(int wert)
         {
         struct knoten *hilf;
         hilf = (struct knoten *) calloc(1,sizeof(struct knoten));
         if (hilf == NULL)
                 return hilf;
         hilf -> links = NULL;
         hilf -> rechts = NULL;
         hilf -> wert = wert;
         hilf -> rang = 0;
         return hilf;
         }
 

delete_baum_000000(struct knoten **wurzel, int wert)
// rueckgabe 0 = ohne fehler
//           2 = wert war nicht drin
//           FEHLER sonst
        {
        return delete_baum_000000_co(NULL,wurzel,wert);
        }
 

static delete_baum_000000_co(
        struct knoten **papa,
        struct knoten **wurzel,
        int wert)
        {
        int res;
        struct knoten **neu;
        struct knoten **bruder;
        if (*wurzel == NULL) /* wert nicht gefunden  */ return 2;
 

        // suchen
        if ((*wurzel) ->wert == wert) // gefunden
                {
                struct knoten *zeiger;
                if (
                        (papa != NULL) &&
                        (((*wurzel) ->rechts) == NULL)  &&
                        (((*wurzel) ->links) == NULL) &&
                        (((*papa)->rang) == 1)
                   )
                // es wird ein schwarzes blatt geloescht
                // das gibt ein rang problem
                        {
                        free(*wurzel);
                        *wurzel = NULL;
                        return 1;
                        }
                else if (
                        (((*wurzel) ->rechts) == NULL)  &&
                        (((*wurzel) ->links) == NULL)
                   )
                   // es wird ein rotes blatt geloescht
                  // oder die alleinige wurzel
                        {
                        free(*wurzel);
                        *wurzel = NULL;
                        return 0; // fertig
                        }
                else if ( (((*wurzel) ->links) == NULL))
                        // vater eines blattes
                        {
                        zeiger = (*wurzel) ->rechts;
                        free(*wurzel);

                        *wurzel = zeiger;
                        return 0; // fertig
                        }
                 else if ( (((*wurzel) ->rechts) == NULL))
                        // vater eines blattes
                        {
                        zeiger = (*wurzel) ->links;
                        free(*wurzel);
                        *wurzel = zeiger;
                        return 0; // fertig
                        }
                // es muss der austausch wert gefunden werden
                zeiger = (*wurzel) ->rechts;
                while (zeiger != NULL)
                        {
                        wert = zeiger->wert;
                        zeiger = zeiger->links;
                        }
                (*wurzel) ->wert = wert; // der austausch;
                neu =  &  ((*wurzel) ->rechts);
                }
        else if ((*wurzel) ->wert > wert) {
                neu =  &  ((*wurzel) ->links);
                }
        else    {
                neu =  &  ((*wurzel) ->rechts);
                }
        res =  delete_baum_000000_co( wurzel, neu,wert);
 

#define RANG(a) (((*a) == NULL) ? -1 : ((*a)->rang))

        if (res == 2) return 2;
        if (res == 0) return 0;
        if (res == FEHLER) return FEHLER;

        if (wurzel == NULL) return 0; // leerer baum

// hier werden die rangstoerungen behoben
// zwischen neu und wurzel muss sie liegen

        if ((RANG(wurzel) - RANG(neu)) == 1) return 0;
        /* in der rekursion muss nicht weiter gemacht werden  */
        if ((RANG(wurzel) - RANG(neu)) !=  2)
                {
                return FEHLER; // sollte nicht sein
                }

// zuerst der fall dass sich die rangstoerung fortsetzt
// d.h. es gibt zu neu keinen roten bruder
// und der schwarze bruder hat keine roten nachfolger

// bruder zeiger
        bruder = ( neu ==  &((*wurzel)->links) ) ?  &((*wurzel)->rechts) : &((*wurzel)->links)  ;

// bruder kann nicht der nullzeiger sein
        if (bruder == NULL) {
                return FEHLER; // sollte nicht sein
                }

        if (RANG(bruder) < RANG(wurzel))
                if (RANG(bruder) >  RANG(& ((*bruder)->rechts)))
                if (RANG(bruder) >  RANG(& ((*bruder)->links)))
                        {(*wurzel)->rang --; return 1;}
// das war der einfache fall, dass sich die rangerniedrigung fortsetzt

// alle anderen faelle werden hier geloest und die delete routine mit return 0 beendet
 

#define BRUDERRECHTSROT() (( neu == &((*wurzel)->links) ) &&  (RANG(wurzel) == RANG(& ((*wurzel)->rechts))))
#define BRUDERLINKSROT() (( neu == &((*wurzel)->rechts) ) &&  (RANG(wurzel) == RANG(& ((*wurzel)->links))))
 

        if (BRUDERRECHTSROT()) { rot_links(wurzel);
                                papa = wurzel;
                                wurzel = & ((*wurzel)->links);
                                bruder =  & ((*wurzel)->rechts);
                                }
        else if (BRUDERLINKSROT()) { rot_rechts(wurzel);
                                papa = wurzel;
                                wurzel= & ((*wurzel)->rechts);
                                bruder =  & ((*wurzel)->links);
                                }

// die rangdifferenz besteht immer noch
// der (neue) bruder ist jetzt schwarz und kein blatt (wg rang)
        if (bruder == NULL) {
                return FEHLER; // sollte nicht sein
                }

#define OHNEROTEBRUEDER(a) ( (RANG(a) > RANG(& ((*a)->links) ))  && (RANG(a) > RANG(& ((*a)->rechts))))
#define ZWEIROTEBRUEDER(a) ( (RANG(a) == RANG(& ((*a)->links) ))  && (RANG(a) == RANG(& ((*a)->rechts))))
#define LINKERROTEBRUEDER(a) ( (RANG(a) == RANG(& ((*a)->links) )) )
#define RECHTERROTEBRUEDER(a) ( (RANG(a) == RANG(& ((*a)->rechts) )) )

        // printf("rangstoerung teil 2\n");
// jetzt nur noch faelle wo der bruder schwarz ist
// der rang der wurzel wird erniedrigt

        ((*wurzel) -> rang) --;
        if (neu == &((*wurzel)->links))
                {
                if (OHNEROTEBRUEDER(bruder))
                        {
                        return 0;
                        }
                if (ZWEIROTEBRUEDER(bruder))
                        {
                        rot_links(wurzel); // fertig
                         ((*wurzel) -> rang) ++;
                        return 0;
                        }
                if (LINKERROTEBRUEDER(bruder))
                        {
                        doppel_rot_rechtslinks(wurzel); // fertig
                         ((*wurzel) -> rang) ++;
                        return 0;
                        }
                if (RECHTERROTEBRUEDER(bruder))
                        {
                        rot_links(wurzel); // fertig
                         ((*wurzel) -> rang) ++;
                        return 0;
                        }
                }
        else    {
                if (OHNEROTEBRUEDER(bruder))
                        {
                        return 0;
                        }
                if (ZWEIROTEBRUEDER(bruder))
                        {
                        rot_rechts(wurzel); // fertig
                         ((*wurzel) -> rang) ++;
                        return 0;
                        }
                if (RECHTERROTEBRUEDER(bruder))
                        {
                        doppel_rot_linksrechts(wurzel); // fertig
                         ((*wurzel) -> rang) ++;
                        return 0;
                        }

                if (LINKERROTEBRUEDER(bruder))
                        {
                        rot_rechts(wurzel); // fertig
                         ((*wurzel) -> rang) ++;
                        return 0;
                        }
                }

        }
 

insert_baum_000000(struct knoten **wurzel, int wert)
// rueckgabe 0 = ohne fehler
//           2 = war schon drin
//           FEHLER sonst
        {
        return insert_baum_000000_co(NULL,NULL,wurzel,wert);
        }
 

static insert_baum_000000_co(
        struct knoten **opa,
        struct knoten **papa,
        struct knoten **wurzel,
        int wert)
         {
         int res;
         struct knoten **neu;
         if (*wurzel == NULL)
                 /* der baum ist noch leer */
                 {
                 *wurzel = new_knoten(wert);
                 if (*wurzel == NULL)
                         return FEHLER;
                 return 1;
                 }
 
 

         if ((*wurzel) ->wert == wert) return 2; // schon da;
         if ((*wurzel) ->wert > wert)
                neu =  &  ((*wurzel) ->links);
         else if ((*wurzel) ->wert < wert)
                neu =  &  ((*wurzel) ->rechts);

         res =  insert_baum_000000_co( papa, wurzel, neu,wert);

         if (res == 0) return 0; // keine rang korrektur mehr
         if (res == 2) return 2; // schon da
         if (res == FEHLER)  return FEHLER; // Fehler
         if (res == 1) // rang ueberpruefung
                {
                if (papa == NULL) return 0;
                if ((*papa)->rang != (*neu)->rang) return 1; // hier keine korrektur
                /* rotation rechts */
                        if (
                         RECHTERNACHFOLGERSCHWARZ(papa) && RECHTERNACHFOLGERSCHWARZ(wurzel)
                           )
                        return rot_rechts(papa);
                /* rotation  links */
                        if (
                         LINKERNACHFOLGERSCHWARZ(papa) && LINKERNACHFOLGERSCHWARZ(wurzel)
                           )
                        return rot_links(papa);
                /* doppel links rechts */
                        if (
                         RECHTERNACHFOLGERSCHWARZ(papa) && LINKERNACHFOLGERSCHWARZ(wurzel)
                           )
                        return doppel_rot_linksrechts(papa);
                /* doppel rechts links */
                        if (
                         LINKERNACHFOLGERSCHWARZ(papa) && RECHTERNACHFOLGERSCHWARZ(wurzel)
                           )
                        return doppel_rot_rechtslinks(papa);

                /* sonst rangerhoehung */
                (*papa)->rang ++;
                return 1;
                }
         // kann nicht sein
         }

print_baum_000000(struct knoten *wurzel)
        {
        print_baum_000000_co(wurzel,0);
        printf("\n");
        }
static print_baum_000000_co(struct knoten *wurzel,int level)
         {
         int i;
         if (wurzel != NULL)
                 {
                  print_baum_000000_co(wurzel->links,level+1);
                 for (i=0;i<3*level;i++) printf(" ");
                 printf("(%d:%d:%d \n",level,wurzel->rang,wurzel->wert);
                  print_baum_000000_co(wurzel->rechts,level+1);
                 }
         }

free_baum_000000(struct knoten *wurzel)
         {
         if (wurzel != NULL)
                 {
                  free_baum_000000(wurzel->links);
                  free_baum_000000(wurzel->rechts);
                  free(wurzel);
                 }
         }
 

rot_rechts(struct knoten **wurzel)
        {
        int wert;
        struct knoten * hilf;

        if (*wurzel == NULL) return FEHLER;
        wert =(*wurzel)->wert;
        hilf = *wurzel;
        *wurzel = (*wurzel)->links;
        hilf->links = (*wurzel)->rechts;
        (*wurzel)->rechts = hilf;
        return 0;
        }

rot_links(struct knoten **wurzel)
        {
        int wert;
        struct knoten * hilf;

        if (*wurzel == NULL) return FEHLER;
        wert =(*wurzel)->wert;
        hilf = *wurzel;
        *wurzel = (*wurzel)->rechts;
        hilf->rechts = (*wurzel)->links;
        (*wurzel)->links = hilf;
        return 0;
        }

doppel_rot_linksrechts(struct knoten **wurzel)
        {
        int wert;
        struct knoten * hilf;
        if (*wurzel == NULL) return FEHLER;
        wert =(*wurzel)->wert;
        if ( (*wurzel)->links == NULL) return FEHLER;
        hilf = (*wurzel)->links->rechts;
        (*wurzel)->links->rechts = hilf->links;
        hilf->links = (*wurzel)->links;
        (*wurzel)->links = hilf->rechts;
        hilf->rechts = (*wurzel);
        *wurzel = hilf;
        return 0;
        }

doppel_rot_rechtslinks(struct knoten **wurzel)
        {
        int wert;
        struct knoten * hilf;
        if (*wurzel == NULL) return FEHLER;
        wert =(*wurzel)->wert;
        if ( (*wurzel)->rechts == NULL) return FEHLER;
        hilf = (*wurzel)->rechts->links;
        (*wurzel)->rechts->links = hilf->rechts;
        hilf->rechts = (*wurzel)->rechts;
        (*wurzel)->rechts = hilf->links;
        hilf->links = (*wurzel);
        *wurzel = hilf;
        return 0;
        }
 
 

main()
{
        struct knoten *wurzel = NULL,*z;
        int i,wert;
        int n;

        scanf("%d",&n);

        for (i=0;i<n;i++)
                insert_baum_000000(&wurzel,rand()%n);
 

        print_baum_000000(wurzel);

        for (i=0;i<n;i++)
                {
 
                wert = i;
                printf("delete wert = %d\n",wert);
                delete_baum_000000(&wurzel,wert);
                }

        print_baum_000000(wurzel);

        free_baum_000000(wurzel);

}