Eigenschaften Binärbäume < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 10:12 Fr 16.11.2018 | | Autor: | Hela123 |
| Aufgabe | In dieser Aufgabe sollen ausgewählte Eigenschaften von Binärbäumen bzw. Suchbäumen bewiesen werden.
(a) Zeigen Sie, dass ein Binärbaum mit n Blättern genau n-1 innere Knoten hat.
(b) Zeigen Sie, dass es in jedem Binärbaum höchstens [mm] 2^i [/mm] Knoten der Tiefe i gibt.
(c) Zeigen Sie, dass für einen Binärbaum mit paarweise disjunkten Schlüsseln gilt: Die Suchbaumeigenschaft gilt genau dann, wenn der In-Order-Durchlauf die Schlüssel in aufsteigend sortierter Reihenfolge ausgibt. |
Hallo Forum,
ich habe alle 3 Teilaufgaben bewiesen, bin mir aber nicht sicher, ob meine Beweise korrekt sind.
Deswegen wäre ich sehr dankbar, wenn sich jemand die Beweise anschaut und ggf. auf die Fehler / Ungenauigkeiten hinweist.
Zum Teil (a):
Hier bin ich mir nicht sicher, ob mein Beweis korrekt ist:
Induktionsbeweis:
IA: n=1
1 Blatt (=Wurzel), 0 innere Knoten
In einem B-Baum mit einem Blatt gibt es keine innere Knoten, also erfüllt.
IS:
Sei w die Wurzel eines Binärbaumes mit insgesamt n > 1 Blätter.
Dann teilt sich der Baum bei w
in zwei Teilbäume [mm] T_1 [/mm] und [mm] T_2 [/mm] auf, die beide zusammen n1 + n2 = n + 1 Blätter besitzen. Nach Induktionsannahme gilt:
[mm] T_1 [/mm] hat genau n1 - 1 und [mm] T_2 [/mm] hat genau n2 - 1 innere Knoten, insgesamt hat T genau n1 + n2 - 2 = n - 1 innere Knoten.
Gehe ich richtig vor?
Ist der Beweis korrekt?
Zum Teil (b):
Wieder Induktionsbeweis:
IA: i = 0
Die Ebene 0 enthält alle Knoten mit Tiefe 0 zur Wurzel. Damit enthält die Ebene 0 genau 1 = [mm] 2^0 [/mm] Knoten (die Wurzel selber). Also erfüllt.
IV: ein Binärbaum der Tiefe i besitzt höchstens [mm] 2^i [/mm] Knoten
IS: i->i + 1
Die Knoten der Ebene i+1 sind genau alle Kinder aller Knoten der Ebene i.
Da jeder Knoten maximal 2 Kinder haben kann, enthält die Ebene i+1 genau [mm] 2*2^i=2^{i+1} [/mm] Knoten.
Auch hier die Frage: Ist der Beweis so in Ordnung?
Zum Teil (c):
Auch hier Induktionsbeweis:
Ich habe versucht über die Länge des Inorder-Durchlaufes.
IA: Als Basisfall verwenden wir die Längen 0 und 1. Ein Inorder-Durchlauf der Länge 0 ist der des leeren Baumes und ein Inorder-Durchlauf der Länge 1 ist der eines Baumes mit nur einem einzigen Element. Diese beiden Bäume erfüllen natürlich die Suchbaumeigenschaft.
IV: Seien [mm] B_l [/mm] und [mm] B_r [/mm] zwei beliebige aber feste binäre Bäume deren Inorder-Durchläufe x und y jeweils in sortierter Reihenfolge sind. Dann sind [mm] B_l [/mm] und [mm] B_r [/mm] binäre Suchbäume.
IS:
Für den Induktionsschritt betrachten wir eine (längere) Inorder-Traversierung des folgenden Baumes B:
B hat eine Wurzel mit Schlüssel k und linkem Teilbaum [mm] B_l [/mm] und rechtem Teilbaum [mm] B_r. [/mm]
Bei der Inorder-Traversierung von B werden zunächst alle Schlüssel aus [mm] B_l [/mm] (also x) dann k und anschließend alle Schlüssel aus [mm] B_r [/mm] (also y).
Die Inorder-Traversierung ist also durch x k y gegeben.
Sei nun x k y in sortierter Reihenfolge. Dann sind alle Schlüssel, die in x enthalten sind, höchstens so groß wie
k und damit auch alle Schlüssel in [mm] B_l [/mm] höchstens so groß wie k.
Analog dazu sind alle Schlüssel, die in y enthalten sind, mindestens so groß wie k und damit auch alle Schlüssel in
[mm] B_r [/mm] mindestens so groß wie k.
Insgesamt erfüllt damit auch der Baum B die Suchbaumeigenschaft.
Kann man das so beweisen?
Schönen Dank im Voraus!
Hela123
|
|
| |
|
> In dieser Aufgabe sollen ausgewählte Eigenschaften von
> Binärbäumen bzw. Suchbäumen bewiesen werden.
>
> (a) Zeigen Sie, dass ein Binärbaum mit n Blättern genau
> n-1 innere Knoten hat.
>
> (b) Zeigen Sie, dass es in jedem Binärbaum höchstens [mm]2^i[/mm]
> Knoten der Tiefe i gibt.
>
> (c) Zeigen Sie, dass für einen Binärbaum mit paarweise
> disjunkten Schlüsseln gilt: Die Suchbaumeigenschaft gilt
> genau dann, wenn der In-Order-Durchlauf die Schlüssel in
> aufsteigend sortierter Reihenfolge ausgibt.
> Hallo Forum,
>
> ich habe alle 3 Teilaufgaben bewiesen, bin mir aber nicht
> sicher, ob meine Beweise korrekt sind.
> Deswegen wäre ich sehr dankbar, wenn sich jemand die
> Beweise anschaut und ggf. auf die Fehler / Ungenauigkeiten
> hinweist.
>
> Zum Teil (a):
> Hier bin ich mir nicht sicher, ob mein Beweis korrekt
> ist:
>
> Induktionsbeweis:
> IA: n=1
> 1 Blatt (=Wurzel), 0 innere Knoten
> In einem B-Baum mit einem Blatt gibt es keine innere
> Knoten, also erfüllt.
>
> IS:
> Sei w die Wurzel eines Binärbaumes mit insgesamt n > 1
> Blätter.
> Dann teilt sich der Baum bei w
> in zwei Teilbäume [mm]T_1[/mm] und [mm]T_2[/mm] auf, die beide zusammen n1
> + n2 = n + 1 Blätter besitzen.
Wenn du von n auf n+1 induzierst, musst du starten mit
"Sei w die Wurzel eines Binärbaumes mit insgesamt n + 1 > 1 Blättern". Oder du gehst von n-1 auf n und schreibst "Sei w die Wurzel eines Binärbaumes mit insgesamt n > 1 Blättern", aber dann auch "Dann teilt sich der Baum bei w in zwei Teilbäume [mm]T_1[/mm] und [mm]T_2[/mm] auf, die beide zusammen n1 + n2 = n Blätter besitzen.
Nach Induktionsannahme
> gilt:
> [mm]T_1[/mm] hat genau n1 - 1 und [mm]T_2[/mm] hat genau n2 - 1 innere
> Knoten, insgesamt hat T genau n1 + n2 - 2 = n - 1 innere
> Knoten.
>
> Gehe ich richtig vor?
> Ist der Beweis korrekt?
>
Genauer (verkürzt) für Induktion von n-1 auf n:
Baum hat n Blätter, n>1, Aufteilung in 2 Teilbäume mit [mm] n_1 [/mm] + [mm] n_2 [/mm] = n Blätter, jeder hat [mm] n_1-1 [/mm] bzw. [mm] n_2-1 [/mm] innere Knoten, zusammen [mm] n_1+n_2-2 [/mm] = n - 2 innere Knoten. Nun fügen wir beide Teilbäume wieder zusammen, dadurch entsteht ein neuer innerer Knoten, somit nun n-1 innere Knoten.
Bemerkung: Die Aussage stimmt nur, wenn unter inneren Knoten Verzweigungen mit 2 Kindern verstanden werden. Sonst könnte man eine beliebig lange Kette mit immer nur einem Kind bilden (viele innere Knoten) mit nur einem Blatt am Ende.
|
|
|
| |
|
| Status: |
(Frage) überfällig  | | Datum: | 15:15 So 18.11.2018 | | Autor: | Hela123 |
Hallo HJKweseleit,
vielen lieben Dank für deine Antwort!(Und auch für die Antworten zu den vergangenen Themen, tut mir leid, dass ich nicht dazu gekommen war zu antworten).
> Genauer (verkürzt) für Induktion von n-1 auf n:
>
> Baum hat n Blätter, n>1, Aufteilung in 2 Teilbäume mit
> [mm]n_1[/mm] + [mm]n_2[/mm] = n Blätter, jeder hat [mm]n_1-1[/mm] bzw. [mm]n_2-1[/mm] innere
> Knoten, zusammen [mm]n_1+n_2-2[/mm] = n - 2 innere Knoten. Nun
> fügen wir beide Teilbäume wieder zusammen, dadurch
> entsteht ein neuer innerer Knoten, somit nun n-1 innere
> Knoten.
Gefällt mir auch besser, danke! 
> Bemerkung: Die Aussage stimmt nur, wenn unter inneren
> Knoten Verzweigungen mit 2 Kindern verstanden werden. Sonst
> könnte man eine beliebig lange Kette mit immer nur einem
> Kind bilden (viele innere Knoten) mit nur einem Blatt am
> Ende.
Die Voraussetzung ist bei uns aber gegeben.
Und wie findest du die andere beiden Beweise? Sind sie so in Ordnung?
Noch mal danke und viele Grüße
Hela123
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 15:20 Di 20.11.2018 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
| |
|
Zum Teil (b):
Wieder Induktionsbeweis:
IA: i = 0
Die Ebene 0 enthält alle Knoten mit Tiefe 0 zur Wurzel. Damit enthält die Ebene 0 genau 1 = $ [mm] 2^0 [/mm] $ Knoten (die Wurzel selber). Also erfüllt.
IV: ein Binärbaum der Tiefe i besitzt höchstens $ [mm] 2^i [/mm] $ Knoten
IS: i->i + 1
Die Knoten der Ebene i+1 sind genau alle Kinder aller Knoten der Ebene i.
Da jeder Knoten maximal 2 Kinder haben kann, enthält die Ebene i+1 genau höchstens $ [mm] 2\cdot{}2^i=2^{i+1} [/mm] $ Knoten.
------------------------------------------------------
Auch hier die Frage: Ist der Beweis so in Ordnung?
Ja, bis auf obige Korrektur. Es muss ja nicht jedes Blatt in der nächsten Generation genau 2 Kinder haben.
Für c) habe ich im Moment keine Zeit.
|
|
|
|
