スプレイ ツリーについて読んでいるときに、ウィキペディアでスプレイ ノード 'X' のランクと償却コストに関する表現を見つけました。{ジグジグまたはジグザグ操作の償却コストを次のように制限できます。
amortized cost = cost + P(tf) - P(ti) ≤ 3(rankf(x) - ranki(x)),
ここで、x はルートに向かって移動されるノードであり、添字 "f" と "i" はそれぞれ操作の後と前を示します。スプレー操作全体を合計すると、これは O(log n) である 3(rank(root)) にテレスコープされます。ジグ操作は多くても 1 つなので、これは定数を追加するだけです。}
私はこれを解釈することができません。上記の詳細を説明してください。可能であれば、いくつかの例を挙げてください。
スプレー ツリーの他の定理の説明へのリンクを提供してください。
ありがとう
静的なスプレー木の単純な償却分析を実行したいとします。ウィキペディアの例のように、1つの基本的なジグザグを取る場合。それは最悪のシナリオです。そして、あなたは持っています：
P（tf）-P（ti）≤3（rankf（x）-ranki（x））
証明：ウィキペディアで使用されている表記法では、変換後のツリーのルートにxがあるため、次のように簡単に取得できます。
ランクf（x）> =ランクf（g）およびランクf（x）> =ランクf（f）
したがって、
Ptf =ランクf（x）+ランクf（g）+ランクf（p）<= 3 *ランクf（x）
変換の前にxを使用して反対の推論を行うと、次のようになります。
Pti =ranki（x）+ranki（g）+ranki（p）> = 3 *ranki（x）
これを操作全体に一般化して、償却原価を計算できます。
私はそれがあなたの結果を証明したと思います、しかし私はそれがあなたが探していたものであるかどうかわかりません。