Randomisierter meldepflichtiger Haufen - erwartete Höhe

9

Randomisierte meldepflichtige Heaps haben eine Operation "Meld", mit der wir dann alle anderen Operationen definieren, einschließlich Einfügen.

Die Frage ist, wie hoch ist die erwartete Höhe dieses Baums mit Knoten?n

Satz 1 von Gambin und Malinkowski, Randomized Meldable Priority Queues (Proceedings of SOFSEM 1998, Lecture Notes in Computer Science, Bd. 1521, S. 344–349, 1998; PDF ) gibt die Antwort auf diese Frage mit Beweis. Ich verstehe jedoch nicht, warum wir schreiben können:

E[hQ]=12((1+E[hQL])+(1+E[hQR])).

Für mich ist die Höhe des Baumes

hQ=1+max{hQL,hQR},

was ich erweitern kann:

E[hQ]=1+E[max{hQL,hQR}]=1+kP[max{hQL,hQR}=k].

Die Wahrscheinlichkeit, dass das Maximum einer Höhe von zwei Teilbäumen gleich k kann unter Verwendung des Gesetzes der Gesamtwahrscheinlichkeit umgeschrieben werden:

P[max{hQL,hQR}=k]=P[max{hQL,hQR}=khQLhQR]P[hQLhQR]+P[max{hQL,hQR}=khQL>hQR]P[hQL>hQR]=P[hQR=khQLhQR]P[hQLhQR]+P[hQL=khQL>hQR]P[hQL>hQR].

Am Ende bekomme ich also:

E[hQ]=1+k{P[hQR=khQLhQR]P[hQLhQR]+P[hQL=khQL>hQR]P[hQL>hQR]}.

Hier stecke ich fest. Ich kann sehen, dass mehr oder weniger gleich ist (wir brauchen jedoch höchstens ) . Aber außer dass nichts von Anfang an zur Formel führt.P[hQL>hQR]1212

Die Höhen der Teilbäume scheinen für mich nicht unabhängig zu sein.

Danke für die Hilfe.

Mateusz Wyszyński
quelle

Antworten:

4

In der Zeitung ist nicht die Höhe. Es ist die Länge eines zufälligen Weges von der Wurzel in einem vollständigen Binärbaum (sie bestehen darauf, dass jedes Blatt "Null" ist), also ist der Ausdruck, den sie haben, das Richtige.hQ

Sie können auch eine Induktion vermeiden. Die Wahrscheinlichkeit, an einem bestimmten Blatt der Tiefe enden, beträgt nur . Die erwartete Länge des Spaziergangs ist alsod2d

leaves(Q)depth()2depth()

welche die Entropie einer Verteilung eine Menge von Größe.|leaves(Q)|

Louis
quelle
1
Können Sie genauer erklären, warum ich die Induktion nicht verwenden muss? Ich stimme der Formel für die erwartete Länge zu. Ich verstehe nur nicht, warum es O (logn) sein sollte? Was meinst du mit Entropie einer Verteilung auf Strings?
Mateusz Wyszyński
Da die Entropie einer Verteilung auf einem Satz der Größe bekanntermaßen durch eine gleichmäßige Verteilung maximiert wird, ist sie in diesem Fall . nlogn
Louis