Ist dieser binäre Baum balanciert?

[ContainerDriver]

Servus,
ich habe einen binären Baum programmiert (also die Funktionen dazu, um einen zu erstellen). Um zu vermeiden das er zu einer
verketten Liste mutiert, habe ich auch versucht, eine Balancier-Funktion zu entwerfen. Diese liefert mir jetzt solch einen Baum ab (er ist auf die Seite gekippt):



| /--->[0|0]1687308769
/--->[0|1]1589022649
\--->[3|2]1321006333
| | /--->[0|0]1245537338
| /--->[1|1]1225910244
| | \--->[0|0]1156720263
\--->[2|2]997643399
| | /--->[0|0]453300481
| \--->[1|0]380043984


. / & \ gibt an, ob das folgende Element rechts oder links angeordnet ist. Die Zahlen in den [] bedeuten [linke_folger|rechte_folger].
Jetzt gab es da ja irgend so eine Regel, die über einen balancierten Binär-Baum sagt, dass sich die Tiefe der Blätter maximal um eins unterscheiden darf (dann ist erbalanciert).
Im Grunde ist das ja eigentlich bei dem oberen Baum der Fall. Dennoch enthält die linke Seite viel mehr Elemente als die rechte (6/2).
Deshalb meine Frage: ist dieser Baum wirklich balanciert?

Gruß, Florian



Ein vollständiger balancierter Binärbaum ist ein vollständiger Binärbaum, bei dem die Abstände zweier beliebiger Blätter von der Wurzel um höchstens 1 voneinander abweichen.

Hmm, ist die Frage, ob /--->[0|1]1589022649 noch ein Blatt ist...

[Boron]

/--->[0|1]1589022649 ist definitiv kein Blatt, da es ja selbst noch ein "Element" unter sich hat.

Und die Wikipedia Definition trifft dann auf den Baum zu.

[ContainerDriver]

Danke schon mal für die Antwort. Ich habe mich jetzt ein bisschen informiert:
der Baum oben ist ein AVL-Baum (kein vollständig ausbalancierter). Die Regel die ich meinte ist für die AVL-Bäume.
Soweit so gut. Leider hat mein Algo noch Fehler, denn manchmal wird die AVL-Regel verletzt. Schade.

Gruß, Florian

[ContainerDriver]

Ich hab jetzt echt ein Problem. Nach meinem Verständnis für die AVL-Regel dürfte dieser Baum kein AVL-Baum sein:


| | | /--->[0|0]83
| | /--->[1|1]82
| | | \--->[0|0]81
| /--->[2|2]80
| | | /--->[0|0]79
| | \--->[0|1]18
/--->[2|3]15
| | /--->[0|0]12
| \--->[0|1]7
\--->[3|4]6
| /--->[0|0]5
\--->[2|1]3
| | /--->[0|0]2
| \--->[0|1]1

, da sich die Höhe zwischen


| | | /--->[0|0]83
| | /--->[1|1]82
| | | \--->[0|0]81
| /--->[2|2]80
| | | /--->[0|0]79

und


\--->[3|4]6
| /--->[0|0]5
\--->[2|1]3

mehr als 1 unterscheidet, nämlich 2. Sehe ich das richtig, dass das kein AVL-Baum ist?

Das Java-Applet auf dieser Seite: http://www.ibr.cs.tu-bs.de/lehre/ss98/audii/applets/avlbaum/
liefert aber beim Einfügen der Elemente 1, 7, 6, 15, 5, 3, 18, 2, 12, 83, 82, 81, 80, 79, 13 die selbe Baumstruktur wie mein Programm (also die selbe Struktur wie oben).
Habe ich jetzt die AVL-Regel falsch verstanden oder ist das JavaApplet auf der Seite falsch?

Hier findet ihr einen Screenshot von dem Applet, damit ihr es nicht ausprobieren müsst: http://www.sebba-net.de/soft/avl-baum.png .

Ich wäre echt froh, wenn mir jemand helfen könnte.

Gruß, Florian

[cybercrow]

nein, dass stimmt schon so.
Soweit ich den Baum auf dem screenshot sehen kann.
Die roten Zahlen sind die Balance.
Du mußt von jedem Knoten rechts und links in die tiefste Ebene runter gehen und dabei die Kanten zählen, rechts ist z.B. plus und links minus. Das Ergebnis muß dann zwischen -1 und 1 liegen.
Du kannst dir nicht zwei beliebige Knoten aussuchen und da dann schauen ob der "höhen Unterschied" größer eins ist.
Du mußt ja nur die roten Zahlen im applet mal nachrechnen. Aber soviel wie ich vom Baum sehe denke ich das es gut stimmen könnte.

[ContainerDriver]

nein, dass stimmt schon so.
Soweit ich den Baum auf dem screenshot sehen kann.
Die roten Zahlen sind die Balance.
Du mußt von jedem Knoten rechts und links in die tiefste Ebene runter gehen und dabei die Kanten zählen, rechts ist z.B. plus und links minus. Das Ergebnis muß dann zwischen -1 und 1 liegen.
Du kannst dir nicht zwei beliebige Knoten aussuchen und da dann schauen ob der "höhen Unterschied" größer eins ist.
Du mußt ja nur die roten Zahlen im applet mal nachrechnen. Aber soviel wie ich vom Baum sehe denke ich das es gut stimmen könnte.
Danke! Ich denke ich habs jetzt verstanden.

Gruß, Florian