Binärer Suchbaum
I. Konzept und Einführung
Binärer Suchbaum (englisch: Binary Search Tree), auch bekannt als binärer Suchbaum, binärer Suchbaum, geordneter binärer Baum oder sortierter binärer Baum. Er erfüllt die folgenden Bedingungen:
- Wenn sein linker Teilbaum nicht leer ist, sind alle Knotenwerte im linken Teilbaum kleiner als sein Wurzelknoten.
- Wenn sein rechter Teilbaum nicht leer ist, sind alle Knotenwerte im rechten Teilbaum größer als sein Wurzelknoten.
Seine linken und rechten Teilbäume sind ebenfalls binäre Suchbäume.
Wie in der folgenden Abbildung dargestellt:

II. Hinweise zur Anwendbarkeit
Binäre Suchbäume haben effiziente Einfüge-, Lösch- und Abfrageoperationen.
Die durchschnittliche Zeitkomplexität istO(log n), das Worst-Case-Szenario istO(n). Binäre Suchbäume unterscheiden sich von Heaps; sie sind nicht unbedingt vollständige Binärbäume, und die zugrunde liegende Ebene lässt sich nicht ohne Weiteres direkt durch Arrays darstellen, daher werden verkettete Listen verwendet, um binäre Suchbäume zu implementieren.
| Element suchen | Element einfügen | Element löschen | |
|---|---|---|---|
| Normales Array | O(n) | O(n) | O(n) |
| Sortiertes Array | O(logn) | O(n) | O(n) |
| Binärer Suchbaum | O(logn) | O(logn) | O(logn) |
Im Folgenden führen wir zunächst die binäre Suchmethode in Array-Form als konzeptionelle Referenz ein und fahren dann mit der Einführung der Suchmethode von binären Suchbäumen fort.
III. Veranschaulichung des Prozesses der binären Suchmethode
Die Idee der binären Suche wurde 1946 vorgeschlagen. Das Suchproblem ist ein sehr wichtiges Grundproblem der Informatik. Die binäre Suche kann nur auf sortierten Sequenzen verwendet werden. Wenn wir ein Element finden möchten, betrachten wir zuerst die Beziehung zwischen dem mittleren Wert V des Arrays und den Zieldaten. Es gibt drei Fälle:
- 1. Wenn es gleich den Zieldaten ist, wird es direkt gefunden.
- 2. Wenn es kleiner als V ist, wird die Suche in der Gruppe kleiner als V fortgesetzt.
- 2. Wenn es größer als V ist, wird die Suche in der Gruppe größer als V fortgesetzt.

IV. Java-Beispielcode
Quellcode-Paket-Download:Herunterladen
Code der Datei src/example/binary/BinarySearch.java:
/**
* Binäre Suchmethode
*/
public class BinarySearch {
// Binäre Suchmethode: finde target im sortierten Array arr
// Wenn target gefunden wird, den entsprechenden Index zurückgeben
// Wenn target nicht gefunden wird, -1 zurückgeben
public static int find(Comparable[] arr, Comparable target) {
// finde target in arr[l...r]
int l = 0, r = arr.length-1;
while( l <= r ){
//int mid = (l + r)/2;
// Um einen Integer-Überlauf in extremen Fällen zu verhindern, verwenden Sie die folgende Logik zur Berechnung von mid
int mid = l + (r-l)/2;
if( arr[mid].compareTo(target) == 0 )
return mid;
if( arr[mid].compareTo(target) > 0 )
r = mid - 1;
else
l = mid + 1;
}
return -1;
}
}