Matroids Matheplanet Forum Index
Moderiert von matroid
Informatik » Algorithmen / Datenstrukturen » AVL Baum, Induktion
Druckversion
Druckversion
Autor
Universität/Hochschule J AVL Baum, Induktion
MePep
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 08.05.2020
Mitteilungen: 135
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Themenstart: 2020-06-25


Hallo,

Ich habe folgendes Problem:

Gegebn ist ein AVL-Baum der Tiefe d. Ich soll nun Induktiv beweisen, das solch ein Baum bis zur Tiefe \(\bigg\lfloor \frac{d}{2} \bigg\rfloor\) vollständig gefüllt ist.

Induktionsanfang: Man kann für den Basisfall d = 0 und d = 1 zeigen, dass diese Aussage stimmt.

Induktionsvorraussetzung: Die Aussage stimmt für ein festes aber beliebiges d.

Induktionsschritt: Nun soll die Aussage auch für einen Baum der Tiefe d+1 gelten. Hat man einen AVL-Baum der Tiefe d+1, so hat ein Teilbaum der Wurzel die Tiefe d, der andere entweder auch die Tiefe d oder d-1. Nur so ist die AVL Eigenschaft für die Wurzel R erfüllt, sprich |depth(R.left) - depth(R.right)| \(\leq\) 1. Aus der IV kann ich dann ja sagen bis wohin die Teilbäume vollständig gefüllt sind, also bis zu welcher Tiefe. Aber ich komme verflixt nochmal nicht auf den Schluss von \(\bigg\lfloor \frac{d+1}{2} \bigg\rfloor\). Ich weiß einfach nicht wie man dahin kommt.

Kann mir vielleicht jemand weiterhelfen?

Mfg



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Kitaktus
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.09.2008
Mitteilungen: 6571
Aus: Niedersachsen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.1, eingetragen 2020-06-26


1) Als IV reicht es nicht aus, die Eigenschaft für Bäume der Tiefe d vorauszusetzen. Was du stattdessen brauchst, merkst Du wahrscheinlich im Laufe des Beweises.
Der IA ist auch entsprechend anzupassen.
2) Du stehst praktisch vor dem offenen Tor, musst nur noch hindurchgehen.
Bis zu welcher Tiefe sind denn die beiden Teilbäume vollständig?
Daraus folgt dann direkt die Induktionsbehauptung.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Creasy
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 22.02.2019
Mitteilungen: 547
Aus: Bonn
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.2, eingetragen 2020-06-26


Hallo,

Vermutlich ist die aussage, dass der baum mindestens bis zur tiefe [d/2] befüllt ist und nicht genau bis zu dieser tiefe. Andernfalls wäre zum bsp ein Avv baum mit 3 Knoten (d=1) der Aussage nach nur bis zur tiefe 0 vollständig.

Du hast also dass obda der linle Teilbaum bis mindestens zur [d-1/2] Ebene und der rechte bis zu [d/2] Ebene befüllt ist (man lässt also die Wurzel erstmal außen vor).
Dann ist der ursprünglich betrachtete baum um 1 Ebene mehr vollständig befüllt (Ebene 0 kommt wieder dazu).
(Soweit warst du glaub ich schon?)

Jetzt hilft dir vielleicht  [(d-1)/2] +1 = [(d+1)/2] weiter.

(Entschuldige die Faulheit für die Darstellung)

[Die Antwort wurde vor Beitrag No.1 begonnen.]


-----------------
Smile (:



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
MePep
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 08.05.2020
Mitteilungen: 135
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.3, vom Themenstarter, eingetragen 2020-06-26


2020-06-26 08:35 - Creasy in Beitrag No. 2 schreibt:
Hallo,

Vermutlich ist die aussage, dass der baum mindestens bis zur tiefe [d/2] befüllt ist und nicht genau bis zu dieser tiefe. Andernfalls wäre zum bsp ein Avv baum mit 3 Knoten (d=1) der Aussage nach nur bis zur tiefe 0 vollständig.

Du hast also dass obda der linle Teilbaum bis mindestens zur [d-1/2] Ebene und der rechte bis zu [d/2] Ebene befüllt ist (man lässt also die Wurzel erstmal außen vor).
Dann ist der ursprünglich betrachtete baum um 1 Ebene mehr vollständig befüllt (Ebene 0 kommt wieder dazu).
(Soweit warst du glaub ich schon?)

Jetzt hilft dir vielleicht  [(d-1)/2] +1 = [(d+1)/2] weiter.

(Entschuldige die Faulheit für die Darstellung)

[Die Antwort wurde vor Beitrag No.1 begonnen.]

Die Aussage ist Inklusive, nicht exklusive, leider. Es stimmt zwar schon, dass ein AVL Baum mit 3 Knoten auch in der Tiefe d = 1 komplett gefüllt ist. Jedoch geht es hier denke ich eher um eine Allgemeine Aussage, das eben bis zu dieser Tiefe mindestens gefüllt ist und über die anderen keine Aussage möglich ist.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Creasy
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 22.02.2019
Mitteilungen: 547
Aus: Bonn
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.4, eingetragen 2020-06-26


Ja das sehe ich ja genauso wie du.

Falls die Aufgabe noch nicht gelöst ist: wo hängst du noch?

Falls die Aufgabe gelöst ist, setze einfach das Häkchen für gelöst.

Grüsse



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
MePep
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 08.05.2020
Mitteilungen: 135
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.5, vom Themenstarter, eingetragen 2020-06-26


2020-06-26 11:37 - Creasy in Beitrag No. 4 schreibt:
Ja das sehe ich ja genauso wie du.

Falls die Aufgabe noch nicht gelöst ist: wo hängst du noch?

Falls die Aufgabe gelöst ist, setze einfach das Häkchen für gelöst.

Grüsse

Ich hab etwas Probleme mit den Gaußklammern, also warum

"Jetzt hilft dir vielleicht  [(d-1)/2] +1 = [(d+1)/2] weiter." das so ist.

Muss man nicht auch zwei Fälle betrachten? Also einmal: Linker UND rechter Teilbaum hat Tiefe d

Und: Linker/Rechter hat Tiefe d, Komplement hat Tiefe d-1?

Oder macht das insgesamt keinen Unterschied?

Wenn ich jetzt den zweiten Fall betrachte hat einer, wie du schon gesagt hast, alles bis zur Tiefe [d-1/2] und der andere bis Tiefe [d/2] alles voll befüllt. Wenn ich jetzt noch die Wurzel hinzunehme dann kommt noch eine zusätzlich befüllte Tiefe ja. Weil einer der beiden Teilbäume ja nur bis [(d-1)/2] befüllt ist, gilt dies also auch für den gesamten Baum oder?

Und diese Tiefe von der Wurzel aus gesehen ist ja [(d-1)/2] + 1 oder nicht? Aber wie sieht es dann mit dem anderen Fall aus? Oder folgt dieser direkt aus diesem?

Mfg



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
MePep
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 08.05.2020
Mitteilungen: 135
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.6, vom Themenstarter, eingetragen 2020-06-26


2020-06-26 08:29 - Kitaktus in Beitrag No. 1 schreibt:
1) Als IV reicht es nicht aus, die Eigenschaft für Bäume der Tiefe d vorauszusetzen. Was du stattdessen brauchst, merkst Du wahrscheinlich im Laufe des Beweises.
Der IA ist auch entsprechend anzupassen.
2) Du stehst praktisch vor dem offenen Tor, musst nur noch hindurchgehen.
Bis zu welcher Tiefe sind denn die beiden Teilbäume vollständig?
Daraus folgt dann direkt die Induktionsbehauptung.

Zu 1): Meinst du damit vielleicht das man annehmen muss, dass es nicht nur für d sondern alle Werte kleiner gleich d gilt ?



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Creasy
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 22.02.2019
Mitteilungen: 547
Aus: Bonn
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.7, eingetragen 2020-06-26


Für die Gleichung mit den Gausklammern betrachte zwei Fälle: d=2k+1 und d=2k und berechne jeweils beide Seiten.

Wie du schon sagtest ist die aussage nur, dass es bis mindestens zu der Tiefe [..] befüllt ist.

Beide Fälle laufen dann aber zusammen in: ein Teilbaum ist mindestens bis zur tiefe [(d-1)/2] und der andere bis mindestens zur tiefe [d/2] gefüllt.


Und ja: du brauchst die IV ja auch für Bäume der Tiefe d-1.

Beste Grüsse
CreasY



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
MePep
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 08.05.2020
Mitteilungen: 135
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.8, vom Themenstarter, eingetragen 2020-06-26


Also was ich machen könnte wäre z.B. im Induktionsanfang zu sagen:

Ich wähle d = 2 und zeige, dass es sowohl für d = 2, also auch d = 1 und d = 0 gilt.

Dann kann ich in meiner IV vorraussetzen, dass die Aussage für ein festes aber beliebiges d, und auch jedes d' > 0 bis d-1 gilt (stimmt das?)

"Für die Gleichung mit den Gausklammern betrachte zwei Fälle: d=2k+1 und d=2k und berechne jeweils beide Seiten."

Also du meinst die Unterscheidung ob d eine gerade oder ungerade Zahl ist, richtig? Wenn sie gerade ist, dann kann ich die Gaußklammern im Fall von d/2 einfach weglassen. Im fall von (d-1)/2 aber nicht.

Wie Kitaktus schon gesagt habe stehe ich vermutlich wirklich vorm offenen Tor, vielleicht bin ich auch schon durchgelaufen ohne es zu merken.

Es tut mir auch echt leid aber so sehr ich mich bemühe, so viel Zeit wie ich auch aufwende ich bin und fühle mich einfach so dermaßen dumm gerade, ich komme einfach nicht drauf. Ich verstehe einfach immer noch nicht wie man denn auf die \(\bigg\lfloor (d+1)/2 \bigg\rfloor\) kommt. Wenn ein Teilbaum bis \(\bigg\lfloor d/2 \bigg\rfloor\) und der andere bis \(\bigg\lfloor (d-1)/2 \bigg\rfloor\) gefüllt ist, dann würde ja die Tiefe des \(\bigg\lfloor d/2 \bigg\rfloor\) Baums nicht mitzählen da der andere ja eventuell niedriger ist. Jetzt müsste ich dann noch zeigen, dass \(\bigg\lfloor (d-1)/2 \bigg\rfloor\) + 1 = \(\bigg\lfloor (d+1)/2 \bigg\rfloor\)
ist oder wie?



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Creasy
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 22.02.2019
Mitteilungen: 547
Aus: Bonn
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.9, eingetragen 2020-06-27


2020-06-26 21:26 - MePep in Beitrag No. 8 schreibt:
Also was ich machen könnte wäre z.B. im Induktionsanfang zu sagen:

Ich wähle d = 2 und zeige, dass es sowohl für d = 2, also auch d = 1 und d = 0 gilt.

Dann kann ich in meiner IV vorraussetzen, dass die Aussage für ein festes aber beliebiges d, und auch jedes d' > 0 bis d-1 gilt (stimmt das?)

Das stimmt zwar, aber das kannst du in der IV auch annehmen, wenn du den IA nur für d=0 machst (wobei $d'\geq 0$ sein sollte).
Ehrlich gesagt sehe ich auch noch nicht ganz, was Kikaktus am IA stört, aber werden wir ja vielleicht noch rausfinden :)


"Für die Gleichung mit den Gausklammern betrachte zwei Fälle: d=2k+1 und d=2k und berechne jeweils beide Seiten."

Also du meinst die Unterscheidung ob d eine gerade oder ungerade Zahl ist, richtig? Wenn sie gerade ist, dann kann ich die Gaußklammern im Fall von d/2 einfach weglassen. Im fall von (d-1)/2 aber nicht.
Da du die Gleichung unten selbst nochmal hinschreibst, kommentiere ich das unten.


Es tut mir auch echt leid aber so sehr ich mich bemühe, so viel Zeit wie ich auch aufwende ich bin und fühle mich einfach so dermaßen dumm gerade, ich komme einfach nicht drauf.
Sowas passiert und ist nicht unnormales. Manchmal muss man auch einfach mal einen Abend nicht drüber nachdenken, und am nächsten Tag versteht mans auf einmal :)


 Ich verstehe einfach immer noch nicht wie man denn auf die \(\bigg\lfloor (d+1)/2 \bigg\rfloor\) kommt. Wenn ein Teilbaum bis \(\bigg\lfloor d/2 \bigg\rfloor\) und der andere bis \(\bigg\lfloor (d-1)/2 \bigg\rfloor\) gefüllt ist, dann würde ja die Tiefe des \(\bigg\lfloor d/2 \bigg\rfloor\) Baums nicht mitzählen da der andere ja eventuell niedriger ist. Jetzt müsste ich dann noch zeigen, dass \(\bigg\lfloor (d-1)/2 \bigg\rfloor\) + 1 = \(\bigg\lfloor (d+1)/2 \bigg\rfloor\)
ist oder wie?

zur letzten Frage: Absolut korrekt!
Ich fasse noch mal von vorne zusammen:
Sei B ein AVL Baum der Tiefe d+1. Wir entfernen die Wurzel von B und erhalten die Teilbäume B_L und B_R (Links und Rechts). Diese sind immer noch AVL Bäume (ist dir das bewusst?, das benötigt man ebenfalls, um die IV anwenden zu können). Außerdem hat entweder B_L oder B_R die Tiefe $d$, o.B.d.A : B_L. B_R hat dann (weil B ein AVL Baum ist) mindestens die Tiefe d-1 (aber vielleicht auch die Tiefe d - Mindestens aber d-1).

Wir können also die IV für B_L und B_R anwenden: B_L ist mindestens biz zur Tiefe $\lfloor \frac{d}{2} \rfloor$ befüllt. B_R ist dagegen bis mindestens $\lfloor \frac{d-1}{2} \rfloor$ befüllt (das bekommt man, wenn B_R die Tiefe d-1 hat. Wenn B_R sogar die Tiefe d hat, dann ist B_R aber mindestens bis $\lfloor \frac{d}{2} \rfloor \geq \lfloor \frac{d-1}{2} \rfloor$ befüllt).

Fügen wir nun wieder die Wurzel hinzu, so ist $B_L$ mindestens bis $\lfloor \frac {d-1}{2} \rfloor +1 $ befüllt. Wir wollen also zeigen:
$\lfloor \frac {d-1}{2} \rfloor +1 = \lfloor \frac{d+1}{2} \rfloor$.

Hierfür der Tipp: Schreibe d=2k und setze ein und zeige die Gleichheit.
Dann schreibe d=2k+1 setze wieder ein und zeige die Gleichheit. Hier hattest du schon festgestellt, dass bei d=2k bei $\lfloor \frac{d-1}{2} \rfloor$ die Gaußklammer nicht einfach wegfällt. Das ist auch korrekt, aber man kann das trotzdem ohne Gaußklammer schreiben: $\lfloor \frac{d-1}{2} \rfloor = \lfloor \frac{2k-1}{2} \rfloor = \lfloor  k-\frac{1}{2} \rfloor = \text{Term ohne Gauß Klammer - deine Aufgabe!}$
Falls du hier hängst, setz mal paar Werte für k>0 ein (k ist ganzzahlig).


Viel Erfolg
Creasy





Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
MePep
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 08.05.2020
Mitteilungen: 135
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.10, vom Themenstarter, eingetragen 2020-06-27


Hallo :) !

Also:

Sei d eine gerade Zahl, also d = 2k.

Dann folgt: \(\bigg\lfloor \frac{2k+1}{2} \bigg\rfloor = \bigg\lfloor k + \frac{1}{2} \bigg\rfloor = k\)
Außerdem: \(\bigg\lfloor \frac{2k-1}{2} \bigg\rfloor + 1 = \bigg\lfloor k - \frac{1}{2} \bigg\rfloor + 1 = k - 1 + 1 = k\)
-> Gleichheit!

Sei d eine ungerade Zahl, also d = 2k+1.
Dann folgt: \(\bigg\lfloor \frac{(2k+1)+1}{2} \bigg\rfloor = \bigg\lfloor k + 1 \bigg\rfloor = k + 1\)
Außerdem: \(\bigg\lfloor \frac{(2k+1)-1}{2} \bigg\rfloor + 1 = \bigg\lfloor k \bigg\rfloor + 1 = k + 1\)
-> Gleichheit!


Falls dies stimmen sollte bin ich ganz schön verärgert. Ich dachte nämlich ständig ich hätte irgendwie alles falsch verstanden, das ich konzeptlich nichts gerafft habe. Doch jetzt könnte es tatsächlich einfach daran gelegen haben das ich so eine Elementare Sache wie Runden einfach Formal nicht verstehe oh man 😄😵.

Jedenfalls vielen Dank für deine Geduld und deine Hilfe bisher, das finde ich wirklich toll.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Creasy
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 22.02.2019
Mitteilungen: 547
Aus: Bonn
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.11, eingetragen 2020-06-27


Guten Morgen,

Alles korrekt, aber ärger dich nicht :)

Gerngeschehen - viel Erfolg weiterhin

Creasy



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Kitaktus
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.09.2008
Mitteilungen: 6571
Aus: Niedersachsen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.12, eingetragen 2020-06-27


Wenn es wirklich an der Auswertung der Gaußklammern lag:
Ist n eine ganze Zahl und a eine beliebige reelle Zahl, dann ist stets
[a+n]=[a]+n, egal ob [..] das Abrunden, das Aufrunden oder das Runden zur nächsten ganzen Zahl bezeichnet.
Für die Gleichung [(d-1)/2]+1 = [(d+1)/2] braucht man also eigentlich keine Fallunterscheidung nach d. Hier wird nur die ganze Zahl 1 in die Klammer reingezogen.

In meinem ersten Beitrag schrieb ich, dass man den Induktionsanfang anpassen müsste. Da habe ich wahrscheinlich nicht genau genug gelesen.
Man benötigt für den Schluss auf d+1 die Gültigkeit der IV für d-1 (*) - man macht also immer Doppelschritte bei der Induktion. Daher brauch man auch einen geraden und einen ungeraden Induktionsanfang.
Tatsächlich waren auch zwei Anfänge gegeben.

(*) Etwas natürlicher ist es freilich, in der IV die Gültigkeit für d-1 _und_ d zu fordern (oder wer mag für alle Werte $\leq$d).



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
MePep hat die Antworten auf ihre/seine Frage gesehen.
MePep hat selbst das Ok-Häkchen gesetzt.
Neues Thema [Neues Thema]  Druckversion [Druckversion]

 


Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2020 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]