wookenny
Erfahrenes Mitglied
Habs schon in nem anderen Forum versucht, aber da konnte mir erst mal auch keiner helfen. Aber hier gibts scheinbar mehr Programmierer.
Hab seit ein paar Tagen eine Frage zu binären Bäumen, die ich nicht gelöst bekomme.
Bei den binären Bäumen als Datenstrukur gibt es ja balancierte Bäume, damit die nicht zu einer Liste degenerieren.
Z.b. der bekannte AVL Baum ist ein höhenbalancierter Baum.
Jetzt soll ähnlich dem AVL Baum ein knotenbalancierter Baum betrachtet werden.
Also ein Baum, bei dem für jeden Knoten gilt, daß die Differenz der Knoten die rechts und die die links unter ihm hängen höchstens 1 ist.
Frage jetzt: Gilt für alle Paare von Blättern(Knoten die keine Söhne mehr haben), daß ihre Höhendifferenz im Baum höchstens 1 ist? Wenn ja, wie kann man dass schön beweisen?
Ich hoffe man kann die Formulierung der Frage verstehen, ist eigentlich ein einfacher Zusammenhang(nur doof zu formulieren), notfalls erläutere ich es noch mal genauer.
vielen Dank
wookenny
Hab seit ein paar Tagen eine Frage zu binären Bäumen, die ich nicht gelöst bekomme.
Bei den binären Bäumen als Datenstrukur gibt es ja balancierte Bäume, damit die nicht zu einer Liste degenerieren.
Z.b. der bekannte AVL Baum ist ein höhenbalancierter Baum.
Jetzt soll ähnlich dem AVL Baum ein knotenbalancierter Baum betrachtet werden.
Also ein Baum, bei dem für jeden Knoten gilt, daß die Differenz der Knoten die rechts und die die links unter ihm hängen höchstens 1 ist.
Frage jetzt: Gilt für alle Paare von Blättern(Knoten die keine Söhne mehr haben), daß ihre Höhendifferenz im Baum höchstens 1 ist? Wenn ja, wie kann man dass schön beweisen?
Ich hoffe man kann die Formulierung der Frage verstehen, ist eigentlich ein einfacher Zusammenhang(nur doof zu formulieren), notfalls erläutere ich es noch mal genauer.
vielen Dank
wookenny