Eine Möglichkeit, einen binären Suchbaum zu implementieren, ist die Verwendung einer verknüpften Liste. Eine verknüpfte Liste ist eine nicht kontinuierliche und nicht sequentielle Speicherstruktur auf einer physischen Speichereinheit Zeiger in der verknüpften Liste werden sequentiell implementiert, und die verknüpfte Liste besteht aus einer Reihe von Knoten, und die Knoten können zur Laufzeit dynamisch generiert werden.
Binärer Suchbaum
Binärer Suchbaum ist ein Paar von Ein spezieller Binärbaum
, das zum Sortieren und Suchen nützlich ist, ist definiert als: linker Teilbaum < rechter Teilbaum
Implementierungsmethode: Im Allgemeinen wird eine verknüpfte Liste verwendet, um den Operationssatz
zu implementieren : Erstellen Sie einen Binärbaum, bestimmen Sie, ob er leer ist, durchlaufen Sie ihn, suchen Sie, finden Sie das kleinste Element, finden Sie das größte Element, fügen Sie ein, löschen Sie
Zeitkomplexität: am bestenO(logN) am schlechtestenO(N)
Verwandte Einführung:
Eine verknüpfte Liste ist eine nicht kontinuierliche und nicht sequentielle Speicherstruktur auf einer physischen Speichereinheit. Die logische Reihenfolge der Datenelemente wird durch die Zeigerverknüpfungsreihenfolge in der verknüpften Liste realisiert. Eine verknüpfte Liste besteht aus einer Reihe von Knoten (jedes Element in der verknüpften Liste wird als Knoten bezeichnet), und Knoten können zur Laufzeit dynamisch generiert werden. Jeder Knoten besteht aus zwei Teilen: Einer ist das Datenfeld, in dem Datenelemente gespeichert werden, und der andere ist das Zeigerfeld, in dem die Adresse des nächsten Knotens gespeichert wird. Im Vergleich zur linearen Tabellensequenzstruktur ist die Operation kompliziert. Da die verknüpfte Liste nicht in der richtigen Reihenfolge gespeichert werden muss, kann sie beim Einfügen eine O(1)-Komplexität erreichen, was viel schneller ist als eine andere lineare Liste oder eine sequentielle Liste, aber das Finden eines Knotens oder der Zugriff auf einen bestimmten nummerierten Knoten erfordert O(n). ) Zeit, und die entsprechenden Zeitkomplexitäten von linearen Tabellen und sequentiellen Tabellen sind O(logn) bzw. O(1).
Durch die Verwendung der verknüpften Listenstruktur kann der Nachteil der verknüpften Array-Liste behoben werden, dass die Datengröße im Voraus bekannt sein muss. Die verknüpfte Listenstruktur kann den Speicherplatz des Computers voll ausnutzen und eine flexible dynamische Speicherverwaltung erreichen. Allerdings verliert die verknüpfte Liste den Vorteil des zufälligen Lesens des Arrays. Gleichzeitig weist die verknüpfte Liste aufgrund der Vergrößerung des Zeigerfelds des Knotens einen relativ großen Speicherplatzaufwand auf. Der offensichtlichste Vorteil einer verknüpften Liste besteht darin, dass die Art und Weise, wie ein reguläres Array zugehörige Elemente anordnet, sich von der Reihenfolge unterscheiden kann, in der diese Datenelemente im Speicher oder auf der Festplatte angeordnet sind, und der Zugriff auf Daten häufig das Umschalten zwischen verschiedenen Anordnungen erfordert. Verknüpfte Listen ermöglichen das Einfügen und Entfernen von Knoten an jeder Stelle der Liste, erlauben jedoch keinen wahlfreien Zugriff. Es gibt viele verschiedene Arten von verknüpften Listen: einfach verknüpfte Listen, doppelt verknüpfte Listen und zirkulär verknüpfte Listen. Verknüpfte Listen können in verschiedenen Programmiersprachen implementiert werden. Die integrierten Datentypen von Sprachen wie Lisp und Scheme umfassen den Zugriff und Betrieb verknüpfter Listen. Programmier- oder objektorientierte Sprachen wie C, C++ und Java sind auf veränderbare Tools angewiesen, um verknüpfte Listen zu generieren.
Das obige ist der detaillierte Inhalt vonEs gibt mehrere Möglichkeiten, einen binären Suchbaum zu implementieren. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!
