最近、私はCLRSのすべての演習を解決しようとしています。しかし、私が理解できないものがいくつかあります。CLRS演習12.4-2からのそれらの1つは次のとおりです。
ツリー内のノードの平均深さがΘ（lg n）であるが、ツリーの高さがω（lg n）であるように、n個のノードで二分探索木を記述します。ノードの平均深さがΘ（lgn）であるnノード二分探索木の高さに漸近的な上限を与えます。
この問題を解決するためのアイデアや参考資料を誰かが共有できますか？ありがとう。
3166 次
3 に答える
6
したがって、この方法でツリーを構築するとします。n個のノードが与えられた場合、f（n）個のノードを取り、それらを脇に置きます。次に、ルートにn --f（n）-1ノードの完全な二分木である左側のサブツリーと長さf（n）のチェーンである右側のサブツリーがある完全な二分木を構築することによってツリーを構築します。後でf（n）を選択します。
では、木の平均的な深さはどれくらいですか？漸近境界が必要なので、n --f（n）-1が2の累乗数より1小さい、たとえば2 ^ k-1になるようにnを選択します。この場合、この高さの合計はツリーの一部は1*2 + 2 * 3 + 4 * 4 + 8 * 5 + ... + 2 ^（k-1）* kであり、これは（IIRC）約k 2^kです。 （n --f（n））log（n --f（n））kの選択による。ツリーの他の部分では、合計の深さは約f（n）^2です。これは、平均パス長が約（（n --f（n））log（n --f（n））+ f（n）^ 2）/nであることを意味します。また、木の高さはf（n）です。したがって、平均深度O（log n）を維持しながら、f（n）を最大化する必要があります。
これを行うには、次のようなf（n）を見つける必要があります。
- n-f（n）=Θ（n）、または分子の対数項が消え、高さが対数ではない場合、
- f（n）^ 2 / n = O（log n）、または分子の2番目の項が大きくなりすぎます。
f（n）=Θ（sqrt（nlog n））を選ぶと、1と2が最大に満たされると思います。だから私は（これについては完全に間違っているかもしれませんが）これがあなたが得ることができるのと同じくらい良いことを賭けたいと思います。平均深さΘ（Logn）を持つ高さΘ（sqrt（nlog n））のツリーを取得します。
お役に立てれば！私の数学がかなり離れている場合は、私に知らせてください。今は遅く、いつものダブルチェックをしていません。:-)
于 2012-02-13T08:48:44.883 に答える
0
まず、木の高さを最大化します。（各ノードに子ノードが1つしかないツリーがあるため、長いチェーンが下に向かっています）。
平均深度を確認してください。（明らかに、平均深度は高すぎます）。
平均的な深さが高すぎる場合は、木の高さを1つ下げる必要があります。木の高さを1つ下げる方法はたくさんあります。平均の高さを最小にする方法を選択してください。（帰納法によって、毎回平均高さを最小にするものを選択する必要があることを証明してください）。あなたが平均的な高さの要件を下回るまで続けてください。（たとえば、誘導を使用して、高さと平均深度の式を計算します）。
于 2012-02-13T10:06:16.403 に答える
0
ツリーのすべてのノードの平均深度を最小化しながらツリーの高さを最大化しようとしている場合、明確な最良の形状は「傘」形状になります。たとえば、kノードで高さ=lgkの完全な二分木です。ここで、0 <k <nと、フルパーツの葉の1つから出てくるnkノードの単一パスまたは「テール」。この木の高さはおおよそlgk+n-kです。
次に、すべてのノードの合計深度を計算しましょう。完全な部分のノードの深さの合計はsum[j* 2 ^ j]であり、合計はj=0からj=lgkまで取得されます。いくつかの代数によると、結果の支配的な項は2klgkです。
次に、テール部分の深さの合計はsum [i + lg k]で与えられます。ここで、合計はi=0からi=nkになります。代数によって、結果はおよそ（nk）lg k +（1/2）（nk）^2になります。
したがって、上記の2つの部分を合計し、nで割ると、すべてのノードの平均深度は（1 + k / n）lg k +（nk）^ 2 /（2n）になります。0 <k <nであるため、ここでの最初の項は、どのkを選択しても、O（lg n）であることに注意してください。したがって、2番目の項がO（lg n）であることを確認するだけで済みます。そのためには、（nk）^ 2 = O（n lg n）、またはk = n --O（sqrt（n lg n））が必要です。この選択では、木の高さは
lg k + n-k = O（sqrt（n lg n））
これは、通常のO（lg n）よりも漸近的に大きく、平均深度をO（lg n）に保ちながら、ツリーを作成できる最も高いものです。
于 2018-01-01T03:49:50.137 に答える