amortisierte Kosten des Spreizbaums : Kosten + P(tf) - P(ti) ≤ 3(rankf(x) - ranki(x)) Erklärung

Question

Bei der Lektüre von Spreizbäumen fand ich in Wikipedia einen Ausdruck über den Rang des Spreizknotens 'X' und die amortisierten Kosten. Er wird angegeben als, { Wir können die amortisierten Kosten jeder Zig-Zig- oder Zig-Zag-Operation durch begrenzen:

amortized cost = cost + P(tf) - P(ti)  3(rankf(x) - ranki(x)),

wobei x der Knoten ist, der zur Wurzel hin verschoben wird, und die Indizes "f" und "i" nach bzw. vor der Operation stehen. Aufsummiert über die gesamte Splay-Operation ergibt dies 3(rank(Root)), was O(log n) ist. Da es höchstens eine Zig-Operation gibt, kommt nur eine Konstante hinzu.}

Ich bin nicht in der Lage, dies zu interpretieren. Kann mir jemand die obigen Ausführungen im Detail erklären. Wenn möglich mit einigen Beispielen.

Bitte geben Sie einige Links für die Erklärungen zu anderen Theoremen von Spreizbäumen an

Danke

Answer 1

Sie möchten eine einfache Amortisationsanalyse von statischen Spreizbäumen durchführen. Nehmen Sie ein einfaches Zickzack, wie das Beispiel auf Wikipedia, das den schlimmsten Fall darstellt. Und Sie haben :

P(tf) - P(ti) 3(rankf(x) - ranki(x))

Beweise: Mit der auf Wikipedia verwendeten Notation, da x nach der Transformation an der Wurzel des Baumes steht, erhält man leicht:

rankf(x)>= rankf(g) und rankf(x)>= rankf(f)

also,

Ptf = rankf(x)+rankf(g)+rankf(p) <= 3*rankf(x)

Bei umgekehrter Betrachtung mit x vor der Transformation erhält man :

Pti = ranki(x)+ranki(g)+ranki(p) >= 3*ranki(x)

können Sie dies auf den gesamten Betrieb verallgemeinern, um die amortisierten Kosten zu berechnen.

Ich schätze, es beweist Ihr Ergebnis, aber ich bin nicht sicher, ob es das ist, wonach Sie gesucht haben.