Wozu dient der binäre Suchbaum?

Binäre Suchbäume werden hauptsächlich für die Suche und dynamische Sortierung verwendet. Die zeitliche Komplexität des „Einfügens/Abfragens/Löschens“ von Binärbäumen beträgt „O(log(n))“, wird jedoch normalerweise nicht verwendet Tatsächliche Verwendung ist so schnell, weil die in der Einfügungsreihenfolge verwendete „Mitte“ normalerweise nicht so genau ist.

Die Rolle des binären Suchbaums

Die Hauptrolle, die ich kenne, ist Suche und dynamische Sortierung. Die zeitliche Komplexität des Einfügens/Abfragens/Löschens in einem Binärbaum beträgt O(log(n)). Bei der tatsächlichen Verwendung ist es jedoch normalerweise nicht so schnell, da die in der Einfügungsreihenfolge verwendete Mitte normalerweise nicht so genau ist. Insbesondere wenn die Reihenfolge der eingefügten Daten geordnet oder grundsätzlich geordnet ist, wird der Binärbaum im schlimmsten Fall ernsthaft unausgeglichen In diesem Fall fällt es auf die gleiche Ebene wie eine verknüpfte Liste.

Die Hauptoperationen des binären Sortierbaums sind:

1. Suche: Rekursiv suchen, ob der Schlüssel vorhanden ist.

2. Einfügung: Der Schlüssel existiert nicht im ursprünglichen Baum. Das Einfügen des Schlüssels gibt true zurück, andernfalls wird false zurückgegeben.

3. Konstruktion: Schleifeneinfügungsvorgang.

4. Löschen: (1) Blattknoten: Direkt löschen, ohne den ursprünglichen Baum zu beeinträchtigen.

(2) Nur Knoten mit linken oder rechten Teilbäumen: Nachdem der Knoten gelöscht wurde, verschieben Sie einfach seinen gesamten linken Teilbaum oder rechten Teilbaum an die Position des gelöschten Knotens, und der Sohn erbt das Erbe des Vaters.

(3) Knoten mit linken und rechten Teilbäumen: Suchen Sie den direkten Vorgänger oder direkten Nachfolger s des Knotens p, der gelöscht werden muss, ersetzen Sie den Knoten p durch s und löschen Sie dann den Knoten s.

Das obige ist der detaillierte Inhalt vonWozu dient der binäre Suchbaum?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!