Suchen in einen Rot-Schwarz Suchbaum

Die Suche in einem Rot-Schwarz Suchbaum ist gleich der Suche in einem binaeren Suchbaum.

Jede Suche in einem binaeren Suchbaum terminiert entweder an einem internen Knoten, wenn der gesuchte Schluessel gefunden wurde, oder an einem externen Knoten, wobei die Suche nicht erfolgreich war.

Vorraussetzungen fuer die hier vorliegende Implementierung:

T sei ein binaerer Baum, der die binaere Suchbedingung erfuellt.

Die Anzahl der Knoten in T sei endlich.

K sei der gesuchte Schluessel. Fuer die hier zugrunde liegende Implementierung ist wichtig, dass der Schluessel nicht ,,0'' ist. Diese Einschraenkung geht ausschliesslich aus der Implementierung hervor und nicht aus dem Algorithmus an sich.

Dann gilt es folgende Faelle zu betrachten:

1. T ist der leere Baum -> K ist nicht in T enthalten und der Algorithmus terminiert nicht erfolgreich
2. T ist nicht der leere Baum.

• ist K kleiner als der Schluesselwert der Wurzel von T, so wird T durch den linken Unterbaum von T ersetzt und die Suche wiederholt
• K ist gleich dem Schluesselwert der Wurzel von T, dann ist der Schluessel K in dem binaeren Suchbaum enthalten und der Algorithmus terminiert erfolgreich
• ist K groesser als der Schluesselwert der Wurzel von T, so wir T durch den rechten Unterbaum von T ersetzt und die Suche wiederholt

Die Suche beginnt bei der Wurzel des Baumes T. Ist der gesuchte Schluesselwert kleiner als der der Wurzel von T, so befindet er sich, wenn er ueberhaupt in T enthalten ist, in dem linken Unterbaum der Wurzel von T. Der linke Unterbaum von T besitzt weniger Knoten als T. Da die Datenstruktur Baum rekursiv beschrieben ist, koennen wir den auf T angewandten Algorithmus auch auf den linken Unterbaum von T anwenden. Analoges gilt fuer den rechten Unterbaum von T. Ist der gesuchte Schluessel groesser als der Schluessel der Wurzel von T, so ist er, insofern er in T enthalten ist, in dem rechten Unterbaum und wir koennen den Algorithmus auf den rechten Unterbaum anwenden.

Ist der Schluessel der Wurzel von T gleich dem gesuchten Schluessel, so terminiert der Algorithmus. Bei jedem Durchlauf der Schleife wird T durch einen Unterbaum von der Wurzel von T ersetzt. Damit verringert sich bei jedem Durchlauf der Schleife die Hoehe von T um den Wert ``1''. Sei h die Hoehe von T. Da die Datenstruktur ``Baum'' auf eine endliche Anzahl von Knoten definiert ist, ist h endlich. Ist h=0 (T ist der leere Baum), terminiert der Algorithmus. Da man eine natuerliche Zahl nicht unendlich oft verringern kann, terminiert der Algorithmus.

Da die Hoehe bei einem Schleifendurchlauf stets um den Wert ``1'' verringert wird, laesst sich aussagen, dass die Zeit, die zum Finden eines Elementes eines binaeren Baums der Hoehe h benoetigt wird, ist. Fuer einen Rot-Schwarz Baum gilt laut Satz 1 des Kapitels 2.3.1, dass die benoetigte Zeit zum Auffinden eines Elementes in einem Rot-Schwarz Baum mit n Knoten ist.

    PUBLIC INT FIND(INT KEY) {

        RBELEMENT CURRENT=ROOT;                 // BEGINNEN BEI DER WURZEL VON T.

        WHILE (CURRENT!=NIL) {                  // UEBERPRUEFEN, OB T DER LEERE BAUM

                                                // IST. FALLS T LEER IST, TERMINIERE.

            IF (KEY==CURRENT.SEARCHKEY) {       // WENN DER SUCHSCHLUESSEL DER

                                                // WURZEL VON T GLEICH DEM 

                                                // GESUCHTEN SCHLUESSEL IST,

                RETURN KEY;                     // TERMINIERE ERFOLGREICH UND

                                                // LIEFERE DEN SCHLUESSEL ZURUECK.

            } ELSE {                            // SONST

                IF (KEY<CURRENT.SEARCHKEY)      // WENN DER GESUCHTE SCHLUESSEL 

                                                // KLEINER IST

                    CURRENT=CURRENT.LEFT;       // ERSETZE T DURCH DEN LINKEN

                                                // UNTERBAUM

                ELSE                            // WENN DER GESUCHTE SCHLUESSEL

                                                // GROESSER IST,

                    CURRENT=CURRENT.RIGHT;      // ERSETZE T DURCH DEN RECHTEN

                                                // UNTERBAUM.

            }

        }

        RETURN 0;                               // FALLS T DER LEERE BAUM IST,

                                                // TERMINIERE NICHT ERFOLGREICH

                                                // UND LIEFERE "0" ZURUECK.

    }