Prof. Dr. R. Laue SS00 Informatik II
Übungsblatt 7

Lösung Aufgabe 15 (8 Programmierpunkte - Abgabe per email)

#define FEHLER 1000
#include <stdio.h>
struct knoten {
         struct knoten *links;
         struct knoten *rechts;
         int wert;
         int 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;
         }

insert_baum_000000(struct knoten **wurzel, int wert)
        {
        return insert_baum_000000_co(NULL,NULL,wurzel,wert);
        }

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;
                 }
#define RECHTERNACHFOLGERSCHWARZ(a) \
                ( ((*a) -> rechts == NULL) || \
                  ((*a)->rechts->rang < ((*a)->rang)) )
#define LINKERNACHFOLGERSCHWARZ(a) \
                ( ((*a) -> links == NULL) || \
                  ((*a)->links->rang < ((*a)->rang)) )

         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)
        {
        return print_baum_000000_co(wurzel,0);
        }
print_baum_000000_co(struct knoten *wurzel,int level)
         {
         if (wurzel != NULL)
                 {
                  print_baum_000000_co(wurzel->links,level+1);
                 printf(" level=%d:rang=%d:wert=%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)
{
struct knoten * hilf;

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

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

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

doppel_rot_linksrechts(struct knoten **wurzel)
        {
        struct knoten * hilf;
        if (*wurzel == NULL) return FEHLER;
        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)
        {
        struct knoten * hilf;
        if (*wurzel == NULL) return FEHLER;
        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;
int i;

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

print_baum_000000(wurzel);
free_baum_000000(wurzel);

}