ContainerDriver
03-09-2004, 11:38
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...
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...