Binaere Suchbäume < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 02:28 Di 11.01.2005 | | Autor: | Rusty |
Hallo Leute!
Soll diese beiden Aufgabe zu binaeren Suchbaeumen loesen - hab leider keinen blassen schimmer wie das zu machen ist.
Ein InformatIker glaubt eine bedeutende Eigenschaft bei binären Suchbäumen gefunden zu haben. Er behauptet, wenn die Suche nach dem Schlüssel k in einem Blatt endet, und man die folgenden drei Mengen definiert
1. X2 = alle Knoten der Suchsequenz zu k
2. X1 = alle Knoten, die links von der Suchsequenz liegen sowie
3. X3 = alle Knoten, die rechts von der Suchsequenz liegen,
dann gilt x1 [mm] \le [/mm] x2 [mm] \le [/mm] x3 für alle x1 [mm] \in [/mm] X1, x2 [mm] \in [/mm] X2 und x3 [mm] \in [/mm] X3.
Zeigen Sie durch ein möglichst kleines Gegenbeispiel, dass diese Behauptung falsch ist. Um entartete Fälle zu vermeiden sollten X1, X2, und X3 nicht leer sein.
Nehmen wir an, dass die Zahlen 1 bis 1000 in einem binären Suchbaum abgelegt sind. Wir wollen die Zahl 363 finden. Welche der folgenden Suchsequenzen kann nicht als Folge der Knoten, die abgefragt wurden, aufgetreten sein?
a) 2, 252, 401, 398, 330, 344, 397, 363
b) 924, 220, 911, 244, 898, 258, 362, 363
c) 925, 202, 911, 240, 912, 245, 363
d) 2, 399, 387, 219, 266, 382, 381, 278, 363
e) 935, 278, 347, 621, 299, 392, 358, 363
Gruss Rusty
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 14:12 Di 11.01.2005 | | Autor: | Lizard |
Also, bei der ersten Aufgabe habe ich auch relativ lange überlegen müssen, bis mir ein Gegenbeispiel eingefallen ist - eigentlich ist es aber ziemlich einfach, wenn man erstmal drauf gekommen ist.
Das Schlüsselwort in der Aufgabenstellung ist hier das "alle" in "für alle x1, ...". Schau dir mal an, was du alles so für Zahlen durchläufst, wenn du nach einer bestimmten Zahl suchst. Nimm vielleicht an, die gesuchte Zahl wäre das Blatt, das rechts außen steht, und schau, ob die Zahlen links von der Suche wirklich alle die gewünschte Eigenschaft erfüllen (bei den meisten Bäumen tun sie es, aber bei manchen eben auch nicht).
Mein Minimalbeispiel hat 4 Knoten, ist allerdings leicht degeneriert. Um das zu vermeiden, benötige ich 6 Knoten, aber womöglich geht das auch mit 5... müsste man sich mal genauer anschauen. Sorry daß ich da nicht mehr zu sagen kann, aber es ist halt eine Denkaufgabe, bei der du allein auf die Lösung kommen solltest. Wenn sich allerdings noch Verständnisprobleme bei der Aufgabenstellung ergeben sollten, melde dich ruhig noch einmal.
Die zweite Aufgabe ist dagegen recht einfach: Du musst dir einfach vorstellen, daß du in der Suchsequenz einen binären Suchbaum durchläufst, und zeichnest dabei den Unterbaum mit den Zahlen auf, die gegeben sind (d.h. diejenigen, auf die während der Suche stößt). Das bedeutet also: Die erste Zahl in der Kette ist die Wurzel. Die zweite Zahl ist das linke Kind der Wurzel, wenn sie kleiner ist als die erste, oder das rechte Kind der Wurzel, wenn sie größer ist. Die dritte Zahl ist dann das Kind dieser Zahl, und so weiter.
Am Ende hast du einen Baum auf dem Blatt, den du jetzt einfach auf die binäre Suchbaumeigenschaft überprüfen musst: Sind alle Zahlen im rechten Unterbaum einer jeden Zahl größer als diese Zahl, und sind alle Zahlen im linken Unterbaum einer jeden Zahl kleiner als diese Zahl? Falls ja, ist der Baum in Ordnung, falls nicht, kannst du die Sequenz ausschließen - sie hätte mit einer binären Suche nicht gebildet werden können, da sie ja nicht aus einem binären Suchbaum stammen darf. Ich hoffe, das ist so relativ klar, falls nicht, melde dich nochmal.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 16:15 Mi 12.01.2005 | | Autor: | Rusty |
Hey Lizard!
Danke schon mal fuer deine Antwort. Das mit den Suchsequenzen ist echt easy. Sitzt gerade dran und bearbeite das. Bei der anderen Sache bin ich noch am ueberlegen. Melde mich evtl. spaeter nochmal.
Gruß Rusty
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 17:01 Mi 12.01.2005 | | Autor: | Lizard |
Das klingt doch schonmal sehr gut!
Bei der anderen Aufgabe hilft dir vielleicht noch die Information, daß mein (degeneriertes) Beispiel die folgende Form hat:
[mm] $x_1$
[/mm]
[mm] \backslash
[/mm]
[mm] $x_2$
[/mm]
[mm] $/$\backslash
[/mm]
[mm] $x_3$ $x_4$
[/mm]
Relevant wird der Vergleich von [mm] $x_1$ [/mm] und [mm] $x_3$. [/mm] Damit hab ich zwar eigentlich schon fast zuviel verraten, aber Hauptsache ist ja, daß du dich auch mal damit beschäftigt hast, und verstehst, warum das so ist, wie es ist :)
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 21:04 Mi 12.01.2005 | | Autor: | Rusty |
Hey Lizard!
War wohl mit "ist ja easy" einwenig voreilig :-(
Versuche jetzt schon seit Stunden diese beiden bloeden Aufgaben zu loesen aber der Groschen viel einfach nicht fallen.
Den Aufbau eines Binaeren Baums habe ich wohl verstanden.
Ich werde nun erstmal fuer 1. den dargestellten Weg aufzeichnen, denn bei den gegebenen Zahlen handelt es sich ja wohl um den Suchweg in eben einem solchen Baum.
(da die darstellung hier etwas muesig ist werde ich einfach die zahlen in einer
Reihe schreiben und mit r(rechts) und l(links) angeben wo sie nach jedem Knoten liegen.
2(wurzel), 252(r), 401(r), 398(l), 330(l), 344(r), 397(r),363(l)
363 ist das Blatt alle anderen Zahlen zwischen 2 u. 363 sind innere Knoten die
in einen binaeren Baum ja max. 2 Nachkommen haben duerfen.
Wie soll ich denn nun bitte sagen koennen ob der dargestellte weg richtig sein kann oder nicht?
Bei der anderen Aufgabe bin ich, obwohl du mir die Lsg. wohl ja schon quasie auf einem Silbertabblet serviert hast auch noch nicht weiter.
Vielleicht hast du ja Lust mir das nochmal zu erklaeren.
Im uebrigen bin ich nicht in diesem Forum um mir von irgend jemanden die Aufgaben loesen zu lassen weil ich selber zu faul bin. Spaetestens inder Klausur schlaegt man dann wohl recht Hard auf  !
Danke schon mal im voraus.
Gruß Rusty
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 01:32 Do 13.01.2005 | | Autor: | Lizard |
Hi,
ja, es kommt schon ganz gut durch, daß du dir schon Gedanken machst... ansonsten hätte die ganze Sache ja auch wenig Sinn :)
Also, der Aufbau eines binären Baums ist dir prinzipiell klar, die Schwierigkeit besteht wohl darin, das ganze in der Praxis umzusetzen. Ist am Anfang auch recht verwirrend, am besten, du behältst im Kopf, wozu man sich den Aufwand eigentlich macht. Das tolle am binären Suchbaum ist nämlich, wie der Name ja schon sagt, daß man sehr schnell herausfinden kann, ob eine bestimmte Zahl darin enthalten ist, oder auch nicht - einfach durch das rekursive Absteigen, jeweils nach links oder rechts. Man muss nie wieder zurück und schauen, ob eine andere Abzweigung nicht vielleicht besser gewesen wäre, weil das die wichtigste Eigenschaft der Suchbäume garantiert: nämlich, daß alles rechts von einer beliebigen Marke größer als diese Marke ist, und alles links davon kleiner (Gleichheit dabei mal ausgeschlossen, lässt man aber auch manchmal zu). Das bedeutet also folgendes: An einer beliebigen Stelle im Baum kann man sich eine Zahl merken, und wenn man sich irgendeinen Nachfolger zu ihrer Rechten sucht, so muss der immer größer sein als diese Zahl; sucht man zu ihrer Linken, stößt man ausschließlich auf kleinere Zahlen.
Wie ist das jetzt für dein Problem relevant? Nun ja, folgendes: Was du dir da aufgemalt hast (übrigens bereits richtig), ist ein Teil eines wahrscheinlich größeren binären Suchbaums, oder zumindest wird das gefordert. Für diesen Teil muss die genannte Eigenschaft natürlich auch gelten... und damit hast du eigentlich das Ausschlusskriterium: Kannst du diese Eigenschaft überall nachweisen, ist die Suchsequenz in Ordnung, findest du ein Gegenbeispiel, ist sie es nicht.
Ich konstruiere mal ein einfaches Beispiel: Wir untersuchen die Sequenz 5, 4, 3, 2, 1. Kann sie erzeugt werden? Offensichtlich ja, man steigt immer nach links ab. Wie ist es mit 5, 4, 2, 3? Auch das funktioniert wohl, man steigt dreimal links ab und einmal rechts. Was passiert bei der Sequenz 5, 4, 2, 6? Hier ergibt sich nun ein Problem: Wir sind bei der 5 nach links abgestiegen, und die Eigenschaft sollte uns jetzt eigentlich garantieren, daß alle Zahlen, auf die wir treffen werden, kleiner als 5 sind. Dann hätte die 6 aber nicht mehr auftreten dürfen (welche übrigens ebenfalls einen Widerspruch zu "kleiner als 4" darstellt, jedoch keinen Widerspruch zu "größer als 2", denn das ist sie ja). Diese Sequenz ist also ungültig!
Ich gebe zu, daß die von dir genannten Aufgaben (übrigens allesamt aus dem Cormen, sehr empfehlenswertes Buch für solche Sachen [Cormen, Leiserson, Rivest, Stein: Introduction to Algorithms, 2nd edition]) etwas komplexer sind als meine Beispiele, aber das Grundschema bleibt sich gleich. Melde dich trotzdem, wenn du noch irgendwelche Probleme hast.
Zu der ersten Aufgabe sage ich erstmal nichts weiter, versuche einfach nochmal, einen Baum zu konstruieren, der zwar an sich korrekt ist, aber bei dem die zitierte Eigenschaft nicht gilt (also beispielsweise [mm] $x_3 [/mm] > [mm] x_1$ [/mm] obwohl [mm] $x_1$ [/mm] auf dem Suchpfad liegt und [mm] $x_3$ [/mm] links davon). Viel Erfolg!
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 14:34 Do 13.01.2005 | | Autor: | Rusty |
Hey Lizard!
Vielen Dank fuer die ausfuehrliche Erklaerung!. Schon sehr merkwuerdig das ich hier mehr Hilfe bekomme als von den Leuten die in der Uni bei uns dafuer bezahlt werden - und das sogar noch zu so spaeter Stunde. Habe jetzt erstmal die Suchsequenzaufgabe geloest. Wirf doch bitte mal einen Blick drauf ob ich das Korrekt umgesetzt habe.
Suchsequenz a: in Ordnung da: erster Abstieg rechts --> alle folgenden Zahlen > 2 = true
Suchsequenz b: in Ordnung da: erster Abstieg links --> alle folgenden Zahlen < 924 = true
Suchsequenz c: in Ordnung da: erster Abstieg links --> alle folgenden Zahlen< 925 = true
Suchsequenz d: in Ordnung da: erster Abstieg rechts --> alle folgenden Zahlen > 2 = true
Suchsequenz e: in Ordnung da: erster Abstieg links --> alle folgenden Zahlen < 935 = true
fuer die andere Versuch ich jetzt mal ein Bsp. zu generieren welches die genannten Bedingungen schlaegt.
Gruß Rusty !
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 15:29 Do 13.01.2005 | | Autor: | Lizard |
*g* Da kam ich grad wieder nach Hause und wollte noch was sinnvolles machen, aber für meinen derzeitigen Stoff fehlte mir irgendwie der Nerv. Da ist so ein bißchen was aus den unteren Semestern genau das richtige :)
Bei den Sequenzen musst du leider nochmal etwas genauer hinschauen: Den ersten Abstieg zu überprüfen reicht nicht aus, jeder einzelne Unterzweig will noch einmal gesondert untersucht werden! Erinnere dich daran, daß die Suchbaumeigenschaft für beliebige Unterbäume gelten muss, d.h. man muss z.B. die Wurzel oben wegschneiden können, und dann immer noch zwei vernünftige Suchbäume da stehen haben. Bei denen musst du dann auch wieder die Wurzel entfernen dürfen, und so weiter. Macht auch nur Sinn, denn beim Absteigen ist dir ja nicht schon nach dem ersten Knoten egal, ob die Eigenschaft weiter gewahrt bleibt oder nicht; du willst schon, daß du dich jederzeit drauf verlassen kannst ;)
Konkretes Problem z.B. bei Sequenz 3: 911 nach 240 gibt Abstieg nach links, aber die nächste Zahl ist 912, d.h. größer als 911 - dürfte also nicht vorkommen. Ich hab aber so ein Gefühl, daß du die nächste Lösung richtig hinbekommst, also frohes Schaffen noch weiterhin...
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 17:20 Do 13.01.2005 | | Autor: | Rusty |
Ja, ja manchmal hat man echt nen Brett .......
So nun aber hoffentlich  !
A: war in ordnung;
b: auch in Ordnung;
c: geht nicht da von 911 nach links dann 240 von da nach rechts zu 912 kommt in Konflikt mit 911 da ja nur noch kleinere zahlen folgen sollten.
d: geht nicht da 387 im Konflikt zur 2 da von der Wurzel nach links abgebogen wurde
e: geht auch nicht da 299 im Konflikt mit 347--> ist kleiner - es duerfen aber nur groessere folgen.
Die andere kapier ich immer noch nicht. Fang hier langsam an die Waende hochzusteigen - das kann doch nicht so schwer sein :-(.
Also habe mal folgende einfachen Baum konstruiert.
5
/
3
/ [mm] \backslash
[/mm]
2 4
/
1
So:
X2 = alle Knoten der Suchsequenz zu K - also Zahlen 3 u.2 zur 1 od. 3 zur 4
X1 = alle Knoten die Links von der Suchsequenz liegen - bei 4 - 3,2,1 (?)
X3 = alle Knotem die rechts von der Suchsequenz liegen - bei 1 - nur 4 (?)
(4 und 1 sind doch eigentlich Blätter - muss man Sie nun mit zaehlen oder nicht?)
und nun soll gelten x1 [mm] \le [/mm] x2 [mm] \le [/mm] x3
Wenn ich das richtig interpretiert habe dann stimmt das wohl fuer den Fall.
ein anderer Baum:
4
[mm] \backslash
[/mm]
9
/ [mm] \backslash
[/mm]
6 12
/ [mm] \backslash
[/mm]
5 7
X2 = 9, 6 zur 5; 9, 6 zur 7 und 9 zu 12
X1 = 5 keine, bei 7 - 9, 6, (5) bei 12 - 9, (6), (5)
X3 = ........
Irgendwie glaub ich das in meinem Bsp. hier der Wurm drin ist drum lass ich das erstmal so.
Gruß Rusty
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 18:10 Do 13.01.2005 | | Autor: | Lizard |
> A: war in ordnung;
Jo.
> b: auch in Ordnung;
Jo.
> c: geht nicht da von 911 nach links dann 240 von da nach
> rechts zu 912 kommt in Konflikt mit 911 da ja nur noch
> kleinere zahlen folgen sollten.
Jo.
> d: geht nicht da 387 im Konflikt zur 2 da von der Wurzel
> nach links abgebogen wurde
Nein: 2 ist die Wurzel, und da danach 387 folgt, wird nach rechts abgebogen. Besser nochmal anschauen!
> e: geht auch nicht da 299 im Konflikt mit 347--> ist
> kleiner - es duerfen aber nur groessere folgen.
Jo.
> Die andere kapier ich immer noch nicht. [...]
Ist gar nicht so schwer. Wir nehmen mal deinen Baum:
> 5
> /
> 3
> / [mm]\backslash[/mm]
> 2 4
> /
> 1
1 und 4 sind Blätter. Wir bilden mal die Mengen X1 bis X3: X2 ist ja erstmal der "Suchpfad" bis zu einem beliebigen Blatt: Ich wähle mir die 4. Welche Knoten sehen wir auf dem Weg dorthin? Das sind 5, 3, 4, und somit ist X2 = 5, 3, 4. Welche Knoten liegen links von dem Pfad? Das sind offensichtlich 2 und 1, also: X1 = 2, 1. Jetzt noch X3: Welche Knoten liegen rechts von dem Pfad? Keine, dein Beispiel ist also degeneriert, da X3 leer ist. Macht aber nix.
Jetzt überprüfen wir die Eigenschaft: Ist jedes Element von X1 kleiner als jedes Element von X2? In der Tat ist dies der Fall, 1 ist kleiner als jeweils 5, 3 oder 4, und auch 2 ist kleiner als 5, 3 oder 4.
Schön, bislang keine Probleme. Nehmen wir also mal die Suche nach der 1: Der Suchpfad und mithin X2 ist dann 5, 3, 2, 1. X1 ist leer, und X3 besteht wohl nur aus 4. Wieder die Überprüfung: Ist jedes Element aus X2 kleiner als jedes Element aus X3?
Hier stoßen wir auf ein Problem: Die 5 ist größer als die 4, die geforderte Eigenschaft gilt also nicht! Du hast also tatsächlich bereits ein Gegenbeispiel gefunden, wenn es auch degeneriert ist. Du kannst dir ja jetzt mal überlegen, wie du es noch kleiner bekommen kannst, und wie du es schaffst, daß weder X1 noch X3 leer sind. Wenn du das gemacht hast, bist du eigentlich schon fertig :)
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 18:47 Do 13.01.2005 | | Autor: | Rusty |
Man das war ja echt ne schwere Geburt.
Finde ich echt Klasse das du nicht die Nerven verloren hast !
Denke jetzt hab ich et wohl kappiert.
Gruß Rusty
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 19:01 Do 13.01.2005 | | Autor: | Lizard |
Och jo, jeder fängt ja mal irgendwann an, mich freut, wenn ich helfen konnte :) Ist auch nicht tragisch, wenn man mal was nicht auf Anhieb versteht, einfach dranbleiben, das kommt schon mit der Zeit. Sehr gut, wenn du es jetzt drauf hast! Binäre Suchbäume sind ein wichtiges Hilfsmittel für alles mögliche (Programmieren wie Beweise), und auf Baumstrukturen trifft man eigentlich immer wieder: freu dich jetzt schon auf Heaps, das nächste Thema, das nicht so ganz trivial ist... Naja gut, wenn sich Probleme ergeben, weißt du ja, wo du hinkommen kannst. Bis dahin, viel Spaß noch!
|
|
|
|
