Mit Induktion 2^d-1 Schlüssel innerhalb von Linksbaum zeigen

Question

Hallo zusammen,

ich habe folgende Aufgabe bekommen.

$$\text{Sei B ein Linksbaum und }d\in\mathbb{N} \text{ der größte an einem Knoten von B vorkommenden Distanzwert}\\\text{Zeigen Sie induktiv, dass B mindestens }2^d-1 \text{ Schlüssel speichert.}$$

Könnte mir da jemand bei helfen? Ich habe absolut keine Ahnung, wie man das berechnen soll.

Vielen Dank im Voraus :)

Answer 1

Hallo LLinux. Ich beginne hier mit einer ganz ähnlichen Aufgabe: Ein Binärbaum der Tiefe t hat maximal K = 2^t - 1 Knoten. Gesucht ist der Induktionsbeweis.

Gelingt dir dieser Beweis?