AVL Baum - Balance ermitteln

nippler92

huhu,

ich hab nen Problem mit der Ermittlung der Balance in meinem AVL Baum
Bsp an der Zahlenfolge 3,9,6,8,10

3 - Balance 0

3 - Balance 1
9 - Balance 0

3 - Balance 2
9 - Balance-1
6 - Balance 0

jetz müsste ja rotiert werden...

Sooo, mein Problem ich weiß nicht wie ich wenn ich mit meiner Funktion anhängen die rückläufigen Knoten anlaufen kann um die Balance ändern zu können

KNOTEN* einordnen(KNOTEN *zeiger, int zahl)
    {

        if(zeiger == NULL)
        {
            zeiger = malloc(sizeof(KNOTEN));
            if(zeiger==NULL)
            {
                printf("Kein Speicherplatz gefunden");
                exit (EXIT_FAILURE);
            }
            zeiger->wert=zahl;
            zeiger->balance=0;
            zeiger->links=NULL;
            zeiger->rechts=NULL;

            return zeiger;
        }

        else if(zeiger->wert >= zahl)
        {
            zeiger->links=einordnen(zeiger->links, zahl);

            if(zeiger->rechts == NULL)
            {
                zeiger->balance = zeiger->balance - 1;
            }
            else if (zeiger->links == NULL)
            {
                zeiger->balance = zeiger->balance + 1;
            }
            else if (zeiger->links == NULL && zeiger->rechts == NULL)
            {
                zeiger->balance=0;
            }

            else if (zeiger->links != NULL && zeiger->rechts != NULL)
            {
                zeiger->balance = zeiger->rechts->balance - zeiger->links->balance;
            }

            printf("Balance %d\n",zeiger->balance);

            zeiger->links=balancieren(zeiger->links);  
        }

        else if(zeiger->wert < zahl)
        {
            zeiger->rechts=einordnen(zeiger->rechts, zahl);

            if(zeiger->rechts == NULL)
            {
                zeiger->balance = -1;
            }
            else if (zeiger->links == NULL)
            {
                zeiger->balance = 1;
            }
            else if (zeiger->links != NULL && zeiger->rechts != NULL)
            {
                zeiger->balance = zeiger->rechts->balance - zeiger->links->balance;
            }
            printf("Balance %d\n",zeiger->balance);

            zeiger->rechts=balancieren(zeiger->rechts);
        }
    }

Mit dem Code kann ich halt nur während ich einfüge die Balance meines Vorgängers bearbeiten.

ich könnte nen zeiger auf meinen elternknoten in die struktur einfügen aber -> uncool, weil ich glaube das es Speicherverschwendung ist und es auch schöner geht, nur hab ich bei mir grad selber ein paar Knoten im Kopf.

Hilfe!

mfg nippler92

Wutz

Bei Bäumen ist es immer sinnvoll, mit root zu arbeiten, d.h. immer und überall root bzw. einen root-Zeiger als Parameter an die einzelnen Funktionen zu übergeben.
Ein innerhalb einer Baum-Funktion weggekapseltes malloc für nodes oder gar root ist immer schlecht, wartungsaufwändig und unübersichtlich.

SeppJ

Also ich würde ja sagen, dass ein parent-Zeiger in Ordnung geht. Aber wenn du es nicht so möchtest, dann musst du dir beim Runtergehen eben die ganzen Eltern merken, sprich: Sie auf einen Stack legen. Entweder indem du tatsächlich einen Stack programmierst oder (vermutlich sehr viel eleganter) indem du Rekursion benutzt. Für Beispiele kannst du hier gucken:
Google: avl tree without parent pointer

nippler92

na wenn ichs mit nem parent pointer mache und dann sozusagen nach jedem einfügen meinen ganzen baum zum eltern knoten des neu eingefügten elements durchlaufen muss wirds ja recht langsam oder?

ICh habs halt mit rekursion versuct, jeweils die erste zeile nach dem else if, klappt halt nur noch nicht

SeppJ

nippler92 schrieb:

na wenn ichs mit nem parent pointer mache und dann sozusagen nach jedem einfügen meinen ganzen baum zum eltern knoten des neu eingefügten elements durchlaufen muss wirds ja recht langsam oder?

Wieso solltest du das müssen?

ICh habs halt mit rekursion versuct, jeweils die erste zeile nach dem else if, klappt halt nur noch nicht

Tja. Vielleicht hilft dir ja der erste oder der dritte Link in meiner Signatur weiter.