Struktuelle Induktion auf Bäumen?

Aufgabe:

Betrachten wir die folgenden Funktionsdefinitionen :

data Tree a = Leaf a | Node a (Tree a) (Tree a)

sumLeaves :: Tree a -> Integer

sumLeaves (Leaf x) = 1

sumLeaves (Node _ lt rt) = sumLeaves lt + sumLeaves rt

sumNodes :: Tree a -> Integer

sumNodes (Leaf x) = 0

sumNodes (Node _ lt rt) = 1 + sumNodes lt + sumNodes rt

Beweisen Sie mittels struktureller Induktion, dass für alle endlichen Bäume t :: Tree a gilt:

sumLeaves t = sumNodes t + 1

Answer 1

[KarlRanseierIII]

Beweisen Sie mittels struktureller Induktion, dass für alle endlichen Bäume t :: Tree a gilt:

sumLeaves t = sumNodes t + 1

Das kann nur dann gelten, wenn der Baum voll besetzt ist, denn dann gilt ja, daß die Anzahl der Knoten in jeder Ebene 2^t ist. Sei obdA t die Blattebene, dann liegen in der Blattebene 2^t Blätter.Zugleich gibt es

$\sum_{i=0}^{t-1}2^i=2^t-1$ Innere Knoten.

Also ist die Zahl der Blätter um genau 1 größer als die Zahl der inneren Knoten.

Zu Deiner Verankerung, t=0 ist lediglich die Wurzel, Du hast 0 innere Knoten und genau 1 Blatt. Alles weitere ergibt sich strukturell dadurch, daß Du aus jedem Blatt immer einen inneren Knoten mit 2 neuen Blättern machst.

Man kann den Prozess auch umgekehrt durch Kontraktion des Baumes machen.

Ein weiterer Ansatz wäre:

Wir betrachten Baum der Tiefe t und nehmen an die Eigenschaft ist erfüllt, Baum der Tiefe t+1 entsteht, indem ich 2 Bäume der Tiefe t unter einer neuen Wurzel zusammenfassen, hierbei verdoppelt sich die Blattzahl, die Zahl der inneren Knoten verdoppelt sich und es kommt noch die neue Wurzel als innerer Knoten hinzu.

Aber wie gesagt, das gitl wirklich nur für den Vollbesatz.

Answer 2

[Erzesel]

Ist dir schon mal aufgefallen, das sich hier niemand mit Deinen Fragen auskennt?

Möglicherweise wärst du in einem Haskelforum besser aufgehoben?

• https://www.haskell.org/