{ ------------------------------------------------------------------------------------------------------------------- }
{                                                                                                                     }
{ Die Unit stellt einen inhaltslosen Datentypen TSuchBaum zur Verfügung. Um einen Suchbaum mit Inhalt zu erhalten,    }
{ muss eine hiervon abgeleitete Klasse erstellt werden, z. B.:                                                        }
{                                                                                                                     }
{  type TIntSuchbaum = class(TSuchbaum)                                                                               }
{         public                                                                                                      }
{           content: integer;                                                                                         }
{           constructor Create (content: Integer);                                                                    }
{           function isEqualTo (which: TSuchbaum): boolean; override;                                                 }
{           function isBiggerThan (which: TSuchbaum): boolean; override;                                              }
{           function contentToString: string; override;                                                               }
{       end;                                                                                                          }
{                                                                                                                     }
{  Die Routinen isEqualTo (gleich) und isBiggerThan (größer) dienen zur Einsortierung in den Suchbaum.                }
{                                                                                                                     }
{ -------------------------------------------------------------------------- Tool zum Suchbaum ---------------------- }

unit Suchbaum;

interface

uses ExtCtrls, Binbaum;

type TSuchBaum=class(TBinBaum)
      private
       function cutOutBiggest (var biggest: TSuchbaum): TSuchbaum;
         { Liefert den SuchBaum ohne das größte Element. Dieses steht abgekapselt in biggest                          }
       function deleteIt: TSuchbaum;
         { Liefert den neuen Suchbaum ohne das zuvor existierende (!!!) Suchelement                                   }

      protected
         { müssen für einen neuen Suchbaum-Typen definiert werden                                                     }
       function isEqualTo (which: TSuchbaum): boolean; virtual; abstract;
       function isBiggerThan (which: TSuchbaum): boolean; virtual; abstract;
         { werden aus den beiden oberen Funktionen abgeleitet                                                         }

      public
       function insert(which: TSuchbaum; var ok: boolean): TSuchbaum;
         { Liefert den neuen SuchBaum mit dem eingefügten Suchelement                                                 }
       function delete (which: TSuchbaum; var ok: boolean): TSuchbaum;
         { Liefert den neuen Suchbaum ohne das eventuell vorhandene Suchelement                                       }
         { war es nicht vorhanden => Existiert = false                                                                }

     end;

implementation

function TSuchbaum.insert (which: TSuchbaum; var ok: boolean): TSuchbaum;
var tb: TSuchBaum;
begin 
  if isEmpty                                                             { Baum ist leer, dann                        }
  then begin
         insert := which;                                                { wird das Element which zum neuen Suchbaum  }
         ok := false;                                                    { und war natürlich nicht vorhanden          }
       end
  else begin
         If isEqualTo(which)                                             { Wenn die aktuelle Wurzel gleich which ist, }
         then begin { ***** HIER ERGÄNZEN! ***** }
                                                                         { dann kann es nicht eingefügt werden        }
                                                                         { Gib also unveränderten Baum zurück         }
              end 
         else if isBiggerThan(which)                                     { Wenn aktuelle Wurzel größer als which ist, }
              then begin { ***** HIER ERGÄNZEN! ***** }
                                                                         { dann muss das Element in den linken Teil-  }
                                                                         { baum eingefügt werden. Dieser (evtl.) er-  }
                                                                         { weiterte linke Teilbaum wird links ange-   }
                                                                         { hängt und der neue Baum wird zurückgegeben }
                   end
              else begin
                     tb := (next('R') as TSuchbaum);                     { das Element muss in den rechten Teilbaum   }
                     tb := tb.insert (which, ok);                        { eingefügt werden. Dieser (evtl.) erweiterte}
                     append (tb, 'R');                                   { rechte Teilbaum wird links angehängt und   }
                     insert := self;                                     { der so erweiterte Baum wird zurückgegeben. }
                   end
       end;
end;

function TSuchbaum.cutOutBiggest (var biggest: TSuchbaum): TSuchbaum;
var tb: TSuchbaum;
begin
   if next('R').isEmpty
      then begin                                                         { größtes Element gefunden, also:            }
             cutOutBiggest := (next('L') as TSuchbaum);                  { dieses Element isolieren, d. h. den linken }
                                                                         { Teilbaum zurückliefern.                    }
             biggest := self;                                            { und das größte Element in CbR-Variablen    }
                                                                         { zurückgeben                                }
           end
      else begin                                                         { noch kein größtes Element                  }
             tb:= (next('R') as TSuchbaum);                              { also muss die Suche im rechten Teilbaum    }
             tb:= tb.cutOutBiggest (biggest);                            { weitergehen. Dieser wird anschließend ohne }
             append (tb, 'R');                                           { das größte Element wieder angehängt.       }
             cutOutBiggest := self;                                      { und der veränderte Baum wird zurückgegeben }
           end;
end;

function TSuchbaum.deleteIt: TSuchbaum;
var groesstes: TSuchbaum;                                                { größtes Element im linken Teilbaum         }
    tb: TSuchbaum;
begin
    if next('R').isEmpty                                                 { wenn rechter Teilbaum leer ist,            }
    then deleteIt := (deleteAndGetNext ('L') as TSuchbaum)               {    dann durch diesen ersetzen.             }
    else if next('L').isEmpty                                            { wenn linker Teilbaum leer ist,             }
         then deleteIt := (deleteAndGetNext('R') as TSuchbaum)           {    dann durch diesen ersetzen.             }
         else begin  { ***** HIER ERGÄNZEN! ***** }
                                                                         { Linken Teilbaum holen                      }
                                                                         { in diesem das größte Element isolieren     }
                                                                         { und diesen Teilbaum wieder anhängen        }

                                                                         { hänge jetzt aktuellen linken und rechten TB}
                                                                         { an das zuvor ermittelte größte Element an  }
                                                                         { und trenne die Teilbäume vom aktuellen     }
                                                                         { Element.                                   }
                                                                         { Jetzt kann das aktuelle Element gelöscht   }
                                                                         { werden und das zuvor größte Element zurück }
              end;                                                       { gegeben werden.                            }
end;

function TSuchbaum.delete(which: TSuchbaum; var ok: boolean): TSuchbaum;
var tb: TSuchBaum;
begin
  If isEmpty
  then begin                                                             { Baum ist leer, dann                        }
         ok := false;                                                    { kann man nichts löschen.                   }
         delete := Self;                                                 { Gib den unveränderten Baum zurück          }
       end
  else begin
         if isEqualTo(which)                                             { Wenn das Suchelement existiert, dann       }
         then begin
                delete := deleteIt;                                      { aktuellen Baum ohne das Element w zurück-  }
                ok := true;                                              { geben.                                     }
              end
         else if isBiggerThan(which)                                     { Wenn die aktuelle Wurzel größer als w, dann}
              then begin
                     tb := (next('L') as TSuchbaum);                     { Suche im linken Teilbaum weiter und lösche }
                     tb := tb.delete (which, ok);                        { darin das Element.                         }
                     append (tb, 'L');                                   { Hänge anschließend den veränderten Baum    }
                     delete := Self;                                     { links an und gib den gesamten Baum zurück. }
                   end
              else begin
                     tb:= (next('R') as TSuchbaum);                      { Suche im rechten Teilbaum weiter und lösche}
                     tb:= tb.delete (which, ok);                         { darin das Element.                         }
                     append (tb, 'R');                                   { Hänge anschließend den veränderten Baum    }
                     delete := Self;                                     { rechts an und gib den gesamten Baum zurück.}
                   end;
       end;
end;

end.