7

CLRSアルゴリズムの本からこの演習のヒントが必要です。

高さhの二分探索木でどのノードから開始しても、Tree-Successorへのk回の連続呼び出しにはO（k + h）時間がかかることを証明します。

4

2 に答える 2

8
  • TREE-SUCCESSORを連続して呼び出した後x、開始ノードを開始ノードとzし、終了ノードとします。k
  • とを含むp間の単純な道にしましょう。xz
  • とその訪問yの共通の祖先になりましょう。xzp
  • の長さpは最大2hで、ですO(h)。
  • outputそれらの値が間にx.keyあり、z.key包括的である要素にしましょう。
  • のサイズはoutputですO(k)。
  • kTREE-SUCCESSORへの連続呼び出しの実行では、にあるノードが訪問され、ノードのpほかに、ノードのサブツリーが訪問されると、そのすべての要素がになります。xyzpoutput
  • したがって、実行時間はO(h+k)です。
于 2012-09-15T18:38:39.520 に答える
3

ヒント：小さな例を考え出し、結果を観察し、理由を推定してみてください。

開始するには、ここで考慮すべきことがいくつかあります。

特定のノードから開始し、Tree-Succcesorへのk回の連続呼び出しは、部分的なツリーウォークを構成します。このウォークはいくつの（少なくともそして多くても）ノードを訪問しますか？（ヒント：key（x）について考えてください）。エッジは最大で2回訪問されることに注意してください（なぜですか？）。

最後のヒント：結果はO(2h+k)です。

于 2011-12-10T06:04:02.160 に答える