Aufgabe 1 - Beweis Mittlere Weglänge
Sei die mittlere Höhe eines Entscheidungsbaumes \( T \) wie folgt definiert
$$ h_{m}(T)=\frac{1}{|B(T)|} \sum \limits_{b \in B(T)} \operatorname{level}(b) $$
wobei \( B(T) \) die Menge der Blätter des Baumes \( T \) bezeichnet. Zur Erinnerung: Ein Entscheidungsbaum ist ein Binärbaum, in dem jeder Knoten genau zwei Kinder hat oder er selbst ein Blatt ist
Zeigen Sie: Für einen Entscheidungsbaum \( T \) gilt, dass \( h_{m}(T) \geq \log (|B(T)|) \). Gehen Sie dabei beim Induktionsschritt in folgenden Schritten vor:
1. Zeigen Sie, dass für einen Baum \( T \), der aus der Wurzel \( v \) und den rechten und linken Teilbẵumen \( T_{1} \) und \( T_{2} \) besteht, folgende Aussage gilt:
$$ h_{m}(T) \geq \frac{\left|B\left(T_{1}\right)\right| \log \left(\left|B\left(T_{1}\right)\right|\right)+\left|B\left(T_{2}\right)\right| \log \left(\left|B\left(T_{2}\right)\right|\right)}{|B(T)|}+1 $$
Kann mir einer einen Beweis aufschreiben damit ich das verstehe?
