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 suchenElement einfügenElement löschen
Normales ArrayO(n)O(n)O(n)
Sortiertes ArrayO(logn)O(n)O(n)
Binärer SuchbaumO(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:

package example.binarySearch;

/**
* 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;
    }
}
Weitere Erweiterungen