home *** CD-ROM | disk | FTP | other *** search
/* * Quelltext zum ATOS-Artikel "Dynamische Datenstrukturen" * ATOS 3/96, 5/96, 1/97 * * Quelltext für einen (binären) AVL-Baum am Beispiel einer CD-Verwaltung. * * Autor: Hauke Wessels */ #include <stdio.h> #include <string.h> #include <stdlib.h> #include "AVLBAUM.H" /***************************************************************** * aus Modula-2 übersetzt */ void tausche(Knoten **z1, Knoten **z2, Knoten **z3) { Knoten *hilf; hilf = *z1; *z1=*z2; *z2=*z3; *z3=hilf; } void rot_rechts(Knoten **z) { tausche(z, &((*z)->links), &((*z)->links->rechts)); } void rot_links(Knoten **z) { tausche(z, &((*z)->rechts), &((*z)->rechts->links)); } void set_balanc(int neu_links, int neu_rechts, Knoten *knoten) { knoten->links->avl = neu_links; knoten->rechts->avl = neu_rechts; } void korr_balanc(Knoten *knoten) { switch(knoten->avl) { case 1: /* Rechtslastig */ { set_balanc(-1, 0, knoten); break; } case -1: /* Linkslastig */ { set_balanc(0, 1, knoten); break; } case 0: /* neutral */ { set_balanc(0, 0, knoten); break; } } } void hoeher_links(Knoten **knoten, int *hoeher) { switch((*knoten)->avl) /* AVL-Wert des aktuellen Knotens untersuchen */ { case -1: /* Linkslastig */ { if ((*knoten)->links->avl == -1) /* linkes Kind auch Linkslastig? */ { rot_rechts(knoten); /* Dann um diesen Knoten im Uhrzeigersinn drehen */ (*knoten)->rechts->avl = 0; /* Danach muß alter Knoten AVL-Wert 0 haben */ } else /* linkes Kind nicht auch Linkslastig */ { rot_links(&((*knoten)->links)); rot_rechts(knoten); korr_balanc(*knoten); } (*knoten)->avl = 0; *hoeher = FALSE; /* Nach dem Ausgleich ist AVL-Wert = 0, keine Seite ist höher */ break; } case 1: /* Rechtslastig */ { (*knoten)->avl = 0; *hoeher = FALSE; break; } case 0: /* neutral */ { (*knoten)->avl = -1; break; } } } void hoeher_rechts(Knoten **knoten, int *hoeher) { switch((*knoten)->avl) { case 1: /* Rechtslastig */ { if ((*knoten)->rechts->avl == 1) { rot_links(knoten); (*knoten)->links->avl = 0; } else { rot_rechts(&((*knoten)->rechts)); rot_links(knoten); korr_balanc(*knoten); } (*knoten)->avl = 0; *hoeher = FALSE; break; } case -1: /* Linkslastig */ { (*knoten)->avl = 0; *hoeher = FALSE; break; } case 0: /* neutral */ { (*knoten)->avl = 1; /* rechtsl. */ break; } } } /************************************************************************ * Variablen: * - wurzel: Zeiger auf den Zeiger der Wurzel des Baumes * - eintrag: Der Eintrag, der eingefügt werden soll * - hoeher: gibt an, ob der Baum beim Einfügen höher geworden ist, oder nicht */ int einfuegen(Knoten **wurzel, Knoten *eintrag, int *hoeher) { int rc, erg; if (*wurzel == NULL) /* am richtigen Platz für den Eintrag angekommen? */ { *wurzel = eintrag; /* einfügen */ eintrag->links = NULL; /* zur Sicherheit ... */ eintrag->rechts = NULL; /* ... markieren */ eintrag->avl = 0; /* ein Blatt ist immer ausgeglichen */ *hoeher = TRUE; /* und oben mitteilen, daß dieser Zweig jetzt um einen höher ist */ return(TRUE); /* wurde eingefügt */ } else /* wir suchen noch nach dem Platz */ { erg = strcmp((*wurzel)->gruppe, eintrag->gruppe); /* Strings vergleichen */ if (erg == 0) /* Eintrag schon vorhanden? */ { *hoeher = FALSE; /* nichts eingetragen, dadurch nicht höher */ return(FALSE); /* 'nicht eingetragen' zurückgeben */ } else /* kein Dupe */ { if (erg < 0) /* String ist kleiner */ { rc = einfuegen(&(*wurzel)->links, eintrag, hoeher); /* Den eintrag in den linken Teilbaum einfügen */ if (*hoeher) /* Hat sich die Höhe des Teilbaums verändert? */ hoeher_links(wurzel, hoeher); /* dann evtl. ausgleichen, je nach Stand */ } else /* String ist größer als akt. Knoten? */ { rc = einfuegen(&(*wurzel)->rechts, eintrag, hoeher); /* Den eintrag in den rechten Teilbaum einfügen */ if (*hoeher) /* Hat sich die Höhe des Teilbaums verändert? */ hoeher_rechts(wurzel, hoeher); /* dann evtl. ausgleichen, je nach Stand */ } return(rc); /* Wert aus Rekursion übernehmen */ } } } int niedriger_links(Knoten **knoten, int *niedriger) /* gleicht knoten aus, wenn linker Teilbaum um 1 niedriger geworden ist */ { switch((*knoten)->avl) /* Balance-Faktor unterscheiden */ { case -1: /* linkslastig */ (*knoten)->avl = 0; /* jetzt ausgeglichen */ break; /* niedriger bleibt TRUE!! */ case 0: /* gleichtief */ (*knoten)->avl = +1; /* jetzt rechtslastig */ niedriger = FALSE; /* oben ändert sich nichts mehr */ break; case 1: /* rechtslastig */ switch((*knoten)->rechts->avl) /* Balance-Faktor des *rechten* Nachfolgers untersuchen */ { case -1: /* linkslastig */ rot_rechts(&(*knoten)->rechts); /* dann rechtslastig machen */ rot_links(knoten); /* linksrotation */ korr_balanc(*knoten); /* und die AVL-Werte setzen */ (*knoten)->avl = 0; /* selbst ist er ausgeglichen */ break; /* niedriger bleibt TRUE! oben muß weiter ausgeglichen werden */ case 0: /* ausgeglichen */ rot_links(knoten); /* linksrotation */ (*knoten)->avl = -1; /* oben ist es jetzt linkslastig */ *niedriger = FALSE; /* Höhe des Baums ändert sich nicht */ break; case 1: /* rechtslastig */ rot_links(knoten); /* um den Knoten einfach links rotieren */ (*knoten)->avl = 0; /* nun ausgeglichen */ (*knoten)->links->avl = 0; /* links ist ausgeglichen (mit neuem rechtem Teilbaum) */ break; /* Höhe hat sich geändert, deswegen bleibt niedriger = TRUE! */ } } return(TRUE); } int niedriger_rechts(Knoten **knoten, int *niedriger) /* gleicht knoten aus, wenn rechter Teilbaum um 1 niedriger geworden ist */ { switch((*knoten)->avl) /* Balance-Faktor unterscheiden */ { case 1: /* rechtslastig */ (*knoten)->avl = 0; /* jetzt ausgeglichen */ break; /* niedriger bleibt TRUE!! */ case 0: /* gleichtief */ (*knoten)->avl = +1; /* jetzt rechtslastig */ niedriger = FALSE; /* oben ändert sich nichts mehr */ break; case -1: /* linkslastig */ switch((*knoten)->links->avl) /* Balance-Faktor des *linken* Nachfolgers untersuchen */ { case 1: /* rechtslastig */ rot_links(&(*knoten)->rechts); /* dann linkslastig machen */ rot_rechts(knoten); /* rechtsrotation */ korr_balanc(*knoten); /* und die AVL-Werte setzen */ (*knoten)->avl = 0; /* selbst ist er ausgeglichen */ break; /* niedriger bleibt TRUE! oben muß weiter ausgeglichen werden */ case 0: /* ausgeglichen */ rot_rechts(knoten); /* rechtsrotation */ (*knoten)->avl = +1; /* oben ist es jetzt linkslastig */ *niedriger = FALSE; /* Höhe des Baums ändert sich nicht */ break; case -1: /* linkslastig */ rot_rechts(knoten); /* um den Knoten einfach rechts rotieren */ (*knoten)->avl = 0; /* nun ausgeglichen */ (*knoten)->rechts->avl = 0; /* rechts ist ausgeglichen (mit neuem rechtem Teilbaum) */ break; /* Höhe hat sich geändert, deswegen bleibt niedriger = TRUE! */ } } return(TRUE); } void ersatz_finden(Knoten **knoten, Knoten **zu_loeschen, int *niedriger) /* sucht den In-Order-Vorgänger und setzt ihn an die Stelle von *zu_loeschen */ { Knoten *hilf; hilf = *knoten; if (hilf->rechts != NULL) /* rechter Sohn ist vorhanden? */ { ersatz_finden(&hilf->rechts, zu_loeschen, niedriger); /* vom linken Sohn das rechteste Blatt suchen (rek.) */ if (*niedriger) /* Ist der Baum nun niedriger? */ niedriger_rechts(knoten, niedriger); /* rechts ist es niedriger geworden. Ausgleichen? */ } else { knoten = &hilf->links; /* linken Teilbaum des alten Kindes ersetzen */ hilf->links = (*zu_loeschen)->links; /* linken Teilbaum an Ersatz hängen */ hilf->rechts = (*zu_loeschen)->rechts; /* rechten Teilbaum an Ersatz hängen */ zu_loeschen = &hilf; /* Generationswechsel. das alte Kind wird nun Vater */ *niedriger = TRUE; } } /* 1. Ersatz finden und an Stelle übergeben 2. ersetztes Element löschen 3. Baum ausgleichen ab alter Ersatz-Stelle */ int loeschen(Knoten **wurzel, Knoten *eintrag, int *niedriger) { int rc, erg; Knoten *hilf; if (*wurzel == NULL) /* Eintrag nicht gefunden? */ { *niedriger = FALSE; /* nix geändert */ return(FALSE); } else /* wir suchen noch nach dem Platz */ { erg = strcmp((*wurzel)->gruppe, eintrag->gruppe); /* Strings vergleichen */ if (erg == 0) /* Eintrag gefunden? */ { hilf = *wurzel; /* Hilfszeiger setzen */ ersatz_finden(&hilf->links, wurzel, niedriger); /* Den Vorgänger suchen und an diese Stelle setzen */ free(hilf); /* und den Speicherplatz frei geben */ if (*niedriger) niedriger_links(wurzel, niedriger); /* links ist niedriger geworden */ return(TRUE); } else /* kein Dupe */ { if (erg < 0) /* String ist kleiner */ { rc = loeschen(&(*wurzel)->links, eintrag, niedriger); /* Den eintrag in den linken Teilbaum einfügen */ if (*niedriger) /* Hat sich die Höhe des Teilbaums verändert? */ niedriger_links(wurzel, niedriger); /* dann evtl. ausgleichen, je nach Stand */ } else /* String ist größer als akt. Knoten? */ { rc = loeschen(&(*wurzel)->rechts, eintrag, niedriger); /* Den eintrag in den rechten Teilbaum einfügen */ if (*niedriger) /* Hat sich die Höhe des Teilbaums verändert? */ niedriger_rechts(wurzel, niedriger); /* dann evtl. ausgleichen, je nach Stand */ } return(rc); /* Wert aus Rekursion übernehmen */ } } } 
