Vergleichen Heap und Baum/

Question

Ich bin ein Neuling in Datenstruktur.

Also fragte ich mich, was ist der Unterschied zwischen Haufen und Baum?

Ich sehe auch auf vielen Dokumenten, dass Heap von Array implementiert wird, und Baum ist Poniters. Ist das richtig?

Und wenn wir Baum oder Haufen verwenden müssen?

Answer 1

Ein Baum in der Informatik ist ein abstrakter Datentyp, der eine Baumstruktur darstellt. Ein Knoten einer Wurzel kann aus untergeordneten Knoten bestehen, wobei jeder untergeordnete Knoten ebenfalls Bäume sind.

Beachten Sie, dass nicht alle Bäume binäre Suchbäume sind. Ein binärer Suchbaum ist ein Baum mit zwei Eigenschaften festlegen:

• Jeder Knoten hat höchstens 2 Kinder

• Das linke Kind ist weniger als die Mutter

• Das rechte Kind größer ist als die Eltern

Eine andere besondere Art von Baum ist ein Haufen. Ein Heap ist speziell, weil er die folgende Eigenschaft aufweist:

• Jeder Knoten in der Struktur ist immer kleiner oder gleich jedem untergeordneten Knoten.

Nun, wie Sie einen Baum zu implementieren, ist Ihnen überlassen. Ein Baum kann durch Zeiger/Referenzen implementiert werden; Ein Knoten speichert einen Wert und Zeiger/Referenzen auf seine Kinder.

Ein Baum kann auch als Array implementiert werden. Der Elternteil befindet sich auf dem Index 0. Wenn es höchstens d Kinder gibt, dann ist das i Kind des Elternteils bei Index k bei Index d*k+i. Wenn alles gleich ist, wollen wir mit Arrays arbeiten, da Arrays im Vergleich zu Traversierungszeigern extrem schnell sind.

Ein binärer Suchbaum wird jedoch normalerweise mithilfe von Zeigern implementiert. Dies hat zwei Gründe.

1. Wenn dies ein Array wäre, müsste es immer genügend Platz für das Worst-Case-Szenario reservieren. Mit anderen Worten, wenn Ihr binärer Suchbaum die Höhe h hat, muss Ihr Array die Größe O(2^h) haben. Das ist schlecht, weil Ihr Baum nur aus h Elementen bestehen könnte.

2. Löschen ist auch sehr zeitaufwendig. Wenn Sie den Stammknoten löschen, müssen Sie einen ganzen Teilbaum nach oben verschieben, um ihn zu ersetzen. Der Grund, warum wir einen binären Suchbaum überhaupt verwenden wollten, war die Gewährleistung von O(log n) Operationen, die wir mit einem Array nicht bekommen.

Ein Haufen auf der Hand, in der Regel als ein Array implementiert wird, weil sein Baum immer vollständig ausgeglichen ist (jeder Knoten d Kinder außer vielleicht bei den Blättern) Dies bedeutet, dass es sehr wenig Platz verschwendet wird, so dass wir gewonnen mach dir keine Sorgen um 1).Darüber hinaus beeinflusst die Löschung für Haufen die Struktur des Baumes nicht drastisch, wie dies bei binären Suchbäumen der Fall ist, so dass 2) auch nicht gilt.