Was ist ein binärer Suchbaum?

Binärer Suchbaum wird auch als binärer Suchbaum oder binärer Sortierbaum bezeichnet. Ein binärer Suchbaum ist als binärer Baum organisiert und kann durch eine verknüpfte Listendatenstruktur dargestellt werden, in der jeder Knoten im Allgemeinen ein Objekt ist Zusätzlich zu Schlüssel- und Satellitendaten enthält jeder Knoten auch die Attribute lchild, rchild und parent.

Binärer Suchbaum, (auch: binärer Suchbaum, binärer Sortierbaum) ist entweder ein leerer Baum oder ein binärer Baum mit den folgenden Eigenschaften: Wenn sein linker Teilbaum nicht leer ist, sind die Werte aller Knoten im linken Teilbaum kleiner als der Wert seines Wurzelknotens. Wenn sein rechter Teilbaum nicht leer ist, sind die Werte aller Knoten im rechten Teilbaum sind nicht leer. Die Werte aller Knoten sind größer als der Wert ihres Wurzelknotens; ihre linken und rechten Teilbäume sind ebenfalls binär sortierte Bäume. Als klassische Datenstruktur verfügt der binäre Suchbaum über die Eigenschaften schneller Einfüge- und Löschvorgänge verknüpfter Listen und den Vorteil einer schnellen Suche in Arrays. Daher wird er häufig in Dateisystemen und Datenbanken verwendet Datenstrukturen führen effiziente Sortier- und Abrufvorgänge durch.

Prinzip

Binärer Suchbaum (BST) wird auch binärer Suchbaum oder binärer Sortierbaum genannt. Ein binärer Suchbaum ist als Binärbaum organisiert und kann durch eine verknüpfte Listendatenstruktur dargestellt werden, in der jeder Knoten ein Objekt ist. Im Allgemeinen enthält jeder Knoten zusätzlich zu Schlüssel- und Satellitendaten auch die Attribute lchild, rchild und parent, die auf das linke Kind, das rechte Kind bzw. die Eltern (Elternknoten) des Knotens verweisen. Wenn kein untergeordneter oder übergeordneter Knoten vorhanden ist, ist der Wert des entsprechenden Attributs NIL. Der Wurzelknoten ist der einzige Knoten im Baum, dessen übergeordneter Zeiger NIL ist, und die untergeordneten Knotenzeiger der Blattknoten sind ebenfalls NIL.

Struktur

Der binäre Suchbaum ist eine Datenstruktur, die die folgenden Vorgänge effizient ausführen kann.

1. Geben Sie einen Wert ein

2. Fragen Sie ab, ob ein bestimmter Wert enthalten ist

3. Löschen Sie einen bestimmten Wert

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