Bäume

Die Folge der Vergleiche ist beim binären Suchen vorbestimmt und kann in einem binären Baum dargestellt werden.

balancierte Bäume

Bei einem balancierten Baum sind die Aste gleichlang (symmetrisch). Für die Suche ist diese 'Baumart' günstig, für das Löschen bzw. Einfügen nicht.

unbalancierter (degenerierter) Baum

Bei einem degenerierten Baum hat jeder Knoten 'nur' rechte oder linke Nachfolger. Hier kann die Suche N Vergleiche benötigen (d.h. Suche bei einem deg. Baum ist schlecht).

AVL - Baum

Bei einem AVL-Baum gilt, dass die Tiefendifferenz der Knoten nicht mehr als 1 betragen darf. AVL steht für die Anfangsbuchstaben der Nachnamen der drei russischen Mathematiker.

Diese Methode ist kompliziert, da man viel herumranchieren muss, um einen balancierten Baum zu erhalten.

2-3-4 Baum

Dieser Baum bietet gegenüber herkömmlichen binären Suchbäumen mehr Flexibilität (durch 3 und 4 Knoten). Im Gegensatz zum Löschen und Einfügen eines Elementes ist das Suchen eine einfache Sache.

Lazy Deletion ('faule' Löschung)

Beim Löschen eines Elementes kommt es darauf an, wo sich der Knoten befindet bzw. wieviele Nachfolger er hat. Hat ein Knoten keinen oder nur einen Nachfolger oder einer seiner zwei Nachfolger hat keinen Nachfolger, so ist das Löschen einfach. Das Problem tritt dann auf, wenn die Nachfolger dieses Knotens weitere Nachfolger haben. Hier muss entweder das am weitesten rechts befindliche Element von der linken Verzweigung oder das am weitesten links befindliche Element von der rechten Verzweigung ausgekettet werden und dann an der Stelle des gelöschten Knotens eingefügt werden.

Bei der Lazy Deletion wird dieses Problem so umgangen, dass der Knoten nicht wirklich gelöscht wird, sondern dass bei dem Datensatz ein Löschbit gesetzt wird.

Indirekte Suche (Indirect Search)

Für Attribute nach denen oft gesucht wird, wird ein Hilfsbaum bzw. ein Hilfsindex benutzt.