Balance eines Baumes berechnen

[Beginner09]

Hallo,

wie berechnen sich die Balance-Werte dieses Baumes?

Quelle: wikipedia.de

Ich kann den allgemeinen Rechenregeln im Netz leider nicht folgen ;(

MfG

 

[javimka]

Soweit ich weiss, hat jeder Knoten eine -1, wenn der linke Teilbaum grösser als der rechte ist, 0, wenn beide Teilbäume gleich gross sind und +1, wenn der rechte Teilbaum grösser als der linke ist.

 

[Beginner09]

Die Balance -1 beim Wert 11 kommt zustande, da der rechte Teilbaum nur ein Blatt und kein - im Vgl. zum linken Teilbaum - Knoten ist?

Nach Deiner genannten Regel müsste 11 EIGENTLICH den Wert +1 haben, da 12 > 10.

MfG

 

[eRaaaa]

also ich versuchs mal zu erklären. denke am besten könnte man es anhand einer grafik zeigen, ich bin aber extrem schlecht, in sachen grafiken 😀

du schreibst am besten an jeden knoten erstmal die höhe. (such am besten den höhsten/längsten pfad bis zur wurzel, hier also von der 9 aufwärts)

das würde in deinem beispiel dann so aussehen:



nun musst du halt für jedne inneren knoten, die kinder betrachten. beispiel:
wurzel: (5) die kinder (3) und (8) haben höhe 3 und 4. (siehe grafik)=> 4-3 = 1 die kinder differenzieren also um 1, ist also ok!

nächstes beispiel, die (11)
die kinder (10) und (12) haben die höhe 2 und 1 = 1-2 = -1 auch ok !

usw.

hoffe das ist einigermaßen verständlich! wenn nicht frage nochmal, wie gesag,t finds so bisschen schwer zu erklären.

 

[javimka]

Nach Deiner genannten Regel müsste 11 EIGENTLICH den Wert +1 haben, da 12 > 10.

Es geht nicht um den Wert innerhalb des Knoten. Du hast ja einen Sortierbaum, da sind die Werte rechts (hoffentlich) immer grösser. Es geht um die Grösse/Länge/Tiefe oder wie auch immer der Teilbäume 😉

 

[eRaaaa]

Es geht nicht um den Wert innerhalb des Knoten.

richtig 😀

Es geht um die Grösse/Länge/Tiefe oder wie auch immer der Teilbäume 😉

höhe, daher auch höhenbalanciert 😀

es ist ja auch egal, ob ich nun das linke kind vom rechten abziehe oder rechte vom linken. also ob da nun -1 oder +1 steht, denk ich mal ist egal(bin mir aber nicht sicher obs dafür eine definition gibt), solange die differenz halt 1, bzw -1 ist, ist alles tutti 😀

 

[Beginner09]

...
wurzel: (5) die kinder (3) und (8) haben höhe 3 und 4. (siehe grafik)=> 4-3 = 1 die kinder differenzieren also um 1, ist also ok!
...

Hier endet mein Verständnis bereits. Kinder (3) und (8) sind welche in Deiner Zeichnung?

MfG

 

[eRaaaa]

Hier endet mein Verständnis bereits. Kinder (3) und (8) sind welche in Deiner Zeichnung?

MfG

na mein baum basiert auf deinem. die knoten sind also die selben, ich habe für die knoten jetzt nur die höhen dazugeschrieben. 3 und 8 sind also bei mir in der zeichnung, auch die kinder von der wurzel(höhen 3 und 4)

 

[Beginner09]

Ich fasse mir gerade vor Entsetzen an den Kopf, DANKE!

Weitere Frage:
Ich habe gelesen damit ein AVL-Baum besteht, ist ein - ich nenne es mal ausgeglichenes - Verhältnis der Äste vorliegt?!
Die Äste dürfen also immer nur eine maximale Differenz von +1 bzw. -1 oder aber 0 haben, oder?

MfG

 

[eRaaaa]

Ein Binärbaum heißt AVL-Baum, wenn sich für jeden seiner Teilbäume die Höhen des linken und rechten Astes höchstens um 1 unterscheiden.

Quelle: AVL-Baum ? Wikipedia

beantwortet dies deine frage? 😀

 

[Löffler]

Das is richtig. Sollte ein Baum aber mal nicht so aussehen(vll ein Knoten entfernt etc) kann man ihn aber wieder "richtig" umstellen über Rotation etc...
AVL-Baum ? Wikipedia

Unter dem Punkt Rebalancierung wird es erklärt wie es funktioniert

*da war einer schneller*

 

[Beginner09]

Quelle: AVL-Baum ? Wikipedia

beantwortet dies deine frage? 😀

Im Zusammenhang mit Deiner schicken Skizze und wikipedia konnte ich auch diese Lücke in meinem Kopfe soeben schließen. 🙂

Danke!

 

[Beginner09]

...
Unter dem Punkt Rebalancierung wird es erklärt wie es funktioniert
...

... und das wird mir NUN die Nerven rauben ;-)

 

[Löffler]

wenn du nen bisschen google'st dann sollten noch mehr Bsp rauskommen oder vll bessere Erklärungen als diese auf wikipedia, obwohl ich die persönlich ganz gut und verständlich finde

 

[eRaaaa]

... und das wird mir NUN die Nerven rauben ;-)

das kann es in der tat 🙂
für sowas fand ich persönlich immer ganz schick, sich animierte java applets oder dergleichen anzuschauen. da wird sowas immer ganz nett dargestellt.
(bei wiki findest du einige links)

 

[Beginner09]

Dankeschön für die Hilfe.

Sollte ich erneut welche benötigen, werdet Ihr von mir hören. 🙂

Schönen Abend noch.