binärer suchbaum: nächst grössers und nächts kleiners element finden

p0llux

Ich habe eine Binären Suchbaum, der soweit funktioniert.
Wenn die Suchfunktion einen Wert nicht findet, soll nun der nächts grössere und nächst kleinere Wert zurückgegeben werden.

Der Knoten, an dem die Suchfunktion 0 zurückgibt, ist ja gerade das nächst grössere Element, wenn der gesuchte Wert kleiner ist als der Knoten und das nächst kleinere Element, falls der Wert grösser wird.

Aber wie kann ich nun noch den kleineren, bzw. grösseren Wert finden? Irgendwie konnte ich da keine Gesetzmässigkeit finden.

Gruss p0llux

ronny

ich würde dir empfehlen einen baum aufzuzeichnen und dann einfach mal das zum nächst größeren/kleineren gehen durchprobieren
du solltest recht schnell feststellen wie der algo funktioniert

p0llux

Nun, das habe ich schon gemacht und auch bei einem weiteren Verusch konnte ich keinen Algo finden.

Kannst du mir nicht einen Tip geben?

ConfusedGuy

also das nächst größere element ist in deinem rechten teilbaum das am weitesten links liegende element.

das nächst kleinere element ist das im linken teilbaum am weitesten rechts liegende.

und das ist die gesetzmäßigkeit: suchst du das größte element gehe ganz rechts im baum runter, suchste das kleinste dann gehe ganz links im teilbaum runter.

eigent sich hervoragend für rekursion..

p0llux

Das sehe ich nicht ganz, hier ein Beispielbaum:

http://www.cosc.canterbury.ac.nz/research/RG/alg/bst.gif

Wenn ich nach 62 suche, dann wäre ja das nächst grössere Element 66 und das nächst kleinere 51.

Aber im linken Teilbaum am weitesten rechts ist ja 37 und im rechten Teilbaum am weitesten Links ist 40. Das stimmt so dann nicht.

Apollon

Es gibt keinen. Das Aussehen des Baumes haengt von der Einfuegereihenfolge der Schluessel ab. Spaetestens an dieser Stelle sollte klar sein, dass es so einen Algorithmus nicht geben kann.

EDIT: Aber eine Moeglichkeit waere, den Baum inorder zu traversieren, das letzte Element behalten bis ein Element > gesuchter Schluessel auftritt. Dann ist das aktuelle Element das naechstgroessere und das letzte das naechstkleinere.

Jester

Man könnte auch jedem Knoten noch in eine Liste aufnehmen bzw. einen next/previous-Zeiger verpassen, sozusagen alle Knoten auf eine Schnur auffädeln. Du mußte nur beim Einfügen/Löschen halt das ganze updaten:

- Einfügen: Zunächst suchen, damit findest Du den nächstgrößeren/nächstkleineren, Du weißt also wo Du Dich in die Liste einhängen mußt.

- Entfernen: Knoten einfach aus der Liste rausnehmen.

Damit lässt sich das ganze nach der fehlgeschlagenen Suche dann in konstanter Zeit realisieren, indem man sich noch einen der Nachbarn des Knoten an der die Suche endete anschaut.

ConfusedGuy

naja, doch.
ich weiß ja nicht wie dein algo zum suchen eines eintrags aussieht aber im wesentlich ist es(pseudocode):

search( baum ){
    if( aktueller knoten == gesuchter eintrag ){ 
        return aktuellen knoten;
        }
    else{
        if( aktueller knoten < gesuchter eintrag ){
            search( rechter teilbaum );
            }
        else{
            search( linker teilbaum );
            }
    }
}

wobei auch noch der fall, das die zahl nicht im baum ist berückstichtigt werden muss

edit. jetzt verstehe ich erst richtig..ist nen bißchen trickreicher, den nächst kleineren oder nächst größeren zu finden..
ich antworte dir wenn ich mehr zeit habe..vermutlich morgen oder heute nacht, dann aber betrunken

life

Apollon schrieb:

Es gibt keinen. Das Aussehen des Baumes haengt von der Einfuegereihenfolge der Schluessel ab. Spaetestens an dieser Stelle sollte klar sein, dass es so einen Algorithmus nicht geben kann.

Totaler Blödsinn. Erstmal gibt es einen offensichtlichen Algorithmus, der einfach alle Knoten durchgeht. Also ist deine Aussage schonmal falsch.
Weiter gibt es aber auch einen Algorithmus mit Laufzeit linear zur Baumhöhe. Dazu siehe z.B. hier: http://wwwcs.uni-paderborn.de/cs/ag-monien/LEHRE/SS06/DuA/15.pdf

Apollon

life schrieb:

Apollon schrieb:

Es gibt keinen. Das Aussehen des Baumes haengt von der Einfuegereihenfolge der Schluessel ab. Spaetestens an dieser Stelle sollte klar sein, dass es so einen Algorithmus nicht geben kann.

Totaler Blödsinn. Erstmal gibt es einen offensichtlichen Algorithmus, der einfach alle Knoten durchgeht. Also ist deine Aussage schonmal falsch.
Weiter gibt es aber auch einen Algorithmus mit Laufzeit linear zur Baumhöhe. Dazu siehe z.B. hier: http://wwwcs.uni-paderborn.de/cs/ag-monien/LEHRE/SS06/DuA/15.pdf

Threadsteller konnte keine Gesetzmaessigkeit finden, die ihm vom Knoten, an dem seine Suche endete, erlaubt das naechstkleinere Element zu finden. Ich sehe keine Moeglichkeit. Falls Du eine Loesung dafuer hast, dann teile sie uns mit. Im verlinktem Skript steht dazu nichts. Weare interessant.

Die Trivialloesung habe ich im selben Beitrag, den Du zitiert hast hingeschrieben. Aber das hast Du nicht mitzitiert.

SG1

Apollon schrieb:

life schrieb:

http://wwwcs.uni-paderborn.de/cs/ag-monien/LEHRE/SS06/DuA/15.pdf

Threadsteller konnte keine Gesetzmaessigkeit finden, die ihm vom Knoten, an dem seine Suche endete, erlaubt das naechstkleinere Element zu finden. Ich sehe keine Moeglichkeit. Falls Du eine Loesung dafuer hast, dann teile sie uns mit. Im verlinktem Skript steht dazu nichts. Weare interessant.

13.4

life

Apollon schrieb:

life schrieb:

Apollon schrieb:

Es gibt keinen. Das Aussehen des Baumes haengt von der Einfuegereihenfolge der Schluessel ab. Spaetestens an dieser Stelle sollte klar sein, dass es so einen Algorithmus nicht geben kann.

Totaler Blödsinn. Erstmal gibt es einen offensichtlichen Algorithmus, der einfach alle Knoten durchgeht. Also ist deine Aussage schonmal falsch.
Weiter gibt es aber auch einen Algorithmus mit Laufzeit linear zur Baumhöhe. Dazu siehe z.B. hier: http://wwwcs.uni-paderborn.de/cs/ag-monien/LEHRE/SS06/DuA/15.pdf

Threadsteller konnte keine Gesetzmaessigkeit finden, die ihm vom Knoten, an dem seine Suche endete, erlaubt das naechstkleinere Element zu finden. Ich sehe keine Moeglichkeit. Falls Du eine Loesung dafuer hast, dann teile sie uns mit. Im verlinktem Skript steht dazu nichts. Weare interessant.

Im Link steht, wie es für das nächstgrößere Element funktioniert. Nächstkleinere sollte dann analog gehen.

Übrigens ist es ein ziemlicher Unterschied, ob man sagt "Ich sehe keine Lösung" oder ob man sagt "Es kann offensichtlich keine Lösung existieren".

Apollon

Ok. Ok. Ich gebe mich geschlagen. Bin im Unrecht.

p0llux

Danke, das in dem Skrip sollte weiterhelfen. Ich habe es jetzt noch nicht genauer angesehen, aber das ist scho was ich suche.

p0llux