Das

Ich versuche zu beweisen, dass ein binärer Heap mit Knoten genau Blätter hat, , der Heap ist folgendermaßen aufgebaut: $n$ $\left\lceil \frac{n}{2} \right\rceil$

Jeder neue Knoten wird per Perkolation eingefügt . Dies bedeutet, dass jeder neue Knoten beim nächsten verfügbaren untergeordneten Knoten erstellt werden muss. Damit meine ich, dass Kinder von links nach rechts und von unten nach unten gefüllt sind. Zum Beispiel der folgende Heap:

    0
   / \
  1   2

würde haben in dieser Reihenfolge gebaut wurden: 0, 1, 2. (Die Zahlen sind nur Indizes, sie geben keinen Hinweis auf die tatsächlichen Daten in diesem Knoten gehalten.)

Dies hat zwei wichtige Auswirkungen:

Es kann keinen Knoten auf Ebene ohne dass Ebene vollständig gefüllt ist $k+1$ $k$
Da untergeordnete Elemente von links nach rechts erstellt werden, dürfen zwischen den Knoten auf Ebene keine "Leerzeichen" oder Situationen wie die folgenden vorhanden sein: $k+1$
```
    0
   / \
  1   2
 / \   \
3  4    6
```

(Dies wäre meiner Definition nach ein illegaler Heap.) Ein guter Weg, sich diesen Heap vorzustellen, ist die Array-Implementierung eines Heaps, bei der es keine "Sprünge" zwischen den einzelnen Arrays geben kann.

Also dachte ich, Induktion wäre wahrscheinlich ein guter Weg, um dies zu tun ... Vielleicht muss sich etwas mit geraden und ungeraden Fällen für n befassen. Eine Induktion, die die Tatsache verwendet, dass gerade Heaps, die auf diese Weise erstellt wurden, einen internen Knoten mit einem untergeordneten Knoten für ein gerades n und keinen solchen Knoten für ein ungerades n haben müssen. Ideen?

data-structures binary-trees varatis
quelle

@ DaveClarke: Nicht ganz; Die damit verbundene Frage ist das Ergebnis eines Missverständnisses über die Teile der Redaktion, die dort als Referenz hinterlassen wurden.

Raphael

Haben Sie versucht, über die Knotennummer bzw. Anzahl der Einfügungen?

Raphael

@ DaveClarke: Warum? Es ist eine berechtigte Frage an sich, imho.

Raphael

Übrigens hat die Frage nichts mit Haufen zu tun. Die Behauptung gilt für jeden vollständigen Binärbaum

Ran G.

Antworten:

Wenn ich Ihre Frage richtig bekommen, ist der erhaltene Haufen nur ein binären Baum bestellt, wo in geordneten meine ich , dass die - ten Stufe kann erst nach dem belegt werden Ebene vollständig gefüllt ist, und jede Ebene von links besetzt nach rechts, ohne zu überspringen. $k$ $k-1$

Dann geht der Beweis so.

Ein perfekter Baum der Tiefe hat genau Knoten. $k$ $2^{k+1}-1$
Angenommen, der Haufen erreicht die Tiefe . Somit
1. bis Stufe der Baum perfekt (und hat dort Knoten) $k-1$ $2^k-1$
2. $n-2^k+1$
$k$
$2^{k-1}$ $k-1$ $\left\lceil \frac{n-2^{k}+1}{2} \right\rceil$ $2^{k-1} - \left\lceil\frac{n-2^{k}+1}{2}\right\rceil$
$n - 2^{k} + 1 + 2^{k - 1} - ⌈ \frac{n - 2^{k} + 1}{2} ⌉$ $n-2^k+1 + 2^{k-1} - \left\lceil\frac{n-2^{k}+1}{2}\right\rceil$

Ran G.
quelle

Beachten Sie, dass voll unterscheiden sich von kompletten unterscheiden sich von perfekt Binärbäumen. Unglückliche, mehrdeutige und inkonsistente Wortwahl, aber was können Sie dagegen tun? Ich denke, es macht Sinn, sich an die Definition von Wikipedia zu halten, da die meisten zuerst dort suchen werden.

Raphael

Oh, wow, ich kannte diese Begriffe nicht einmal. Vielen Dank für den Hinweis.

Ran G.

"bis zum Level k − 1 ist der Baum perfekt (und hat dort 2 ^ k − 1 Knoten)" und "Von den 2 ^ (k − 1) Knoten auf dem Level k − 1 scheinen" widersprüchliche Aussagen zu sein, oder vermisse ich etwas

adrian h.

2^{k} - 1

$2^k-1$

2^{k - 1}

$2^{k-1}$

2^{k - 1} + 2^{k - 2} + . . .

$2^{k-1}+2^{k-2}+...$

Ah du hast vollkommen recht, vielen Dank für die Klarstellung!

adrian h.

Hier ist ein einfacher logischer Beweis.

$n^{th}$ $\lfloor{n/2}\rfloor$ $\lfloor n/2 +1\rfloor)^{th}$ $\lfloor{n/2}\rfloor$

$\lfloor(n/2)\rfloor$ $\lceil(n/2)\rceil$

Zubin Pahuja
quelle

Ganz intuitive und klare Erklärung. Vielen Dank.

18.11.15 Uhr