Wie zu beweisen, dass sich Kinder in Heap-Datenstruktur befinden: 2 * n und 2 * n + 1? - Baum, Binärbaum, Haufen

Dies ist keine Hausaufgabe, ich habe heute die Struktur von Heap-Daten gelernt und weiß nicht, wie ich beweisen soll, dass diese Beziehung wahr ist. Danke.

Antworten:

3 für die Antwort № 1

Durch Induktion beweisen:

1. Kinder der Wurzel (1) -> Kind1 = 2 * 1 = 2, Kind2 = 2 * 1 + 1 = 3 wahr
2. Angenommen Kinder des k-ten Elements sind -> Kind1 = 2k, Kind2 = 2k + 1
3. Beweisen Kinder von (k + 1) -ten Elementen sind child1 = 2 * (k + 1), child2 = 2 (k + 1) + 1 (Beweisen Sie dies)

Beweis von 3: Da Kinder von k-ten Elementen dann bei 2k und 2k + 1 sind (basierend auf der Annahme), sind die nächsten beiden Elemente danach 2k + 2 und 2k + 3.

2k + 2 = 2 (k + 1) (erstes Kind für k + 1 ist bewiesen) (a)

2k + 3 = 2k + 2 + 1 = 2 (k + 1) + 1 (zweites Kind für k + 1 ist bewiesen) (b)

von (a) & (b) -> also 3 ist gültig, also Kind des Elements n sind 2n und 2n + 1

---

0 für die Antwort № 2

Hier ist ein Beweis ohne Induktion, der aus meiner Sicht intuitiver und aufschlussreicher ist. Hier sind 4 mentale Schritte, die diese Beziehung zu mir belegen.

Machen Sie den Baum flach.

Lassen Sie uns alle Eckpunkte eines Baums auf folgende Weise aufzählen:

So sehen diese Verices im Array aus:

Geschwister in Reihe trennen.

Wir können feststellen, dass alle zwei aufeinander folgenden Knoten (mit Ausnahme des ersten) untergeordnete Knoten eines gemeinsamen Scheitelpunkts sind:
1 [ 2 3 ] [ 4 5 ] [ 6 7 ] [ 8 9 ]

Erstellen Sie dieses Array anders.

Nun wollen wir in umgekehrter Reihenfolge denken. Was ist, wenn wir ein Array von Paaren haben: [(2, 3), (4, 5), (6, 7), (8, 9)] und wir wollen sie in a aggregieren einzelnes Array?

Nehmen wir an, wir haben bereits die ersten 3 Paare platziert:
[ 2 3 ] [ 4 5 ] [ 6 7 ]

Was wird der Index der Nummer 8 im letzten Array sein? Wir wissen, dass wir bereits 3 Paare platziert haben und sie am Anfang 3 * 2 = 6 Plätze belegt haben, so dass wir den 7. Platz belegen werden.

Wenn wir die Platzierung von Paaren codieren, sieht es so aus:

pair<int, int> pairs[4] = { {2, 3}, {4, 5}, {6, 7}, {8, 9} };
int aggregate[2 * 4];
for (int i = 0; i < 4; i++)
{
aggregate[2 * i] = pairs[i].first;
aggregate[2 * i + 1] = pairs[i].second;
}

Der Schlüsselteil ist dieser Index des Arrays Aggregat[2 * i]. In diesem Code wird deutlich, warum wir mit multiplizieren 2 - Wir machen es, weil wir müssen überspringen der Vorherige i - 1 Paare.

Kombinieren Sie die Abflachung des Baumes und die Aggregation von Paaren

Jetzt müssen wir die Entsprechung zwischen sehenErstellen eines aggregierten Array von Paaren und Abflachen eines Binärbaums. Jedes Geschwisterpaar hat einen Elternteil. Wenn zwei Geschwister (2, 3) und (4, 5) nebeneinander angeordnet sind, sind auch ihre Eltern benachbart. Geschwister (2, 3) haben Eltern 1, Geschwister (4, 5) haben Eltern 2, Geschwister (6, 7) haben Eltern 3. Also die Eltern ist wie ein Index in diesem Array von Paaren pairs[4] = { (2, 3), (4, 5), (6, 7), (8, 9) } und wenn wir verwenden 2 * i um auf sein linkes Kind zuzugreifen, können wir uns vorstellen überspringen i - 1 Paare von Kindern, die durch vorherige Eckpunkte generiert wurden.

---