Binärer Heap und binärer Suchbaum in C++

In der C++-Programmierung sind binärer Heap und binärer Suchbaum zwei häufig verwendete Datenstrukturen. Sie weisen Ähnlichkeiten, aber auch Unterschiede auf. In diesem Artikel werden die Konzepte, Grundoperationen und Anwendungsszenarien von binären Heaps bzw. binären Suchbäumen vorgestellt.

1. Binärer Heap

1.1 Konzept

Ein binärer Heap ist ein vollständiger Binärbaum, der die folgenden zwei Eigenschaften erfüllt:

1.1.1 Heap-Reihenfolge

Heap-Reihenfolge bedeutet, dass in einem binären Heap jeder den Wert von jedem hat Knoten ist nicht größer (oder nicht kleiner als) der Wert seines übergeordneten Knotens. Hier nehmen wir als Beispiel den maximalen Heap, dh der Wert des Wurzelknotens ist der größte Wert im gesamten Baum und die Werte aller untergeordneten Knoten sind kleiner oder gleich dem Wert des Wurzelknotens.

1.1.2 Vollständige Binärbaumeigenschaften

Mit Ausnahme der untersten Ebene müssen alle anderen Ebenen gefüllt sein und alle Knoten müssen nach links ausgerichtet sein.

Hier wird das folgende Array verwendet, um einen maximalen Heap darzustellen:

[ 16, 14, 10, 8, 7, 9, 3, 2, 4 , 1 ]

Der entsprechende Heap sieht wie folgt aus:

16

/ 14 10 "Methode:


Fügen Sie das neue Element in den am weitesten links stehenden leeren Bereich am unteren Rand des Heaps ein.

Vergleichen Sie das neue Element mit seinem übergeordneten Knoten. Wenn der Wert des neuen Elements größer als der seines übergeordneten Knotens ist, tauschen Sie es aus Positionen der beiden und wiederholen Sie diesen Vorgang, bis das neue Element nicht mehr größer als sein übergeordneter Knoten ist oder die Spitze des Heaps erreicht.

1.2.2 Löschvorgang

Der Vorgang zum Löschen des obersten Elements des Heaps in einem binären Heap wird mithilfe der „Sift Down“-Methode angepasst:

Das oberste Element des Heaps und das Element ganz rechts am Das untere Element des Heaps wird angepasst.

Das ursprüngliche obere Element des Heaps wird Schicht für Schicht verglichen. Wenn sein Wert kleiner als der Maximalwert im untergeordneten Element ist Vergleichen Sie ihn mit dem Maximalwert im untergeordneten Knoten. Die Werte werden ausgetauscht und dieser Vorgang wird wiederholt, bis die Heap-Reihenfolge erfüllt ist.
• 1.3 Anwendungsszenarien

Binärer Heap wird häufig zur Implementierung von Prioritätswarteschlangen und Heap-basierten Sortieralgorithmen wie Heap-Sortierung, TopK-Problem usw. verwendet.

2. Binärer Suchbaum

2.1 Konzept

• Der binäre Suchbaum (BST) ist ein geordneter Baum, der die folgenden Eigenschaften erfüllt:
• 2.1.1 Die Werte aller Knoten im linken Teilbaum sind gleich ist kleiner als der Wert seines Wurzelknotens.
• 2.1.2 Die Werte aller Knoten im rechten Teilbaum sind größer als der Wert seines Wurzelknotens.

2.1.3 Der linke und der rechte Teilbaum sind jeweils auch binäre Suchbäume.

Nehmen Sie den folgenden Baum als Beispiel:

    6
  /   
 2     7

/

1 4 9

   /    /
  3   5 8

Dann handelt es sich um einen binären Suchbaum.

2.2 Grundoperationen

2.2.1 Suchoperation

Die Operation zum Suchen eines Knotens in einem binären Suchbaum besteht im Wesentlichen darin, die Größe des zu findenden Knotenwerts kontinuierlich mit dem aktuellen Knotenwert zu vergleichen und weiterzumachen die rekursive Suche im linken/rechten Teilbaum.

2.2.2 Einfügevorgang

Der Vorgang des Einfügens eines neuen Knotens in einen binären Suchbaum erfordert einen Vergleich beginnend mit dem Wurzelknoten und der Suche nach der Position, an der er eingefügt werden soll. Nach dem Einfügen müssen die Eigenschaften des binären Suchbaums ermittelt werden zufrieden sein.

2.2.3 Löschvorgang

Der Vorgang zum Löschen eines Knotens im binären Suchbaum kann in drei Situationen unterteilt werden:

Der zu löschende Knoten ist ein Blattknoten. Löschen Sie ihn einfach direkt.

Es gibt nur einen ein zu löschender Knoten

Wenn der zu löschende Knoten zwei untergeordnete Knoten hat, ersetzen Sie den Knoten durch den kleinsten Knoten im rechten Teilbaum des Knotens und löschen Sie den kleinsten Knoten im rechten Teilbaum des Knotens.

2.3 Anwendungsszenarien

Binäre Suchbäume werden häufig verwendet, um Szenarien mit Such- und Einfügevorgängen wie Wörterbüchern und Symboltabellen zu implementieren. Die Suchleistung hängt von der Datenverteilung ab.

3. Vergleich von binären Heaps und binären Suchbäumen

3.1 Ähnlichkeiten

• Binäre Heaps und binäre Suchbäume sind beide Binärbäume und haben einige der gleichen Eigenschaften:
• Die Anfangsposition des Wurzelknotens kann sein Jeder Knoten kann zum Implementieren der Prioritätswarteschlange verwendet werden. Die zeitliche Komplexität sowohl des Einfügens als auch des Löschens beträgt O(logn).

3.2 Unterschiede

Es gibt auch einige offensichtliche Unterschiede zwischen binären Heaps und binären Suchbäumen:

3.2.1 Datenverteilung

In einem binären Heap werden Elemente ohne Regelmäßigkeit auf die Knoten verteilt. Dies ist nur notwendig Um sicherzustellen, dass jeder Knoten die Heap-Reihenfolge erfüllt, unterliegt die Größe der Elemente in einem binären Suchbaum einer bestimmten Sortierregel, d. h. sie erfüllt die Eigenschaft „klein links“ und „groß rechts“.

3.2.2 Zugriff auf minimale/maximale Werte

In einem binären Heap kann auf den maximalen/minimalen Wert in O(1)-Zeit zugegriffen werden, d Elemente ist O(logn); in einem binären Suchbaum erfordert das Finden des minimalen/maximalen Werts das Durchlaufen des Teilbaums, und die Zeitkomplexität ist ebenfalls O(logn).

• 3.2.3 Lösch- und Einfügevorgänge
• In einem binären Heap muss jeder Lösch- und Einfügevorgang der Heap-Reihenfolge folgen, dh der zeitlichen Komplexität von O(logn); Knoten und das Einfügen eines neuen Knotens hängen von der Höhe des Baums ab, sodass im schlimmsten Fall eine Zeitkomplexität von O(n) erforderlich sein kann.
• 3.3 Auswahlvorschläge

Bei der Auswahl eines binären Heaps und eines binären Suchbaums müssen Sie entsprechend den spezifischen Bedingungen des Anwendungsszenarios auswählen.

Wenn Sie den Minimal-/Maximalwert schnell ermitteln müssen und keine besonderen Anforderungen an die Größe der Elemente haben, können Sie dem binären Heap Vorrang einräumen.

Wenn Sie Elemente schnell einfügen/löschen müssen und die Größen der Elemente in einer bestimmten Reihenfolge sortiert werden müssen, können Sie die Wahl eines binären Suchbaums in Betracht ziehen.

IV. Fazit

Zusammenfassend sind binäre Heaps und binäre Suchbäume beide wichtige Datenstrukturen und haben in verschiedenen Szenarien ihre eigenen Vor- und Nachteile. Das Verständnis der Konzepte, Grundoperationen und Anwendungsszenarien von binären Heaps und binären Suchbäumen ist für das Schreiben effizienter Programme von großer Bedeutung.

Das obige ist der detaillierte Inhalt vonBinärer Heap und binärer Suchbaum in C++. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!