home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
Turbo Toolbox
/
Turbo_Toolbox.iso
/
sonderh1
/
avlb_els.inc
< prev
next >
Wrap
Text File
|
1979-12-31
|
13KB
|
366 lines
{===== MODUL AVLB-ELS === Einfuegen, Loeschen und Suchen in AVL-Baeumen =====}
{----------------------------------------------------------------------------}
{ Der direkte linke Nachfolger des Knotens 'baum' tauscht mit 'baum' die
Position unter Beibehaltung der Ordnung im Baum und ohne die Kennzeichen
fuer die Ausgeglichenheit anzugleichen, da dies beim Loeschen anders
vorgeht als beim Einfuegen. }
PROCEDURE rot_r (VAR baum: tree);
VAR ast: tree;
BEGIN
ast := baum^.links;
baum^.links := ast^.rechts;
ast^.rechts := baum;
baum := ast;
END;
{----------------------------------------------------------------------------}
{ Wie 'rot_r' nur seitenverdreht. }
PROCEDURE rot_l (VAR baum: tree);
VAR ast: tree;
BEGIN
ast := baum^.rechts;
baum^.rechts := ast^.links;
ast^.links := baum;
baum := ast;
END;
{----------------------------------------------------------------------------}
{ Der direkte Nachfolger zweiten Grades des Knotens 'baum' ueber den Pfad
links, rechts wird an die Stelle des Knotens gesetzt. Der ehemalige Knoten
'baum' wird dann der linke Nachfolger des oben genannten. Die Anpassungen
fuer die Ausgeglichenheitskennzeichen werden weitestgehend vorgenommen. }
PROCEDURE rot_lr (VAR baum: tree);
VAR ast1, ast2: tree;
BEGIN
ast1 := baum^.links;
ast2 := ast1^.rechts;
ast1^.rechts := ast2^.links;
ast2^.links := ast1;
baum^.links := ast2^.rechts;
ast2^.rechts := baum;
IF ast2^.schiefe=left THEN
baum^.schiefe := right
ELSE
baum^.schiefe := none;
IF ast2^.schiefe=right THEN
ast1^.schiefe := left
ELSE
ast1^.schiefe := none;
baum := ast2;
END;
{----------------------------------------------------------------------------}
{ Wie 'rot_lr' nur seitenverdreht. }
PROCEDURE rot_rl (VAR baum: tree);
VAR ast1, ast2: tree;
BEGIN
ast1 := baum^.rechts;
ast2 := ast1^.links;
ast1^.links := ast2^.rechts;
ast2^.rechts := ast1;
baum^.rechts := ast2^.links;
ast2^.links := baum;
IF ast2^.schiefe=right THEN
baum^.schiefe := left
ELSE
baum^.schiefe := none;
IF ast2^.schiefe=left THEN
ast1^.schiefe := right
ELSE
ast1^.schiefe := none;
baum := ast2
END;
{============================================================================}
{ Im 'baum' wird nach dem 'stichwort' gesucht. Ist es noch nicht vorhanden,
wird dafuer ein neuer Knoten in den Baum eingefuegt. Ist der Baum AVL-ausge-
glichen, bleibt diese Ausgeglichenheit erhalten. }
PROCEDURE einfuegen (VAR baum: tree; stichwort: key; VAR gewachsen: BOOLEAN);
{--------------------------------------------------------------------------}
PROCEDURE erzeugen (VAR baum: tree; stichwort: key; VAR gewachsen: boolean);
BEGIN
new (baum);
gewachsen := true;
restinfo (stichwort, baum^.info);
message (1);
WITH baum^ DO
BEGIN
links := nil;
rechts := nil;
schiefe := none;
END;
END;
{--------------------------------------------------------------------------}
{ Gehoert das 'stichwort' in den linken Teilbaum von 'baum', dann ist diese
Prozedur aufzurufen. Nach dem rekursiven Aufruf von 'einfuegen' wird der
Teilbaum ausgeglichen, was aber nur in einem bestimmten Fall noetig ist,
da der Teilbaum durch das Einfuegen unter Umstaenden nur schlechter oder
sogar besser ausgeglichen wird. }
PROCEDURE weiter_links (VAR baum: tree; stichwort: key;
VAR gewachsen: BOOLEAN);
BEGIN
einfuegen (baum^.links, stichwort, gewachsen);
IF gewachsen THEN
CASE baum^.schiefe OF
right: BEGIN
baum^.schiefe := none;
gewachsen := false;
END;
none: baum^.schiefe := left;
left: BEGIN
IF baum^.links^.schiefe = left THEN
BEGIN
rot_r (baum);
baum^.rechts^.schiefe := none;
END
ELSE
rot_lr (baum);
baum^.schiefe := none;
gewachsen := false;
END;
END;
END;
{--------------------------------------------------------------------------}
{ Wie 'weiter_links' nur seitenverdreht. }
PROCEDURE weiter_rechts (VAR baum: tree; stichwort: key;
VAR gewachsen: BOOLEAN);
BEGIN
einfuegen (baum^.rechts, stichwort, gewachsen);
IF gewachsen THEN
CASE baum^.schiefe OF
right: BEGIN
IF baum^.rechts^.schiefe=right THEN
BEGIN
rot_l (baum);
baum^.links^.schiefe := none;
END
ELSE
rot_rl (baum);
baum^.schiefe := none;
gewachsen := false;
END;
none: baum^. schiefe := right;
left: BEGIN
baum^.schiefe := none;
gewachsen := false;
END;
END;
END;
{--------------------------------------------------------------------------}
BEGIN { einfuegen }
IF baum = nil THEN
erzeugen (baum, stichwort, gewachsen)
ELSE IF baum^.info.stichwort > stichwort THEN
weiter_links (baum, stichwort, gewachsen)
ELSE IF baum^.info.stichwort < stichwort THEN
weiter_rechts (baum, stichwort, gewachsen)
ELSE
BEGIN
gewachsen := false;
message(4);
END;
END;
{============================================================================}
{ Im 'baum' wird nach dem 'stichwort' gesucht und der dazugehoerige Knoten
aus dem Baum entfernt. Eine vorhandene AVL-Ausgeglichenheit des Baumes
bleibt dabei erhalten. }
PROCEDURE loeschen (VAR baum: tree; stichwort: key; VAR geschrumpft: BOOLEAN);
VAR knoten: tree; { zeigt auf den freizugebenden Knoten }
{--------------------------------------------------------------------------}
{ Es wird ein AVL-Ausgleich vorgenommen, fuer den Fall, dass der rechte
Teilbaum von 'baum' geschrumpft ist. Dabei kann es sein, dass der Baum
nun besser ausgeglichen ist (vorher right), schlechter ausgeglichen ist
(vorher none) oder aber auch nicht mehr ausgeglichen ist, so dass eine
Rotation faellig wird, die je nach Situation eine andere Form hat. }
PROCEDURE ausgl_rechts (VAR baum: tree; VAR geschrumpft: BOOLEAN);
BEGIN
CASE baum^.schiefe OF
left: CASE baum^.links^.schiefe OF
left: BEGIN
rot_r (baum);
baum^.schiefe := none;
baum^.rechts^.schiefe := none;
END;
none: BEGIN
rot_r (baum);
baum^.schiefe := right;
baum^.rechts^.schiefe := left;
geschrumpft := false;
END;
right: BEGIN
rot_lr (baum);
baum^.schiefe := none;
END;
END;
none: BEGIN
baum^.schiefe := left;
geschrumpft := false;
END;
right: baum^.schiefe := none;
END;
END;
{--------------------------------------------------------------------------}
{ Wie 'ausgl_rechts' nur seitenverdreht. }
PROCEDURE ausgl_links (VAR baum: tree; VAR geschrumpft: BOOLEAN);
BEGIN
CASE baum^.schiefe OF
right: CASE baum^.rechts^.schiefe OF
right: BEGIN
rot_l (baum);
baum^.schiefe := none;
baum^.links^.schiefe := none;
END;
none: BEGIN
rot_l (baum);
baum^.schiefe := left;
baum^.links^.schiefe := right;
geschrumpft := false;
END;
left: BEGIN
rot_rl (baum);
baum^.schiefe := none;
END;
END;
none: BEGIN
baum^.schiefe := right;
geschrumpft := false;
END;
left: baum^.schiefe := none;
END;
END;
{--------------------------------------------------------------------------}
{ Diese Prozedur sucht in dem angegebenen Baum 'zweig' das kleinste Stich-
wort. Dessen Inhalt wird dann im zu loeschenden Knoten gespeichert. Damit
wird der eigene Knoten zum zu loeschenden. }
PROCEDURE kleinsten_holen (VAR zweig: tree; VAR geschrumpft: BOOLEAN);
BEGIN
IF zweig^.links = nil THEN
BEGIN { Kleinster gefunden }
baum^.info := zweig^.info; { Kleinsten hochholen }
knoten := zweig; { Loeschmarke umsetzen }
zweig := zweig^.rechts; { Knoten den Kleinsten aus Baum entfernen }
geschrumpft := true; { bezogen auf den Vorgaenger von 'zweig' }
END
ELSE
BEGIN
kleinsten_holen (zweig^.links, geschrumpft);
IF geschrumpft THEN
ausgl_links (zweig, geschrumpft);
END;
END;
{--------------------------------------------------------------------------}
{ Der Knoten, auf den 'baum' zeigt, wird aus dem Baum entfernt und die
direkt nachfolgende Umgebung wird ausgeglichen. Das Ausgleichen des ge-
samten Baumes erfolgt auf dem Rueckweg durch die rekursiven Aufrufe von
'loeschen'. }
PROCEDURE entfernen (VAR baum: tree; VAR geschrumpft: BOOLEAN);
BEGIN
knoten := baum;
IF baum^.rechts = nil THEN
BEGIN { Wenn rechts kein Nachfolger ist, }
baum := baum^.links; { kann der linke Teilbaum ohne Kon- }
geschrumpft := true; { sequenzen an die Stelle des zu loeschenden }
END { Knoten gesetzt werden. }
ELSE IF baum^.links = nil THEN
BEGIN { Ebenso wird mit dem rechten }
baum := baum^.rechts; { Teilbaum verfahren, wenn es keinen }
geschrumpft := true; { linken gibt. }
END
ELSE
BEGIN
{ Fuer den Fall, dass es beide direkten Nachfolger gibt, wird der
Knoten mit dem naechstgroesseren Stichwort an seine Stelle gelegt }
kleinsten_holen (baum^.rechts, geschrumpft);
IF geschrumpft THEN
ausgl_rechts (baum, geschrumpft);
END;
Dispose (knoten);
END;
{--------------------------------------------------------------------------}
BEGIN { loeschen }
IF baum = nil THEN
BEGIN
message (0);
geschrumpft := false;
END
ELSE IF baum^.info.stichwort > stichwort THEN
BEGIN
loeschen (baum^.links, stichwort, geschrumpft);
IF geschrumpft THEN
ausgl_links (baum, geschrumpft);
END
ELSE IF baum^.info.stichwort < stichwort THEN
BEGIN
loeschen (baum^.rechts, stichwort, geschrumpft);
IF geschrumpft THEN
ausgl_rechts (baum, geschrumpft);
END
ELSE
BEGIN
entfernen (baum, geschrumpft);
message (2);
END;
END;
{----------------------------------------------------------------------------}
{ Im 'baum' wird nach dem 'stichwort' gesucht und eine entsprechende Meldung
ausgegeben. Anstelle der Meldung ist die betreffende Operation auszufuehren,
z. B. werden die zum Stichwort gehoerenden Informationen ausgegeben oder
geaendert, je nach Anwendung. }
PROCEDURE suchen (baum: tree; stichwort: key);
BEGIN
IF baum = nil THEN
message (0)
ELSE IF baum^.info.stichwort > stichwort THEN
suchen (baum^.links, stichwort)
ELSE IF baum^.info.stichwort < stichwort THEN
suchen(baum^.rechts, stichwort)
ELSE
message (3);
END;
{========================= ENDE DES MODULS AVLB-ELS =========================}