 |
 |
 |
 |
 |
 |
Startseite » Forum » Binärbaum, Höhe, Knoten, Beweis
Binärbaum, Höhe, Knoten, Beweis
Universität / Fachhochschule
Sonstiges
Tags: Baum, Beweis, Binärbaum, Knoten, Lemma?
 
|
  |
|---|
|
Hallo zusammen, Ich komme bei der Aufgabe nicht weiter, bzw. hab kein Plan wie ich des Beweisen soll. Aufgabe: Beweisen Sie das folgende Lemma. Enthält ein Binärbaum Knoten, so beträgt seine Höhe mindestens −1. LG Lasina Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert): "Ich benötige bitte nur das Ergebnis und keinen längeren Lösungsweg." |
| Hierzu passend bei OnlineMathe: |
|
 |
|
Hallo, du meinst mit den ? |
|
|
|
Hallo, ermanus schrieb: > du meinst mit log den log2? Ich denke schon. Zudem nehme ich an, dass ein aus einem einzigen Knoten bestehender Baum die Höhe Null hat (Anzahl der Kanten des längsten Weges von der Wurzel aus, gerichtete Kanten). Zur Lösung: Berechne den Zusammenhang zwischen der Höhe eines "vollen" Binärbaums und der Anzahl seiner Knoten . Mit "voll" meine ich einen Baum, bei dem für alle Knoten gilt: Die Anzahl der Nachbarn ist entweder 0 oder 2 und die Elemente mit Null Nachbarn sind auf einer Ebene (der obersten, also der mit der höchsten Zahl). Sicher habt ihr für so etwas einen geeigneten Begriff. Sollte klar sein, dass ein nicht "voller" Baum im Vergleich zum vollen Baum mit gleicher Höhe weniger Knoten haben muss. Soll heißen, du kannst eine Ungleichung zwischen und finden, die im Falle "voller" Bäume gerade Gleichheit nach sich zieht. Diese Ungleichung kannst du umstellen nach und solltest die gesuchte Gleichung daraus ableiten. Mfg Michael |
|
Diese Frage wurde automatisch geschlossen, da der Fragesteller kein Interesse mehr an der Frage gezeigt hat.
|
1372648
1372621