TU Wien:Algebra und Diskrete Mathematik UE (diverse)/Übungen SS19/Beispiel 314

Aus VoWi
Zur Navigation springen Zur Suche springen

Man zeige, dass die Anzahl der binären Suchbäume mit n Knoten durch die Catalan-Zahl C_{n} gegeben ist. (Hinweis: Man stelle eine Bijektion zwischen binären Suchbäumen und (geordneten) vollen Binärbäumen her und verwende das vorherige Beispiel.)

Lösungsvorschlag von Ryus[Bearbeiten]

Der Unterschied zwischen normalen binären Bäumen und vollen binären Suchbäumen ist, dass in binären Suchbäumen nicht jeder Knoten entweder keine oder zwei Nachfolger haben muss, sondern auch nur einen haben kann, wobei man jedoch dazwischen unterscheidet, ob der Nachfolger links oder rechts vom aktuellen Knoten ist.

In Beispiel 313 wurde bereits bewiesen, dass die Anzahl der vollen Binärbaum mit n+1 Blättern der n-ten Catalan-Zahl entspricht. Wenn wir es also schaffen, eine Bijektion zu finden, welche von einem binären Suchbaum mit n Knoten zu einem Binärbaum mit n+1 Blättern führt, haben wir damit auch sofort gezeigt, dass die Anzahl der binären Suchbäume mit n Knoten durch die n-te Catalan Zahl gegeben ist.

Dazu überlegen wir uns folgendes Verfahren: Wir nehmen den binären Suchbaum und fügen an jeden Knoten, der nicht zwei Nachfolger hat, so viele Nachfolger wie möglich (also maximal 2) an. So erhalten wir einen entsprechenden Baum mit n+1 Blättern. Diese Funktion ist bijektiv, da wir von jedem Baum mit n+1 Blättern auf einen Baum mit n Knoten kommen können, in dem wir diese Blätter einfach wieder entfernen.

TU Wien-Algebra und Diskrete Mathematik UE (diverse) - BaumBijektion.png

In Beispiel 310 wurde gezeigt, dass die Anzahl der Blätter eines Binärbaumes gleich der Anzahl der internen Knoten + 1 ist. Durch unsere Abbildung werden alle n Knoten zu internen Knoten. Die Anzahl der Blätter im so entstandenen neuen Baum muss daher n+1 sein!

Somit ist die Bijektion gefunden und die Aussage bewiesen.