| Vorheriges Thema anzeigen :: Nächstes Thema anzeigen |
| Autor |
Nachricht |
Formelhai
Anmeldungsdatum: 25.06.2005
Beiträge: 5
|
 Verfasst am: 25. Jun 2005 12:11 Titel: Minimale Zahl der Knoten AVL Baum |
 |
|
Hallo,
ich soll beweisen, dass für die minimale Zahl von Knoten in einem AVL-Baum der Höhe h gilt:
N(h) > N(h-1) + N(h-2) + 1
Würdet ihr das auch über Induktion machen, oder habt ihr eine bessere Idee?
thx |
|
| Nach oben |
|
 |
|
|
ED209
Anmeldungsdatum: 30.05.2005
Beiträge: 122
|
| Verfasst am: 25. Jun 2005 12:17 Titel: |
|
|
Bist du sicher, dass das groesser ist? Ich haette jetzt gesagt, dass das gleich ist.
_________________
+++++++++++++[>++++>+<<-]>.--.>---. |
|
| Nach oben |
|
|
Gast
|
| Verfasst am: 25. Jun 2005 13:03 Titel: |
|
|
| Es ist auch gleich, allerdings ist die Aufgabenstellung so, dass man zeigen soll, dass es größer ist. Wenn es gleich wäre, wie würdet ihr es dann zeigen? |
|
| Nach oben |
|
|
Formelhai
Anmeldungsdatum: 25.06.2005
Beiträge: 5
|
| Verfasst am: 25. Jun 2005 13:04 Titel: |
|
|
| Es ist auch gleich, allerdings ist die Aufgabenstellung so, dass man zeigen soll, dass es größer ist. Wenn es gleich wäre, wie würdet ihr es dann zeigen? |
|
| Nach oben |
|
|
ED209
Anmeldungsdatum: 30.05.2005
Beiträge: 122
|
| Verfasst am: 25. Jun 2005 13:42 Titel: |
|
|
| Formelhai hat Folgendes geschrieben: | | Es ist auch gleich, allerdings ist die Aufgabenstellung so, dass man zeigen soll, dass es größer ist. Wenn es gleich wäre, wie würdet ihr es dann zeigen? |
Wenn wir von einer widerspruchsfreien Mathematik ausgehen (normalerweise geht man davon aus) kann das nicht gleichzeitig groesser und gleich sein.
Wie ich das zeigen wuerde, dass es gleich ist kann ich nicht sagen, da es in meinen Augen direkt aus der Definition hervorgeht.
_________________
+++++++++++++[>++++>+<<-]>.--.>---. |
|
| Nach oben |
|
|
kurellajunior
Administrator
Anmeldungsdatum: 14.02.2005
Beiträge: 214
Wohnort: Berlin-Pankow
|
| Verfasst am: 26. Jun 2005 11:24 Titel: |
|
|
Vielleicht habe ich AVL-Baum falsch in Erinnerung aber:
&=&1\\ N(2)&=&2\\ N(3)&=&4\\ N(4)&=&8 \neq 7=N(3)+N(2)+1)
oder?
_________________
 |
|
| Nach oben |
|
|
Formelhai
Anmeldungsdatum: 25.06.2005
Beiträge: 5
|
| Verfasst am: 26. Jun 2005 12:43 Titel: |
|
|
soweit ich weiß ist das auch falsch.
N(0) = 1
N(1) = 2
N(2) = 4
N(3) = 7 = N(2) + N(1) + 1
... |
|
| Nach oben |
|
|
kurellajunior
Administrator
Anmeldungsdatum: 14.02.2005
Beiträge: 214
Wohnort: Berlin-Pankow
|
| Verfasst am: 26. Jun 2005 16:01 Titel: |
|
|
Ok, dann zur Sicherheit, was bitte genau ist ein AVL-Baum und wofür steht N(x) genau?
_________________
|
|
| Nach oben |
|
|
Formelhai
Anmeldungsdatum: 25.06.2005
Beiträge: 5
|
| Verfasst am: 26. Jun 2005 18:52 Titel: |
|
|
h ist die Höhe des Baums
N(h) ist die minimale Anzahl von Knoten so dass der Baum noch AVL-Eigenschaft besitzt.
AVL- Eigenschaft: für jeden Knoten v in dem Baum T gilt:
Höhe (linken Unterbaum) - Höhe (rechten Unterbaum) = -1 oder 0 oder +1 |
|
| Nach oben |
|
|
kurellajunior
Administrator
Anmeldungsdatum: 14.02.2005
Beiträge: 214
Wohnort: Berlin-Pankow
|
| Verfasst am: 26. Jun 2005 21:12 Titel: |
|
|
Verstanden und nein, keine bessere Idee als Induktion. Nur solltest Du vorher festlegen ob die Wurzel die Höhe 1 oder 0 hat um Verwirrungen zu vermeiden. Kannst Deinen Beweis gerne posten, für alle interessierten 
Jan
_________________
|
|
| Nach oben |
|
|
|
FAQ
Suchen
Mitgliederliste
Benutzergruppen
Registrieren
Profil
Einloggen, um private Nachrichten zu lesen
Login
