Übung 12

Aufgabe 1: Suchbäume

a)

• Die Logarithmische Tiefe wird sicher gestellt, indem alle Blätter auf der gleichen Höhe gespeichert werden.
  Hierbei gibt es die Beschränkeung, dass (fast) alle inneren Knoten zwischen $a$ und $b$ Kinder haben (Menge).
  Dadurch stellen wir sicher, dass Operationen effizient laufen und es generell "nur" eine geringe Tiefe gibt.
  • Sicherstellen der Invariante beim
    • Einfügen durch Spalt-Operationen
    • Löschen durch Balancieren oder Verschmelzen

d) Beweis:

• Induktionsannahme: $n=1$ Suchbaum besteht nur aus Wurzel
  • Wurzel ist ein Blatt
  • Baum hat $0=(1-1)$ innere Knoten
• Induktionsvorraussetzung: Sei $n\in {\mathbb{N}}_i\forall 1\le n\le n$ gekte, dass ein binärer Suchbaum mit $n^{\prime }$ Blättern genau $n^{\prime }-1$ innere Knoten hat.
• Induktionsschritt: $n\to n+1$. Sei $T$ binärer Suchbaum mit $n+1$ Blättern $n+1\ge 2$, d.h. Wurzel ist innerer Knoten und hat genau 2 Kinder, die Wurzeln von Teilbäumen $T_1,T_2$ sind. Wir können $T_1,T_2$ als binäre Suchbäume mit $n_1\le n,n_2\le n$ Blättern auffassen
• $1\le n_1\le n=>T_1$ hat $n_1-1$ innere Knoten
• $1\le n_2\le n=>T:2$ hat $n_2-1$
• $\#$ innere Knoten von $T=n_1-1+n_2-1+1$
  • $T_1\to n_1$
  • $T_2\to n_2$
  • Wurzel $\to 1$
• $$\begin{gathered} =n_1+n_2-1 \\ =(n+1)-1=n \end{gathered}$$