スプレー ツリー内の各ディクショナリ操作は、スプレー操作を使用して、ノードをツリーのルートに移動します。このスプレイ操作の償却効率は、通常、潜在的な方法で分析され、オンラインの多くのソース (ウィキペディアを含む) ページで説明されています。このスプレー操作の償却時間は、O(m lg n) として報告されます。
ただし、挿入、削除などの完全な辞書操作の実際の分析はどこにもありません...これらの各操作は、スプレイ操作に加えて、ツリーを下方向に検索して、挿入するノードの正しい位置を見つけますまたは削除します。そのノードを見つけた後でのみ、スプレー操作を開始できます。
人々は次のような発言をする傾向があります。
- 「スプレーツリー操作の複雑さは、関連するスプレーの複雑さと同じです」
- [「私たちの分析では、検索、挿入、または削除を実行する時間は、関連するスプレイの時間に比例することに注意してください」], p. Goodrich の本の 456「C++ のデータ構造とアルゴリズム」
2 つの質問があります。
- 検索を実行する時間がスプレイの時間に比例するというこの結論をどのように出すことができますか? この種のことは、ノードへの下方トラバーサルの時間もスプレイのタイに比例することを意味しますか?
- 下向きトラバーサルの償却時間効率はどれくらいですか? 下向きのトラバーサルを行うだけでツリーの構造を変更しないという理由だけで、それは定数ですか (そのため、可能性は同じままです)。そして、これは最悪の場合なので、= N よりも一定ではありませんか?
どうすればこの結論を下すことができるでしょうか。