home *** CD-ROM | disk | FTP | other *** search
/ TCE Demo 2 / TCE_DEMO_CD2.iso / demo_cd_.2 / mags / atos / atos971f.arj / atos971f / SOURCEN / AVLBAUM.C next >
C/C++ Source or Header  |  1997-02-01  |  11KB  |  321 lines
  1. /*
  2.  * Quelltext zum ATOS-Artikel "Dynamische Datenstrukturen"
  3.  * ATOS 3/96, 5/96, 1/97
  4.  *
  5.  * Quelltext für einen (binären) AVL-Baum am Beispiel einer CD-Verwaltung.
  6.  *
  7.  * Autor: Hauke Wessels
  8.  */
  9.  
  10. #include <stdio.h>
  11. #include <string.h>
  12. #include <stdlib.h>
  13.  
  14. #include "AVLBAUM.H"
  15.  
  16.  
  17. /*****************************************************************
  18.  * aus Modula-2 übersetzt
  19.  */
  20. void tausche(Knoten **z1, Knoten **z2, Knoten **z3)
  21. {
  22.     Knoten *hilf;
  23.     
  24.     hilf = *z1;
  25.     *z1=*z2;
  26.     *z2=*z3;
  27.     *z3=hilf;
  28. }
  29.  
  30. void rot_rechts(Knoten **z)
  31. {
  32.     tausche(z, &((*z)->links), &((*z)->links->rechts));
  33. }
  34.  
  35. void rot_links(Knoten **z)
  36. {
  37.     tausche(z, &((*z)->rechts), &((*z)->rechts->links));
  38. }
  39.  
  40. void set_balanc(int neu_links, int neu_rechts, Knoten *knoten)
  41. {
  42.     knoten->links->avl = neu_links;
  43.     knoten->rechts->avl = neu_rechts;
  44. }
  45.  
  46. void korr_balanc(Knoten *knoten)
  47. {
  48.     switch(knoten->avl)
  49.     {
  50.         case 1:       /* Rechtslastig */
  51.         {
  52.             set_balanc(-1, 0, knoten);
  53.             break;
  54.         }
  55.         case -1:     /* Linkslastig */
  56.         {
  57.             set_balanc(0, 1, knoten);
  58.             break;
  59.         }
  60.         case 0:     /* neutral */
  61.         {
  62.             set_balanc(0, 0, knoten);
  63.             break;
  64.         }
  65.     }
  66. }
  67.  
  68. void hoeher_links(Knoten **knoten, int *hoeher)
  69. {
  70.     switch((*knoten)->avl)                            /* AVL-Wert des aktuellen Knotens untersuchen */
  71.     {
  72.         case -1:                                      /* Linkslastig */
  73.         {
  74.             if ((*knoten)->links->avl == -1)           /* linkes Kind auch Linkslastig? */
  75.             {
  76.                 rot_rechts(knoten);                   /* Dann um diesen Knoten im Uhrzeigersinn drehen */
  77.                 (*knoten)->rechts->avl = 0;            /* Danach muß alter Knoten AVL-Wert 0 haben */
  78.             }
  79.             else                                       /* linkes Kind nicht auch Linkslastig */
  80.             {
  81.                 rot_links(&((*knoten)->links)); 
  82.                 rot_rechts(knoten);
  83.                 korr_balanc(*knoten);
  84.             }
  85.             (*knoten)->avl = 0; *hoeher = FALSE;      /* Nach dem Ausgleich ist AVL-Wert = 0, keine Seite ist höher */
  86.             break;
  87.         }
  88.         case 1:    /* Rechtslastig */
  89.         {
  90.             (*knoten)->avl = 0; *hoeher = FALSE;
  91.             break;
  92.         }
  93.         case 0:    /* neutral */
  94.         {
  95.             (*knoten)->avl = -1;
  96.             break;
  97.         }
  98.     }
  99. }
  100.  
  101. void hoeher_rechts(Knoten **knoten, int *hoeher)
  102. {
  103.     switch((*knoten)->avl)
  104.     {
  105.         case 1:    /* Rechtslastig */
  106.         {
  107.             if ((*knoten)->rechts->avl == 1)
  108.             {
  109.                 rot_links(knoten);
  110.                 (*knoten)->links->avl = 0;
  111.             }
  112.             else
  113.             {
  114.                 rot_rechts(&((*knoten)->rechts));
  115.                 rot_links(knoten);
  116.                 korr_balanc(*knoten);
  117.             }
  118.             (*knoten)->avl = 0; *hoeher = FALSE;
  119.             break;
  120.         }
  121.         case -1:    /* Linkslastig */
  122.         {
  123.             (*knoten)->avl = 0; *hoeher = FALSE;
  124.             break;
  125.         }
  126.         case 0:    /* neutral */
  127.         {
  128.             (*knoten)->avl = 1;  /* rechtsl. */
  129.             break;
  130.         }
  131.     }
  132. }
  133.  
  134. /************************************************************************
  135.  * Variablen: 
  136.  *      - wurzel: Zeiger auf den Zeiger der Wurzel des Baumes
  137.  *      - eintrag: Der Eintrag, der eingefügt werden soll
  138.  *      - hoeher: gibt an, ob der Baum beim Einfügen höher geworden ist, oder nicht
  139.  */
  140. int einfuegen(Knoten **wurzel, Knoten *eintrag, int *hoeher)
  141. {
  142.     int rc, erg;
  143.     if (*wurzel == NULL)                                                /* am richtigen Platz für den Eintrag angekommen? */
  144.     {
  145.         *wurzel = eintrag;                                                /* einfügen */
  146.         eintrag->links = NULL;                                            /* zur Sicherheit ... */
  147.         eintrag->rechts = NULL;                                            /* ... markieren      */
  148.         eintrag->avl = 0;                                                /* ein Blatt ist immer ausgeglichen */
  149.         *hoeher = TRUE;                                                    /* und oben mitteilen, daß dieser Zweig jetzt um einen höher ist */
  150.         return(TRUE);                                                    /* wurde eingefügt */
  151.     }
  152.     else                                                                /* wir suchen noch nach dem Platz */
  153.     {
  154.         erg = strcmp((*wurzel)->gruppe, eintrag->gruppe);                /* Strings vergleichen */
  155.         if (erg == 0)                                                    /* Eintrag schon vorhanden? */
  156.         {
  157.             *hoeher = FALSE;                                            /* nichts eingetragen, dadurch nicht höher */
  158.             return(FALSE);                                                /* 'nicht eingetragen' zurückgeben */
  159.         }
  160.         else                                                            /* kein Dupe */
  161.         {
  162.             if (erg < 0)                                                /* String ist kleiner */
  163.             {
  164.                 rc = einfuegen(&(*wurzel)->links, eintrag, hoeher);        /* Den eintrag in den linken Teilbaum einfügen */
  165.                 if (*hoeher)                                            /* Hat sich die Höhe des Teilbaums verändert? */
  166.                     hoeher_links(wurzel, hoeher);                        /* dann evtl. ausgleichen, je nach Stand */
  167.             }
  168.             else                                                        /* String ist größer als akt. Knoten? */
  169.             {
  170.                 rc = einfuegen(&(*wurzel)->rechts, eintrag, hoeher);    /* Den eintrag in den rechten Teilbaum einfügen */
  171.                 if (*hoeher)                                            /* Hat sich die Höhe des Teilbaums verändert? */
  172.                     hoeher_rechts(wurzel, hoeher);                        /* dann evtl. ausgleichen, je nach Stand */
  173.             }
  174.             return(rc);                                                    /* Wert aus Rekursion übernehmen */
  175.         }
  176.     }    
  177. }
  178.                 
  179. int niedriger_links(Knoten **knoten, int *niedriger)                    /* gleicht knoten aus, wenn linker Teilbaum um 1 niedriger geworden ist */
  180. {
  181.     switch((*knoten)->avl)                                                /* Balance-Faktor unterscheiden */
  182.     {
  183.         case -1:                                                        /* linkslastig */
  184.             (*knoten)->avl = 0;                                            /* jetzt ausgeglichen */
  185.             break;                                                        /* niedriger bleibt TRUE!! */
  186.         case 0:                                                            /* gleichtief */
  187.             (*knoten)->avl = +1;                                        /* jetzt rechtslastig */
  188.             niedriger = FALSE;                                            /* oben ändert sich nichts mehr */
  189.             break;
  190.         case 1:                                                            /* rechtslastig */
  191.             switch((*knoten)->rechts->avl)                                /* Balance-Faktor des *rechten* Nachfolgers untersuchen */
  192.             {
  193.                 case -1:                                                /* linkslastig */
  194.                     rot_rechts(&(*knoten)->rechts);                        /* dann rechtslastig machen */
  195.                     rot_links(knoten);                                    /* linksrotation */
  196.                     korr_balanc(*knoten);                                /* und die AVL-Werte setzen */
  197.                     (*knoten)->avl = 0;                                    /* selbst ist er ausgeglichen */
  198.                     break;                                                /* niedriger bleibt TRUE! oben muß weiter ausgeglichen werden */
  199.                 case 0:                                                    /* ausgeglichen */
  200.                     rot_links(knoten);                                    /* linksrotation */
  201.                     (*knoten)->avl = -1;                                /* oben ist es jetzt linkslastig */
  202.                     *niedriger = FALSE;                                    /* Höhe des Baums ändert sich nicht */
  203.                     break;
  204.                 case 1:                                                    /* rechtslastig */
  205.                     rot_links(knoten);                                    /* um den Knoten einfach links rotieren */
  206.                     (*knoten)->avl = 0;                                    /* nun ausgeglichen */
  207.                     (*knoten)->links->avl = 0;                            /* links ist ausgeglichen (mit neuem rechtem Teilbaum) */
  208.                     break;                                                /* Höhe hat sich geändert, deswegen bleibt niedriger = TRUE! */
  209.             }
  210.     }
  211.     return(TRUE);
  212. }
  213.  
  214. int niedriger_rechts(Knoten **knoten, int *niedriger)                    /* gleicht knoten aus, wenn rechter Teilbaum um 1 niedriger geworden ist */
  215. {
  216.     switch((*knoten)->avl)                                                /* Balance-Faktor unterscheiden */
  217.     {
  218.         case 1:                                                            /* rechtslastig */
  219.             (*knoten)->avl = 0;                                            /* jetzt ausgeglichen */
  220.             break;                                                        /* niedriger bleibt TRUE!! */
  221.         case 0:                                                            /* gleichtief */
  222.             (*knoten)->avl = +1;                                        /* jetzt rechtslastig */
  223.             niedriger = FALSE;                                            /* oben ändert sich nichts mehr */
  224.             break;
  225.         case -1:                                                        /* linkslastig */
  226.             switch((*knoten)->links->avl)                                /* Balance-Faktor des *linken* Nachfolgers untersuchen */
  227.             {
  228.                 case 1:                                                    /* rechtslastig */
  229.                     rot_links(&(*knoten)->rechts);                        /* dann linkslastig machen */
  230.                     rot_rechts(knoten);                                    /* rechtsrotation */
  231.                     korr_balanc(*knoten);                                /* und die AVL-Werte setzen */
  232.                     (*knoten)->avl = 0;                                    /* selbst ist er ausgeglichen */
  233.                     break;                                                /* niedriger bleibt TRUE! oben muß weiter ausgeglichen werden */
  234.                 case 0:                                                    /* ausgeglichen */
  235.                     rot_rechts(knoten);                                    /* rechtsrotation */
  236.                     (*knoten)->avl = +1;                                /* oben ist es jetzt linkslastig */
  237.                     *niedriger = FALSE;                                    /* Höhe des Baums ändert sich nicht */
  238.                     break;
  239.                 case -1:                                                /* linkslastig */
  240.                     rot_rechts(knoten);                                    /* um den Knoten einfach rechts rotieren */
  241.                     (*knoten)->avl = 0;                                    /* nun ausgeglichen */
  242.                     (*knoten)->rechts->avl = 0;                            /* rechts ist ausgeglichen (mit neuem rechtem Teilbaum) */
  243.                     break;                                                /* Höhe hat sich geändert, deswegen bleibt niedriger = TRUE! */
  244.             }
  245.     }
  246.     return(TRUE);
  247. }
  248.  
  249. 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 */
  250. {
  251.     Knoten *hilf;
  252.     
  253.     hilf = *knoten;
  254.     
  255.     if (hilf->rechts != NULL)                                        /* rechter Sohn ist vorhanden? */
  256.     {
  257.         ersatz_finden(&hilf->rechts, zu_loeschen, niedriger);        /* vom linken Sohn das rechteste Blatt suchen (rek.) */
  258.         if (*niedriger)                                                /* Ist der Baum nun niedriger? */
  259.             niedriger_rechts(knoten, niedriger);                    /* rechts ist es niedriger geworden. Ausgleichen? */
  260.     }
  261.     else
  262.     {
  263.         knoten = &hilf->links;                            /* linken Teilbaum des alten Kindes ersetzen */
  264.         hilf->links = (*zu_loeschen)->links;            /* linken Teilbaum an Ersatz hängen */
  265.         hilf->rechts = (*zu_loeschen)->rechts;            /* rechten Teilbaum an Ersatz hängen */
  266.         zu_loeschen = &hilf;                            /* Generationswechsel. das alte Kind wird nun Vater */
  267.         *niedriger = TRUE; 
  268.     }
  269. }
  270.  
  271. /*
  272. 1. Ersatz finden und an Stelle übergeben
  273. 2. ersetztes Element löschen
  274. 3. Baum ausgleichen ab alter Ersatz-Stelle
  275. */
  276.  
  277. int loeschen(Knoten **wurzel, Knoten *eintrag, int *niedriger)
  278. {
  279.     int rc, erg;
  280.     Knoten *hilf;
  281.     
  282.     if (*wurzel == NULL)                                                /* Eintrag nicht gefunden? */
  283.     {
  284.         *niedriger = FALSE;                                                /* nix geändert */
  285.         return(FALSE);
  286.     }
  287.     else                                                                /* wir suchen noch nach dem Platz */
  288.     {
  289.         erg = strcmp((*wurzel)->gruppe, eintrag->gruppe);                /* Strings vergleichen */
  290.         if (erg == 0)                                                    /* Eintrag gefunden? */
  291.         {
  292.             hilf = *wurzel;                                                /* Hilfszeiger setzen */
  293.             ersatz_finden(&hilf->links, wurzel, niedriger);                /* Den Vorgänger suchen und an diese Stelle setzen */
  294.             free(hilf);                                                    /* und den Speicherplatz frei geben */
  295.             if (*niedriger)
  296.                 niedriger_links(wurzel, niedriger);                        /* links ist niedriger geworden */
  297.             return(TRUE);
  298.         }
  299.         else                                                            /* kein Dupe */
  300.         {
  301.             if (erg < 0)                                                /* String ist kleiner */
  302.             {
  303.                 rc = loeschen(&(*wurzel)->links, eintrag, niedriger);    /* Den eintrag in den linken Teilbaum einfügen */
  304.                 if (*niedriger)                                            /* Hat sich die Höhe des Teilbaums verändert? */
  305.                     niedriger_links(wurzel, niedriger);                    /* dann evtl. ausgleichen, je nach Stand */
  306.             }
  307.             else                                                        /* String ist größer als akt. Knoten? */
  308.             {
  309.                 rc = loeschen(&(*wurzel)->rechts, eintrag, niedriger);    /* Den eintrag in den rechten Teilbaum einfügen */
  310.                 if (*niedriger)                                            /* Hat sich die Höhe des Teilbaums verändert? */
  311.                     niedriger_rechts(wurzel, niedriger);                /* dann evtl. ausgleichen, je nach Stand */
  312.             }
  313.             return(rc);                                                    /* Wert aus Rekursion übernehmen */
  314.         }
  315.     }    
  316. }
  317.  
  318.  
  319.  
  320.  
  321.