Binäre Suchbäume mit Algorithmus erweitern?
Hallo liebe Community, ich will einen Algorithmus schreiben, welcher einen binären Suchbaum, mit paarweise verschiedenen Schlüsseln, automatisch erweitert. Stellen wir uns vor wir haben einen Suchbaum, diesen übergeben wir dem Algorithmus und geben ihm dem Namen T. Der Algorithmus hängt an jedes Blatt von T neue Blätter an (so viele wie möglich). Hier ein kleines Beispiel:
wird zu
Ich habe dann erstmal angefangen drauf los zu programmieren und habe auch ein bisschen was hinbekommen. Aber bei mir ist das Problem, dass wenn der Baum größer wird, dass dann kein korrekter Suchbaum mehr rauskommt. Erst habe ich einen Algorithmus geschrieben der für Bäume der Höhe 2 funktioniert, dann für die Höhe 3. Dann habe ich bemerkt, dass das aber nicht für die Höhe 4 funktioniert und dann habe ich mich gefragt ob meine Grundidee vielleicht falsch war.
Meine Idee war ansich folgende: Erstmal habe ich triviale Bäume der Höhe 0 und 1 abgedeckt. Dann kommen wir zum richtigen Algorithmus (erstmal für einen Baum mit der Höhe zwei): Man schaut sich jeden Knoten rekursiv an. Wenn das linke Kind und das rechte Kind vom Knoten beide NULL sind, dann ist der Knoten ein Blatt, nennen wir dieses Blatt y.
Dann gibt es vier Fälle für das Blatt y:
- Das Blatt kann ein linkes Kind im linken Teilbaum sein: Dann muss der Schlüssel des linken Kindes kleiner sein, als der Schlüssel von y. Der Schlüssel vom rechten Blatt muss größer sein als der Schlüssel von y aber kleiner als der Vaterknoten von y.
- Das Blatt kann ein rechtes Kind im linken Teilbaum sein: Dann muss der Schlüssel des linken Kindes kleiner sein, als der Schlüssel von y, aber größer sein als der Vaterknoten von y. Der Schlüssel vom rechten Kind muss größer sein als der Schlüssel von y, aber kleiner als die Wurzel vom Baum.
- Das Blatt kann ein linkes Kind im rechten Teilbaum sein: Dann muss der Schlüssel des linken Kindes kleiner sein, als der Schlüssel von y aber größer als die Wurzel vom Baum. Der Schlüssel vom rechten Kind muss größer sein als der Schlüssel von y, aber kleiner sein als der Vaterknoten von y.
- Das Blattt kann ein rechtes Kind im rechten Teilbaum sein: Dann muss der Schlüssel des linken Kindes kleiner sein als der Schlüssel von y, aber größer als die Wurzel des Baums. Der Schlüssel des rechten Kindes muss größer sein, als der Schlüssel von y.
Mit diesen Bedingungen, kann man dann einen Algorithmus schreiben, der funktioniert. Aber halt nur für Bäume der Höhe 2. Bei einem Baum der Höhe drei hat das dann nicht mehr funktioniert, weil es sozusagen erstmal einen linken und einen rechten Teilbaum gibt und dann davon nochmal jeweils einen linken und rechten. Meine Idee war dann einfach ob, man sich in einem rechten Teilbaum befindet oder in einem linken, aber das hat nicht geklappt. Vielleicht kann mir ja jemand eine Grundidee geben, weil meine Idee anscheinend nicht richtig funktioniert. Das implementieren mache ich selber.
1 Antwort
Der Zweck der Übung wird nicht so wirklich klar.
An Deinem Beispiel (graphisch) wird nicht klar, warum ausgerechnet diese Blätter hinzugefügt werden.
Welchem Zweck also dient die Erweiterung?
Naja, bei einem Suchbaum fügt man ja ansich Schlüssel hinzu, die dann an einem geeigneten Ort landen.
Bei einem binären Suchbaum wird das ein Blatt sein.
Soweit so klar.
Dadurch "degeneriert" der Baum - will man dies nicht und soll er weiterhin ausgewichtet sein, muß er eben 'repariert' werden, indem man Rotationen ausführt.
Quasi nach Schlüssel zu suchen, die man an einer bestimmten Stelel als Blatt anhängen kann, ist irgendwie 'eigenartig'.
Aber um zur Frage zurückzukommen, Wann immer Du links absteigst, wird der aktuelle Schlüssel Dein Upper Bound, wenn Du rechts absteigst, Dein Lower Bound. Kommst Du an einem Blatt an, kannst Du ein linkes Kind zwischen Lower Bound und aktuellem Blattschlüssel erzeugen, ein rechtes zwischen Blatt udn Upper Bound.
Kommst Du damit weiter?
Ja das hilft mir wirklich sehr, weiter ich werde jetzt erstmal probieren mit diesem Ansatz weiter zu arbeiten.
Okay ich habe jetzt einen Algorithms dazu entworfen der auch funktioniert. Ich habe erst ein paar Probleme gehabt mit der Startinitialisierung, aber zu Beginn sollte doch lowerBound = 0 sein und upperBound = unendlich (bzw. in der Implementierung dann der maximale Wert für den Datentyp z.B. Integer), oder? Damit funktioniert es auf jeden Fall.
Bei numerischen Werten würdest Du natürlich (formal) ansich mit -Inf und + Inf (Unendlich) starten, in der Praxis orientierst Du Dich natürlich am zulässigen Wertebereich.
Es ist halt einfach eine Übung um das Verständnis zu verbessern. Einen wirklich praktischen Zweck gibt es da nicht. Man hat einfach einen Baum T gegeben und dann soll man einen Algorithmus entwickeln, der an die Blätter vom Baum T weiter Blätter anhängt. Nach dem Anhängen soll es sich halt immer noch um einen binären Suchbaum handeln. Einen Zweck gibt es da nicht. Typische Schulaufgabe halt: Es gibt keine praktische Relevanz.
Ich verstehe aber nicht warum dir nicht klar ist warum ausgerechnet diese Blätter hinzugefügt wurden. Es handelt sich ja um einen Suchbaum. Als linkes Kind von der zwei braucht man etwas das kleiner ist als zwei. Das ist dann halt nur die 1. Als rechtes Kind von der zwei braucht man einen Schlüssel der größer ist als zwei aber kleiner als 4. Das ist halt nunmal nur die drei. Als linkes Kind von der 6 brauchen wir wieder einen Schlüssel der kleiner ist als 6 aber größer als 4, da gibt es nur die 5. als rechtes Kind von der 6 brauchen wir einen Schlüssel der größer ist als 6 aber kleiner als 8, das ist dann nur die 7. Die 9 braucht als linkes Kind einen Schlüssel der kleiner ist als 9 aber größer als 8. Das wäre 10, aber 10 ist schon Vaterknoten von 9, deswegen kann es kein linkes Kind geben. Als rechtes Kind von der 9 brauchen wir etwas das größer ist als 9 aber kleiner als 10, es gibt keine natürliche Zahl die diese Bedingung erfüllt, also wird kein Blatt angehangen. Bei der 11 brauchen wir als linkes Kind etwas das kleiner ist als 11 aber größer als 10. Da gibt es nicht. Als rechtes Kind von der 11 könnnen wir jedes x Element R nehmen für das gilt, dass x > 11. Der Algorithmus wählt dann einfach eine Zahl die diese Bedingung erfüllt. Es ist also durchaus klar definiert (durch die Eigenschaften eines Suchbaums) welche Schlüsselwerte genommen werden müssen.