Intuition hinter Spreizbaum (selbst ausbalancierende Bäume)

Question

Ich lese die Grundlagen von Spreizbäumen. Die amortisierten Kosten eines Betriebs sind O (log n) über N -Operationen. Eine grobe Grundidee ist, dass Sie beim Zugriff auf einen Knoten ihn spreizen, dh Sie nehmen ihn zur Wurzel. Wenn Sie das nächste Mal schnell zugegriffen werden und auch wenn der Knoten tief war, verbessert er die Balance-Ness des Baumes.

Ich verstehe nicht, wie der Baum für diese Beispieleingabe amortisiert O (log n) durchführen kann:

Sagen Sie, ein Baum von N -Knoten ist bereits gebaut. Meine nächsten N -Operationen sind n Reads. Ich greife auf einen tiefen Knoten in der Tiefe n zu. Dies dauert O (n). Stimmt, dass der Baum nach diesem Zugang ausgeglichen wird. Aber sagen Sie jedes Mal, wenn ich auf den aktuellsten tiefen Knoten greife. Dies wird niemals weniger als O (log n) sein. Wie können wir dann jemals den ersten kostspieligen O (N) -Orgo (N) ausgleichen und die amortisierten Kosten jeder Lektüre als O (log n) mitbringen?

Vielen Dank.

Answer 1

Angenommen, Ihre Analyse ist korrekt und die Operationen sind O(log(n)) per Zugang und O(n) das erste Mal...

Wenn Sie immer auf das Bottommost-Element zugreifen (mit einer Art von Worst-Case-Orakel), eine Sequenz von a Zugriffe dauern O(a*log(n) + n). Und so sind die amortisierten Kosten pro Betrieb O((a*log(n) + n)/a)=O(log(n) + n/a) oder nur O(log(n)) Mit der Anzahl der Zugriffe wächst groß.

Dies ist die Definition der asymptotischen Durchschnittsfallleistung/Zeit/Raum, auch als "amortisierte Leistung/Zeit/Raum" bezeichnet. Sie denken versehentlich, dass eine einzige O(n) Schritt bedeutet, dass alle Schritte zumindest sind O(n); Ein solcher Schritt ist auf lange Sicht nur eine konstante Menge an Arbeit; das O(...) Versteckt, was wirklich los ist, was die Grenze von nimmt [total amount of work]/[queries]=[average ("amortized") work per query].

Dies wird niemals weniger als O (log n) sein.

Es muss sein, um zu bekommen O(log n) Durchschnittliche Leistung. Um Intuition zu erhalten, kann die folgende Website gut sein: http://users.informatik.uni-halle.de/~jopsi/dinf504/chap4.shtml Speziell das Bild http://users.informatik.uni-halle.de/~jopsi/dinf504/splay_example.gif - Es scheint, dass während der Ausführung der O(n) Operationen bewegen Sie den Pfad, den Sie durchsucht haben, um ihn nach oben auf dem Baum zu knüpfen. Sie haben wahrscheinlich nur eine begrenzte Anzahl von solchen O(n) Operationen, die ausgeführt werden müssen, bis der gesamte Baum ausgeglichen ist.

Hier ist eine andere Möglichkeit, darüber nachzudenken:

Betrachten Sie einen unausgeglichenen binären Suchbaum. Du kannst ausgeben O(n) Zeit ausbalancieren. Vorausgesetzt, Sie fügen keine Elemente hinzu*, nimmt es nimmt O(log(n)) Amortisierte die Zeit pro Abfrage, um ein Element zu holen. Die Ausgleichsanpassungskosten sind in den amortisierten Kosten enthalten, da sie effektiv eine Konstante ist, die, wie in den Gleichungen der Antwort gezeigt, durch die unendliche Menge an Arbeit, die Sie leisten, verschwindet (wird in Zittern). (*Wenn Sie Elemente hinzufügen, brauchen Sie einen selbstausgleichenden binären Suchbaum, von dem einer ein Spreizbaum ist.)