|
Wie bereits bekannt ist, kann man die Folge der Vergleiche des binären Suchens in einem binären Baum darstellen. Die Idee ist nun, die Daten in einem Baum durch Verkettung zu speichern. Der Vorteil gegenüber der binären Suche ist, daß die Datenstruktur immer leicht wartbar ist. Es ist einfach ein neues Element einzubinden und ohne kompliziertes Herumschieben von Daten ist immer eine sortierte Struktur vorhanden.
Sie ist eine der fundamentalsten Methoden der Informatik. Trotz ihrer Einfachheit ist sie effizient, und wird daher sehr oft eingesetzt.
Ein Baum ist dadurch definiert, daß jedes Glied genau ein übergeordnetes hat. Ein binärer Baum hat zusätzlich noch die Eigenschaft, daß jeder Knoten eine linke und eine rechte Verkettung hat. Beim binären Suchen wird weiters davon ausgegangen, daß alle Datensätze mit einem kleineren Schlüssel im linken Unterbaum und alle größeren und gleichen im rechten Unterbaum sind.
Bei der Suche vergleicht man den gesuchten Schlüssel mit der Wurzel, und geht dann in den entsprechenden Unterbaum, wo diese Vergleiche rekursiv fortgesetzt werden, bis die Gleichheit der Schlüssel erreicht ist, oder wenn der entsprechende Unterbaum leer ist.
Um einen Knoten hinzuzufügen, verfährt man wie beim erfolglosen Suchen, nur wird dann der leere Unterbaum durch den einzufügenden Knoten (I) ersetzt.
Ein Suchen oder Einfügen in einem binären Suchbaum erfordert durchschnittlich ca. 2 ln N Vergleiche, wenn der Baum aus N zufälligen Schlüsseln aufgebaut ist.
Die Laufzeit von Algorithmen, die binäre Suchbäume betreffen sind stark von der Form der Bäume abhängig. Bei ausgeglichenen Bäumen kann sie sogar logarithmisch werden. Durch die Art des Aufbauens der Bäume können aber auch extrem ungünstige Bäume entstehen (A Z B Y C X ... oder A B C D E F ...).
Im ungünstigsten Fall kann eine Suche in einem binären Suchbaum mit N Schlüsseln N Vergleiche erfordern.
|
