Frage zu binären Bäumen

[wookenny]

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

 

[NomadSoul]

Meinst Du Bayer-Bäume?
Kannste das mal irgendwie visualisieren?!

 

[wookenny]

Also ich meine schon binäre Suchbäume, B-Bäume sind ja was anderes.
Als Beispiel:
binärer Suchbaum

Hier ist ein AVL-Baum zu sehen.
Aber kein knotenbalancierter. Denn unter der 5 hängen links 4 und rechts 8 Knoten.

Der Teilbaum mit der 10 als Wurzel ist ein knotenbalacierter Baum.
Hier ist die Differenz der Knoten die im rechten und linken Teilbaum eines jeden Knoten hängen immer 1,0 oder -1.

Die Frage ist jetzt, wie man zeigt, dass alle Blätter im Knotenbalancierten Baum jeweils paarweise nur eine Höhendiffernz von höchstens 1 haben.

Im ganzen Baum(ist ja AVL) stimmts nicht. Hier ist die Differenz 2. Im 2. Beispiel stimmt es aber schon.

Ich hoffe, das klärt die Frage.

 

[mffm]

Hi,

Du kannst das mit Induktion über n = „Anzahl der Knoten“ beweisen:


Für n = 1 gilt die Behauptung natürlich.

n > 1:

Betrachte einen Baum mit n – 1 Knoten, an den ein neues Blatt angehängt werden soll.

Fall 1: Alle Blätter liegen in einer Tiefe t. Dann ist es egal, wo man ein neues Blatt anhängt, die Behauptung gilt immer.

Fall 2: Einige Blätter liegen in einer maximalen Tiefe t, die anderen höchstens in Tiefe t – 1.

Sei nun k der Knoten, an den man das neue Blatt anhängen will. Dieser liege in Tiefe t. Wenn dies einen gültigen Baum ergibt, ist die Behauptung widerlegt.

Bevor das neue Blatt angehängt wird, verfolgt man die Vorgänger von k so lange, bis man zum ersten Mal zu einem Knoten v kommt, bei dem an einem Teilbaum k hängt und am anderen ein Blatt mit der Tiefe t - 1.
Der eine Teilbaum, an dem k hängt, hat nun b Knoten, der
andere höchstens b – 1.

Wenn man nun das neue Blatt an k hängt, so ist hat dieser Teilbaum b + 1 Knoten, wodurch aber die Baumeigenschaft verletzt ist.


Der Beweis müßte eigentlich stimmen, ich hoffe, das hilft Dir weiter.

Gruß
Flo

 

[wookenny]

Ich glaube dein Beweis funktioniert nicht für allgemeine knotenbalancierte Bäume.
Denn im Fall1 erhält man ja einen Baum der Höhe h+1 der irgendwo als neues Blatt nun diesen zusätzlichen Knoten hängen hat. Allerdings weiss man nicht, ob alle knotenbalancierten Bäume mit n+1 Knoten so aussehen müssen.

Im 2.ten Fall auch. Es ist halt kein expliziter Algorithmus gegeben, der mir sagt, wie Blätter eingefügt werden sollen.


Mir ist aber ein Beweis eingefallen.
Per Induktion über die Höhe der Bäume. Ausserdem kann man zeigen, das die Hööhe dieser Bäume mit log_2 abgerundet nach oben beschränkt ist. Daher ist die Höhe dieser Bäume = log_2 abgerundet.
Dazu noch der einfache Beweis, das bei einen vollem Baum (mit (2^m^) -1 Knoten) alle Blätter die gleiche Höhe haben und die Induktion klappt.

Danke für deine Mühe.

 

[mffm]

Hi,

das war vielleicht etwas mißverständlich: Ich bin nicht davon ausgegangen, daß man einen neuen Knoten einfügt, indem ihn man einfach als neues Blatt anhängt.
Meine Idee war: Ein Baum mit n Knoten kann immer auf einen Baum mit n - 1 Knoten, an den man in der tiefsten Ebene ein Blatt anhängt, zurückgeführt werden (natürlich muß n die Anzahl der Knoten und nicht der Blätter sein) und dann schaut man, was passiert, wenn das Blatt an einer "ungünstigen" Stelle liegt.
Aber das nur als kleiner Nachtrag, Du hast ja schon einen Beweis gefunden.

Gruß
Flo