Atari Logo
Atari Computer

Hauptseite -
Welches System? -
Hardware -
Software -
Emulatoren -
Internet
MausNet
Programmieren
Verweise
Über

Algorithmen

Home Botanik: Basisalgorithmen für Container doppelt verkettete Liste AVL-Baum

3.3 Binärbaum

Die Listen haben den Nachteil, das eine Suche nach einem bestimmten Element immer der Reihe nach jedes Element der Liste vergelichen muß, also im ungünstigsten Fall die Liste komplett durchwandert. Die Suche kann stark beschleunigt werden, wenn jeder Knoten zwei Zeiger hat. Ein Zeiger zeigt auf Elemente, die kleiner sind und ein Zeiger zeigt auf Elemente, die größer sind.


Geht man von der Wurzel des Baums einen Knoten weiter, so kann dieser Knoten mit seinen Unterknoten wieder als ein Teilbaum betrachtet werden. Deshalb lassen sich einige Operationen sehr einfach relursiv beschreiben.

Das Einfügen ein es neuen Elements geht wie folgt:

  1. Starte mit der Wurzel
  2. Ist der aktuelle Knoten NULL/NIL, setze ihn auf das neue Element und das neue Element ist eingefügt.
  3. Ist das neue Element kleiner als der aktuelle Knoten, führe Schritt 2 mit dem linken Nachfolgeknoten durch.
  4. Ist das neue Element größer als der aktuelle Knoten, führe Schritt 2 mit dem rechten Nachfolgeknoten durch.

Auch das Suchen läßt sich rekursiv leicht beschreiben:

  1. Starte mit der Wurzel
  2. Ist der aktuelle Knoten leer, ist das Element nicht vorhanden und die Suche ist beendet.
  3. Ist der aktuelle Knoten der gesuchte, ist die Suche ist beendet.
  4. Ist das gesuchte Element kleiner als der aktuelle Knoten, führe Schritt 2 mit dem linken Nachfolgeknoten durch.
  5. Ist das gesuchte Element größer als der aktuelle Knoten, führe Schritt 2 mit dem rechten Nachfolgeknoten durch.

Für das komplette Durchwandern des Baums gibt es drei verschiedenen Möglichkeiten, die sich in der Reihenfolgem, in der die einzelnen Knoten bearbeitet werden, unterscheiden

praeorder
  1. Bearbeite den aktuellen Knoten
  2. Durchwandere den linken Teilbaum
  3. Durchwandere den rechten Teilbaum
inorder
  1. Durchwandere den linken Teilbaum
  2. Bearbeite den aktuellen Knoten
  3. Durchwandere den rechten Teilbaum
postorder
  1. Durchwandere den linken Teilbaum
  2. Durchwandere den rechten Teilbaum
  3. Bearbeite den aktuellen Knoten

Das Entfernen eines Knoten ist allerdings aufwendiger, da zwei Teilbäume zu einem Teilbaum vereinigt werden müssen. Wenn einer der zwei Teilbäume des zu entfernenden Knotens leer ist, ist das Löschen einfach. Der nicht leere Teilbaum ersetzt den zu löschenden Knoten. Seind beide Teilbäume nicht leer, kann der folgende Algorithmus benutzt werden:


  1. Suche im rechten Teilbaum nach links den untersten Knoten.
  2. Füge dort links den linken Teilbaum an. Dies geht, da alle Elemente des linken Teilbaums kleiner als das zu löschende Element sind. Und damit sind sie auch kleiner als alle Elemente des rechten Teilbaums.
  3. Setze den rechten Teilbaum an der Stelle des zu löschenden Elements ein.

Alternativ kann natürlich auch der rechte Teilbaum in den linken eingebaut werden. Das zu löschende Element wird dann durch den linken Teilbaum ersetzt.

Beispielcode
Home Botanik: Basisalgorithmen für Container doppelt verkettete Liste AVL-Baum


Best viewed with any browser English version not yet available.

Änderungen und Irrtümer vorbehalten. Letzte Änderung:
14 September 2001.
Home - Mail an den Webmaster - Impressum