1/3 balancierter Binärbaum < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) reagiert/warte auf Reaktion  | | Datum: | 19:00 Mo 19.01.2009 | | Autor: | Tasel |
| Aufgabe | Wir definieren einen [mm] $\bruch{1}{3}$-balancierten [/mm] Binärbaum $B$ wie folgt:
Für jeden Teilbaum aus $B$ mit Wurzel $v$ und [mm] $n_{v}$ [/mm] Knoten gilt: Sowohl der rechte als auch der linke Teilbaum von $v$ hat maximal [mm] $\bruch{2}{3}n_{v}$ [/mm] Knoten.
Zeige mittels Induktion über die Höhe $h$: Für die Höhe $h$ eines [mm] $\bruch{1}{3}$-balancierten [/mm] Binärbaums $B$ mit $n$ Knoten gilt: $h [mm] \le log_{\bruch{3}{2}}(n)$. [/mm] |
Den Induktionsanfang bekomme ich zwar noch hin:
Ein Baum der Höhe 0 ($h = 0$) hat nur ein Knoten, welcher gleichzeitig die Wurzel ist.
IA: Für $h = 0$:
$0 [mm] \le log_{\bruch{3}{2}}(1)$
[/mm]
$0 [mm] \le [/mm] 0$
Nur komme ich allerdings beim Induktionsschritt nicht weiter. Wie stelle ich sicher, dass ich immer ein [mm] $\bruch{1}{3}$-balancierten [/mm] Baum erhalte? Müsste ich jetzt nicht zeigen, was bei $h+1$ geschieht?
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 07:26 Di 20.01.2009 | | Autor: | bazzzty |
> [Def. 1/3-balancierter Binärbaum]
> Zeige mittels Induktion über die Höhe [mm]h[/mm]: Für die Höhe [mm]h[/mm]
> eines [mm]\bruch{1}{3}[/mm]-balancierten Binärbaums [mm]B[/mm] mit [mm]n[/mm] Blättern
> gilt: [mm]h \le log_{\bruch{2}{3}}(n)[/mm].
Vorsicht, hier ist ein Fehler. So ist sie sicher nicht lösbar, weil [mm]log_{\bruch{2}{3}}(n)[/mm] negativ ist für alle $n>1$. Da Du mit [mm]log_{\bruch{3}{2}}(n)[/mm] weiterrechnetst, gehe ich mal davon aus, dass das stimmt.
Und ich vereinfache mal die Aufgabe:
[mm]n\geq(\bruch{3}{2})^h[/mm] (das ist äquivalent).
> Den Induktionsanfang
> bekomme ich zwar noch hin:
>
> Ein Baum der Höhe 0 ([mm]h = 0[/mm]) hat nur ein Blatt, welches
> gleichzeitig die Wurzel ist.
>
> IA: Für [mm]h = 0[/mm]:
>
> [mm]0 \le log_{\bruch{3}{2}}(1)[/mm]
> [mm]0 \le 0[/mm]
Ja. Es stimmt also für h=0.
> Nur komme ich allerdings beim Induktionsschritt nicht
> weiter. Wie stelle ich sicher, dass ich immer ein
> [mm]\bruch{1}{3}[/mm]-balancierten Baum erhalte?
Das gehört zur Voraussetzung (siehst Du gleich noch).
> Müsste ich jetzt
> nicht zeigen, was bei [mm]h+1[/mm] geschieht?
Ja. Aber erst kommt die Induktionsannahme.
INDUKTIONSANNAHME: Es gilt für ein $h$, dass jeder 1/3-balancierter Baum mit Höhe h mindestens [mm] (3/2)^h [/mm] Blätter hat.
Jetzt der Induktionsschluss: Wenn es für ein h gilt, dann auch für h+1.
INDUKTIONSSCHLUSS: Sei B ein 1/3-balancierter Binärbaum mit Höhe h+1. Mindestens einer der beiden Teilbäume hat also Höhe h. Den nennen wir [mm] B_1. [/mm] Auch [mm] B_1 [/mm] ist 1/3-balanciert. Nach Induktionsannahme hat [mm] B_1 [/mm] also mindestens [mm]n_1=XXX[/mm] Blätter. Da B 1/3-balanciert ist, gilt für die Anzahl der Blätter von $B$: [mm]n\geq YYY\geq \bruch{3}{2}^{h+1}[/mm]. Was zu beweisen war.
Ich hab Dir noch was zum Ausbrüten hinterlassen, wenn die Struktur nicht klar ist, frag einfach nach.
Ein ganz allgemeiner Tipp zu Induktionen: Schreib Induktionsanfang, -annahme und -schluss hin. Mach Dir bei -anfang und -schluss klar, was genau Du zeigen musst. Das geht meist ohne den Lösungsweg zu kennen, ganz mechanisch:
IAnf: zu zeigen: Es gilt für 1 (oder 0, selten fängt man höher an).
IAnn: Es gilt für h (n,m...).
IS: Zu zeigen: Dann gilt es auch für h+1.
|
|
|
| |
|
| Status: |
(Frage) beantwortet  | | Datum: | 17:35 Di 20.01.2009 | | Autor: | Tasel |
Danke für die Antwort!
Wie ich heute erfahren habe, ist dem Aufgabensteller ein Fehler unterlaufen. Es werden nicht die Blätter, sondern die Knoten in den Teilbäumen betrachtet (habe meinen Text entsprechend geändert und den kleinen Tippfehler ebenfalls korrigiert).
Zum IS:
$ [mm] B_{1} [/mm] $ hätte somit mindestens $ [mm] n_{1} [/mm] = [mm] (\bruch{3}{2})^{h} [/mm] $ Knoten.
Nun komme ich nicht weiter. $ B $ hätte insgesamt die Anzahl von $ [mm] B_{1} [/mm] $ plus die Anzahl des zweiten Teilbaums + 1 (Knoten von $ B $) Knoten. Nur woher weiß ich wie viele Knoten der zweite Teil von $ B $ hat?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 09:23 Mi 21.01.2009 | | Autor: | bazzzty |
> Danke für die Antwort!
>
> Wie ich heute erfahren habe, ist dem Aufgabensteller ein
> Fehler unterlaufen. Es werden nicht die Blätter, sondern
> die Knoten in den Teilbäumen betrachtet (habe meinen Text
> entsprechend geändert und den kleinen Tippfehler ebenfalls
> korrigiert).
Das ändert zum Glück nichts an dem Beweis.
>
> Zum IS:
>
> [mm]B_{1}[/mm] hätte somit mindestens [mm]n_{1} = (\bruch{3}{2})^{h}[/mm]
> Knoten.
Exakt.
> Nun komme ich nicht weiter. [mm]B[/mm] hätte insgesamt die Anzahl
> von [mm]B_{1}[/mm] plus die Anzahl des zweiten Teilbaums + 1
> (Knoten
> von [mm]B [/mm]) Knoten. Nur woher weiß ich wie viele Knoten der
> zweite Teil von [mm]B[/mm] hat?
Das mußt Du zum Glück nicht bestimmen. Du willst nur zeigen, dass, wenn B 1/3-balanciert ist, B mindestens [mm]\bruch{3}{2}^{h+1}[/mm] Knoten hat. Du kannst also jetzt verwenden:
a) B hat Höhe h+1
b) [mm] B_1 [/mm] hat Höhe h und mindestens [mm]\bruch{3}{2}^{h}[/mm] Knoten.
c) B ist 1/3-balanciert und deshalb enthält keiner der beiden Teilbäume darf mehr als 2/3 der Knoten.
Setze einfach mal b) und c) zusammen. Das war die zweite offene Gleichung in meiner letzten Antwort. Was folgt daraus für die Knotenzahl von B?
|
|
|
|
