Binärbäume
-
Ahoi,
hab ein problem mit folgender Aufgabe:
Sei k(i) die Anzahl der Knoten des Teilbaumes mit Wurzel i. Zeigen sie, dass für jeden Knoten i gilt: Die Anzahl der Knoten des größeren Teilbaumes ist maximal
2/3*k(i).Ich nehme an, dass ich da mittels vollst. Induktion rangehen kann, aber noch fehlt mir dazu der richtige Ansatz.
-
Hmmm stimmt doch nicht ein Binärbaum kann auch zuner Liste werden dann wäre die max Größe des Maxbaums k(i)....
-
Um was für Bäume handelt es sich denn, bzw. werden sie nach irgendeiner Vorschrift balanciert?
-
es handelt sich um Heaps, also bin. Bäume, die bis auf die letzte Ebene vollst. ausgefüllt sein müssen, linkes Kind von i ist 2i, rechtes Kind 2i+1 und der Elternknoten von i ist [i/2].
-
der größere teilbaum kann nicht mehr als eine ebene tiefer sein als der kleinere teilbaum. im extremfall ist sind alle blätter des größeren teilbaums gleich tief und eine ebene teifer als alle blätter des kleineren teilbaums. dann hat der größere teilbaum 2^t-1 elemente und der kleinere hat 2^(t-1)-1 elemente.
alle unter k(i) sind zusammen 1 + 2^t-1 + 2^(t-1)-1 und alle des größeren teilbaums sind 2^t-1.zu zeigen ist, daß 2^t-1 <= 2/3 * (1 + 2^t-1 + 2^(t-1)-1)
ob das geht?