# Balance eines Baumes berechnen



## Beginner09 (2. Dez 2009)

Hallo,

wie berechnen sich die Balance-Werte dieses Baumes?






_Quelle: wikipedia.de_

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

MfG


----------



## javimka (2. Dez 2009)

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 (2. Dez 2009)

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 (2. Dez 2009)

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 (2. Dez 2009)

Beginner09 hat gesagt.:


> 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 (2. Dez 2009)

javimka hat gesagt.:


> 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 (2. Dez 2009)

eRaaaa hat gesagt.:


> ...
> 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 (2. Dez 2009)

Beginner09 hat gesagt.:


> 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 (2. Dez 2009)

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 (2. Dez 2009)

> 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 (2. Dez 2009)

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 (2. Dez 2009)

eRaaaa hat gesagt.:


> _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 (2. Dez 2009)

Löffler hat gesagt.:


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



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


----------



## Löffler (2. Dez 2009)

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 (2. Dez 2009)

Beginner09 hat gesagt.:


> ... 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 (2. Dez 2009)

Dankeschön für die Hilfe.

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

Schönen Abend noch.


----------

