 Bäume_Algorithmen_und_Datenstrukturen |
Flo
unregistriert
 |
|
| Bäume_Algorithmen_und_Datenstrukturen |
     |
Meine Frage:
Hallo,
ich komme bei einer Studienaufgabe absolut nicht weiter. Ich habe nicht einmal einen Ansatz, da man trinäre Bäume weder unter Google noch in ausgewählter Lektüre findet. Hier die Aufgabe:
Die Höhe eines Baums ist definiert als die Anzahl der Knoten in einem längsten Pfad
von Knoten zu einem Blatt. Damit hat ein Baum, der nur aus der Wurzel besteht, schon
die Höhe 1. Beweisen Sie, dass ein vollständiger trinärer Baum (jeder Knoten, der kein
Blatt ist, hat genau 3 Kinder) der Höhe h genau (3h 1048576 1)/2 Knoten enthält.
Hinweis: Wissen über die Geometrische Reihe ist immer nützlich.
Über Hinweise, Tipps etc. wäre ich sehr erfreut. lg
Meine Ideen:
...
|
|
18.06.2017 12:11 |
|
|
as_string 
Haudegen
Dabei seit: 06.11.2013
Beiträge: 639
Herkunft: Heidelberg
|
|
| RE: Bäume_Algorithmen_und_Datenstrukturen |
|
Hallo!
Was ein "trinärer Baum" ist, ist in der Aufgabe ja beschrieben: Jeder Nicht-Blatt-Knoten hat 3 Kinder. Bei einem "binären Baum" (den solltest Du finden können) sind es ja genau 2 Kinder.
Die Formel. die Du für die Höhe angegeben hast, kann ich leider nicht richtig erkennen. Kannst Du die nochmal deutlich schreiben?
Gruß
Marco
|
|
|
20.06.2017 11:09 |
|
|
|
