Binärer Suchbaum
In der Informatik ist ein binärer Suchbaum oder ABR (auf Englisch binärer Suchbaum oder BST ) eine Datenstruktur, die eine Menge oder ein assoziatives Array darstellt, dessen Schlüssel zu einer vollständig geordneten Menge gehören . Ein binärer Suchbaum ermöglicht schnelle Operationen, um einen Schlüssel zu finden, einen Schlüssel einzufügen oder zu löschen.
Definition
Allgemeine Definition
Ein binärer Suchbaum ist ein binärer Baum, in dem jeder Knoten einen Schlüssel hat , so dass jeder Knoten des linken Teilbaums einen Schlüssel hat, der kleiner oder gleich dem des betrachteten Knotens ist, und jeder Knoten des rechten Teilbaums einen Schlüssel hat, der größer als ist oder gleichwertig - Abhängig von der Implementierung des ABR können gleichwertige Schlüssel verboten sein oder nicht. Die Knoten, die wir hinzufügen, werden zu Blättern des Baums.
Spezifische Definitionen
- Ein binärer Suchbaum gilt als vollständig, wenn alle Ebenen des Baums gefüllt sind, mit Ausnahme möglicherweise der letzten, auf der sich die Knoten links befinden.
- Ein perfekter Binärbaum ist ein vollständiger Baum mit allen Blättern auf derselben Höhe (die letzte Ebene ist vollständig besetzt).
- Ein Binärbaum gilt als entartet, wenn jeder seiner Knoten höchstens ein Kind hat.
- Ein Binärbaum ist ausgeglichen, wenn alle Pfade von der Wurzel zu den Blättern gleich lang sind.
Operationen
Forschung
Das Durchsuchen eines Binärbaums nach einem Knoten mit einem bestimmten Schlüssel ist ein rekursiver Prozess . Wir beginnen mit der Untersuchung der Wurzel. Wenn sein Schlüssel der gesuchte Schlüssel ist, wird der Algorithmus beendet und gibt die Wurzel zurück. Wenn es streng weniger ist, befindet es sich im linken Teilbaum, auf dem wir die Suche rekursiv durchführen. Wenn der gesuchte Schlüssel streng größer als der Stammschlüssel ist, wird die Suche im rechten Teilbaum fortgesetzt. Wenn wir ein Blatt erreichen, dessen Schlüssel nicht der gesuchte ist, wissen wir, dass der gesuchte Schlüssel keinem Knoten gehört und daher nicht im Suchbaum erscheint. Wir können die Erkundung eines binären Suchbaums mit der Dichotomiesuche vergleichen, die auf die gleiche Weise abläuft, außer dass sie direkt zu jedem Element eines Arrays führt, anstatt Links zu folgen. Der Unterschied zwischen den beiden Algorithmen besteht darin, dass wir bei der dichotomen Suche ein Kriterium für die Aufteilung des Raums in zwei Teile annehmen, das wir bei der Suche in einem Baum nicht haben.
fonction Recherche(A,e) Si A = . retourner Faux Sinon A = (x,FilsGauche,FilsDroit) Si x = e retourner Vrai Sinon si e < x retourner Recherche(FilsGauche,e) Sinon retourner Recherche(FilsDroit,e)Diese Operation erfordert im Durchschnitt eine Zeit in O (log (n)), im kritischen Fall jedoch O (n), wenn der Baum vollständig unausgeglichen ist und wie eine verknüpfte Liste aussieht. Dieses Problem ist ausgeschlossen, wenn die Welle während des Einfügens durch Drehen ausgeglichen wird, wodurch zu lange Listen entstehen können.
Einfügen
Das Einfügen eines Knotens beginnt mit einer Suche: Wir suchen nach dem Schlüssel des einzufügenden Knotens. Wenn wir zu einem Blatt kommen, fügen wir den Knoten als untergeordnetes Element des Blattes hinzu, indem wir seinen Schlüssel mit dem des Blattes vergleichen: Wenn er niedriger ist, befindet sich der neue Knoten links; sonst wird es richtig sein.
fonction Insertion(A,e) Si A = . retourner (e,.,.) Sinon A = (x,FilsGauche,FilsDroit) Si e < x retourner (x,Insertion(FilsGauche,e),FilsDroit) Sinon retourner (x,FilsGauche,Insertion(FilsDroit,e))Die Komplexität ist dieselbe wie bei der Suche: O (log n) im Durchschnittsfall und O (n) im kritischen Fall.
Es ist auch möglich, eine Prozedur zum Hinzufügen eines Elements zur Wurzel eines Binärbaums zu schreiben. Diese Operation erfordert die gleiche Komplexität, ist jedoch hinsichtlich des Zugriffs auf die Elemente besser.
Streichung
Wir beginnen damit, den Schlüssel des zu löschenden Knotens im Baum zu finden. Nachdem der zu löschende Knoten mit seinem Schlüssel gefunden wurde, sind mehrere Fälle zu berücksichtigen:
- Entfernen eines Blattes : Sie müssen es nur aus dem Baum entfernen, da es keine Fäden hat.
- Entfernen eines Knotens mit einem untergeordneten Knoten : Er muss aus dem Baum entfernt werden, indem er durch seinen Sohn ersetzt wird.
- Löschen eines Knotens mit zwei untergeordneten Knoten : Angenommen, der zu löschende Knoten heißt N (der Knoten mit dem Wert 7 in der folgenden Grafik). Wir tauschen den Knoten N mit seinem nächsten Nachfolger (dem Knoten ganz links des rechten Teilbaums unten, dem Knoten mit dem Wert 9) oder seinem nächsten Vorgänger (dem Knoten ganz rechts des Teilbaums links unten mit dem Knoten des Werts 6) aus. Dies ermöglicht es, eine binäre Suchbaumstruktur am Ende der Operation beizubehalten. Dann wenden wir die Löschprozedur erneut auf N an , das jetzt ein Blatt oder ein Knoten mit nur einem Kind ist.
Diese Wahl der Implementierung kann dazu beitragen, den Baum aus dem Gleichgewicht zu bringen. Da immer Blätter des linken Teilbaums gelöscht werden, führt die häufige Verwendung dieser Funktion zu einem schwereren Baum rechts als links. Dies kann behoben werden, indem nacheinander die Entfernung des Minimums des rechten Sohnes mit der Entfernung des Maximums des linken Sohnes abgewechselt wird, anstatt immer das letztere zu wählen. Zum Beispiel ist es möglich, einen Zufallsfaktor zu verwenden: Das Programm hat eine von zwei Chancen, das richtige Kind auszuwählen, und eine von zwei Chancen, das linke Kind auszuwählen.
In allen Fällen erfordert diese Operation das Durchlaufen des Baums von der Wurzel zu einem Blatt: Die Ausführungszeit ist daher proportional zur Tiefe des Baums, die im schlimmsten Fall gleich n ist, daher ein Komplexitätsmaximum in O (n) .
Anwendungen
Ordentlicher Kurs
Wir können die Schlüssel eines binären Suchbaums in aufsteigender Reihenfolge abrufen, indem wir einen Infix-Scan durchführen. Es ist notwendig, die sortierte Liste in dieser Reihenfolge zu verketten, die rekursiv erhalten wird, indem das linke Kind an der Wurzel durchlaufen wird, und dann die Liste, die rekursiv erhalten wird, indem das rechte Kind durchlaufen wird. Es ist möglich, dies in umgekehrter Reihenfolge zu tun, beginnend mit dem richtigen Teilbaum. Der Pfad des Baums erfolgt in linearer Zeit, da er jeden Knoten nur einmal durchlaufen muss.
fonction ParcoursInfixe(A): si A = . retourner [] sinon A = (x,FilsGauche,FilsDroit) retourner ParcoursInfixe(FilsGauche) + [x] + ParcoursInfixe(FilsDroit)Sortierung
Wir können daher einen einfachen, aber ineffizienten Sortieralgorithmus erstellen , indem wir alle Schlüssel, die wir sortieren möchten, in einen neuen binären Suchbaum einfügen und diesen Baum dann wie oben geordnet durchsuchen.
A = . pour e dans L faire A = Insertion(A,e) ListeTriee = ParcoursInfixe(A)Die schlechteste Ausführungszeit ist in O (n²), wobei n die Anzahl der Schlüssel im Baum ist, die erhalten werden, wenn die Schlüssel bereits bestellt sind: Wir haben dann eine verknüpfte Liste. Wenn wir zum Beispiel die Schlüssel 1, 2, 3, 4, 5 in dieser Reihenfolge angeben, erhalten wir den Baum (Void, 1, (Void, 2, (Void, 3, (Void, 4, (Void, 5,))))))) Leer))))) . Es gibt viele Möglichkeiten, um dieses Problem zu vermeiden. Die häufigste ist der ausgeglichene Baum. Wir können dann zu einem schlimmsten Fall in O (n * ln (n)) gelangen.
Prioritätswarteschlangen
Die binären Suchbäume können verwendet werden, um den abstrakten Typ der Prioritätswarteschlange zu implementieren . Tatsächlich werden die Operationen des Einführens eines Schlüssels und des Vakuumtests mit vorteilhaften Komplexitäten ausgeführt (jeweils in O (log (n)) und in O (1), wobei n die Anzahl der im Baum dargestellten Schlüssel ist). Für das Löschen des größten Schlüssels reicht es aus, den Baum von seiner Wurzel aus zu durchsuchen, indem Sie das richtige untergeordnete Element für jeden Knoten auswählen und das Terminalblatt löschen. Dies erfordert eine Anzahl von Operationen, die der Höhe des Baums entsprechen, daher eine logarithmische Komplexität bei der Anzahl der Schlüssel. Der berüchtigte Vorteil dieser Darstellung einer Prioritätswarteschlange besteht darin, dass bei einem ähnlichen Prozess auch der kleinste Schlüssel in logarithmischer Zeit entfernt wird.
Ausbalancieren
Das Einfügen und Löschen wird bei O (h) ausgeführt, wobei h die Höhe des Baums ist. Dies erweist sich als besonders kostspielig, wenn der Baum sehr unausgeglichen ist (z. B. ein Kammbaum, dessen Höhe in der Anzahl der Schlüssel linear ist), und wir gewinnen daher an Effizienz beim Ausbalancieren der Bäume während ihrer Verwendung. Es gibt Techniken, um ausgeglichene Bäume zu erhalten , dh um eine logarithmische Höhe in der Anzahl der Elemente zu gewährleisten:
- Der AVL-Baum
- die Bäume rot-schwarz
- Bäume 2-3
- die 2-3-4 Bäume
- die B-Bäume
Erweiterungen
Ein Spreizbaum ist ein binärer Suchbaum, der häufig verwendete Elemente automatisch näher an die Wurzel bringt. In einem Treap hat jeder Knoten auch eine höhere Priorität als jedes seiner untergeordneten Knoten.