TechCodeview

Zuerst werden wir das verstehen Binärbaum Und binärer Suchbaum separat, und dann werden wir uns die Unterschiede zwischen einem Binärbaum und einem binären Suchbaum ansehen.

Was ist ein Binärbaum?

A Binärbaum ist einZeiger auf das linke Kind:Es speichert die Referenz des linken untergeordneten Knotens.Hinweis auf das richtige Kind:Es speichert die Referenz des rechten untergeordneten Knotens.Datenelement:Das Datenelement ist der Wert der Daten, die vom Knoten gespeichert werden.

Der Binärbaum kann wie folgt dargestellt werden:

In der obigen Abbildung können wir beobachten, dass jeder Knoten maximal zwei untergeordnete Knoten enthält. Wenn ein Knoten kein linkes oder rechtes Kind enthält, wäre der Wert des Zeigers in Bezug auf dieses Kind NULL.

Grundlegende Terminologien, die in einem Binärbaum verwendet werden, sind:

Wurzelknoten:Der Wurzelknoten ist der erste oder oberste Knoten in einem Binärbaum.Elternknoten:Wenn ein Knoten über Kanten mit einem anderen Knoten verbunden ist, wird dieser Knoten als übergeordneter Knoten bezeichnet. In einem Binärbaum kann der übergeordnete Knoten maximal zwei untergeordnete Knoten haben.Untergeordneter Knoten:Wenn ein Knoten seinen Vorgänger hat, wird dieser Knoten als a bezeichnet untergeordneter Knoten .Blattknoten:Der Knoten, der kein untergeordnetes Element enthält, wird als a bezeichnet Blattknoten .Interner Knoten:Der Knoten, der mindestens zwei untergeordnete Knoten hat, wird als bezeichnet interner Knoten .Tiefe eines Knotens:Der Abstand vom Wurzelknoten zum gegebenen Knoten wird als a bezeichnet Tiefe eines Knotens . Wir versehen alle Knoten mit Beschriftungen, so dass der Wurzelknoten mit 0 gekennzeichnet ist, da er keine Tiefe hat, untergeordnete Knoten der Wurzelknoten mit 1 und untergeordnete Elemente des untergeordneten Wurzelknotens mit 2.Höhe:Der längste Abstand vom Wurzelknoten zum Blattknoten beträgt Höhe des Knotens .

In einem Binärbaum gibt es einen Baum, der als a bekannt ist perfekter Binärbaum . es ist ein Baum, in dem alle internen Knoten zwei Knoten enthalten müssen und alle Blattknoten die gleiche Tiefe haben müssen. Im Fall eines perfekten Binärbaums kann die Gesamtzahl der in einem Binärbaum vorhandenen Knoten mithilfe der folgenden Gleichung berechnet werden:

n = 2^m+1-1

Dabei ist n die Anzahl der Knoten und m die Tiefe eines Knotens.

Was ist ein binärer Suchbaum?

A Binärer Suchbaum ist ein Baum, der einer bestimmten Reihenfolge folgt, um die Elemente anzuordnen, während der Binärbaum keiner Reihenfolge folgt. In einem binären Suchbaum muss der Wert des linken Knotens kleiner als der des übergeordneten Knotens sein und der Wert des rechten Knotens muss größer als der des übergeordneten Knotens sein.

Lassen Sie uns das Konzept eines binären Suchbaums anhand von Beispielen verstehen.

In der obigen Abbildung können wir beobachten, dass der Wert des Wurzelknotens 15 beträgt, was größer ist als der Wert aller Knoten im linken Teilbaum. Der Wert des Wurzelknotens ist kleiner als die Werte aller Knoten in einem rechten Teilbaum. Jetzt bewegen wir uns zum linken untergeordneten Element des Wurzelknotens. 10 ist größer als 8 und kleiner als 12; Es erfüllt auch die Eigenschaft des binären Suchbaums. Jetzt bewegen wir uns zum rechten untergeordneten Knoten des Wurzelknotens. der Wert 20 ist größer als 17 und kleiner als 25; Es erfüllt auch die Eigenschaft eines binären Suchbaums. Daher können wir sagen, dass der oben gezeigte Baum der binäre Suchbaum ist.

Wenn wir nun im obigen Binärbaum den Wert von 12 auf 16 ändern, müssen wir herausfinden, ob es sich immer noch um einen binären Suchbaum handelt oder nicht.

Der Wert des Wurzelknotens beträgt 15, was größer als 10, aber kleiner als 16 ist, sodass er die Eigenschaft des binären Suchbaums nicht erfüllt. Daher handelt es sich nicht um einen binären Suchbaum.

Operationen am binären Suchbaum

Wir können Einfüge-, Lösch- und Suchvorgänge für den binären Suchbaum ausführen. Lassen Sie uns verstehen, wie eine Suche bei einer binären Suche durchgeführt wird. Unten ist der Binärbaum dargestellt, für den wir die Suchoperation durchführen müssen:

Angenommen, wir müssen 10 im obigen Binärbaum suchen. Um die binäre Suche durchzuführen, berücksichtigen wir alle Ganzzahlen in einem sortierten Array. Zuerst erstellen wir eine vollständige Liste in einem Suchraum, und alle Zahlen werden im Suchraum vorhanden sein. Der Suchraum wird durch zwei Zeiger markiert, nämlich Start und Ende. Das Array des obigen Binärbaums kann dargestellt werden als:

Zuerst berechnen wir das mittlere Element und vergleichen das mittlere Element mit dem zu suchenden Element. Das mittlere Element wird mit n/2 berechnet. Der Wert von n ist 7; Daher ist das mittlere Element 15. Das mittlere Element ist nicht gleich dem gesuchten Element, d. h. 10.

Hinweis: Wenn das gesuchte Element kleiner als das mittlere Element ist, wird die Suche in der linken Hälfte durchgeführt; Andernfalls erfolgt die Suche in der rechten Hälfte. Bei Gleichheit wird das Element gefunden.

Da das zu durchsuchende Element kleiner als das mittlere Element ist, wird die Suche im linken Array durchgeführt. Jetzt wird die Suche auf die Hälfte reduziert, wie unten gezeigt:

Das mittlere Element im linken Array ist 10, was dem gesuchten Element entspricht.

Zeitkomplexität

Bei einer binären Suche gibt es n Elemente. Wenn das mittlere Element nicht mit dem gesuchten Element übereinstimmt, wird der Suchraum auf n/2 reduziert und wir verkleinern den Suchraum so lange um n/2, bis wir das Element gefunden haben. Wenn wir uns in der gesamten Reduktion von n über n/2 bis n/4 usw. bewegen, wird log benötigt₂n Schritte.

Unterschiede zwischen Binärbaum und Binärsuchbaum