ノードの平均深さはΘ（LG n）であるのnノード二分探索木の高さに漸近上限を与えます。しかし私は理解できないそれらのいくつかがあります。ここでCLRS運動12.4-2から、それらの一つである：は最近、私はCLRS内のすべての演習を解決しようとしている
は、ツリー内のノードの平均深さは、Θ（LG n）がなく、木の高さであるようなN個のノード上でバイナリ検索ツリーを記述するω（lg n）である。ノードの平均深度がΘ（lg n）であるnノード二分探索木の高さに漸近上限を与える。
誰もがこの問題を解決するためにいくつかのアイデアや参照を共有できますか？ありがとう。
それでは、私たちは木をこのように構築することを想定してみましょう。与えられたn個のノードは、F（n）は、ノードを取り、脇に置き。次に、ルートが、n - f（n）-1ノードの完全なバイナリツリーである左サブツリーと、長さf（n）のチェーンである右サブツリーとを有する完全なバイナリツリーを構築することによって、ツリーを構築する。後でf（n）を選びます。
木の平均深度は？漸近的な拘束が必要なだけなので、n - f（n） - 1が2の完全な累乗、例えば2^k - 1未満であるようなnを選んでみましょう。その場合、この中の高さの合計木の一部は、（IIRC）約k 2^kである1 * 2 + 2 * 3 + 4 * 4 + 8 * 5 + ... + 2 ^（k-1）* 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）= Θ（sqrt（n log n））を選ぶと、1と2が最大限満足されると思います。だから、私は（これについて完全に間違っているかもしれないが）賭けるだろうが、これはあなたが得ることができるほど良いことである。平均深さがΘ（Log n）の高さがΘ（sqrt（n log n））のツリーが得られます。
希望すると便利です。私の数学が途方もない場合は、私に教えてください。今は遅く、私は通常の二重チェックをしていません。 :-)
これは近いですが、完全なツリーがチェーンになっている完全な左のサブツリーを持つよりも、葉ノードの1つから尾を引いた完璧なツリーがほしいと思います。基本的には、できるだけ多くのノードをツリーの最上部近くにパックし、1つの長いチェーンをツリーから外したいとします。 –
@ robertking-うーん、それは良い点です。数学を再構築しても、チェーンからのノードのO（log n）だけが割り引かれるため、これは漸近的にそうなるようには見えません。しかし、私はあなたが正しいと思います。 – templatetypedef
と@ robertkingのポイントは、私はこれが答えであるべきだと思います。 – meteorgan
最初にツリーの高さを最大化します。 （各ノードには1つの子ノードしかないツリーがあるので、長いチェーンが下に向いています）。
平均深度を確認してください。 （明らかに平均深度が高すぎる）。
平均深さが高すぎる一方で、あなたは1で、ツリーの高さを低くしなければなりません。 ツリーの高さを1つずつ減らす方法はたくさんあります。平均の高さを最小にする方法を選択します。 （誘導によって、平均高さを最小にするものを選択するたびに証明されます）。あなたは平均的な高さの要件を下回るまで続けてください。 （例えば、高さと平均深さの公式を誘導を用いて計算する）。
具体的な回答はありますか？私はあなたの推論が大好きで、私はあなたが何に到着したのか不思議です。 – templatetypedef
私はまったく答えがありません。私がそれを試していたら正直言って私はあなたのテクニックを使います。 –
平均値のツリーのすべてのノードの深さを最小にしながらツリーの高さを最大化しようとする場合、明確な最良の形は「傘」形になります。 k個のノードと高さ= lg kを有する完全な2分木であり、ここで0 < k < nは、完全な部分の葉の1つから出てくるn-k個のノードの単一経路、すなわち「テール」と一緒になる。この木の高さはおよそlg k + n - kです。
ここで、すべてのノードの合計深さを計算しましょう。完全な部分のノードの深さの合計はsum [j * 2^j]です。ここで、合計はj = 0からj = lg kまでです。いくつかの代数によって、結果の支配的項は2k lg kです。
次に、tail部分の深さの合計は、sum [i + lg k]によって与えられます。ここで、合計は、i = 0からi = n-kまでです。いくつかの代数によって、結果はおよそ（n-k）lg k +（1/2）（n-k）^ 2になります。
したがって、上の2つの部分を合計し、nで割ると、すべてのノードの平均深さは（1 + k/n）lg k +（n-k）^ 2 /（2n）です。 0 < k < nなので、私たちが何を選んでも、最初の項はO（lg n）です。したがって、第2項がO（lg n）であることを確認するだけでよい。これを行うには、（n-k）^ 2 = O（n lg n）またはk = n-O（sqrt（n lg n））が必要です。この選択で、木の高さは
LGのK + N - = O（SQRT（N LGのN））
これは通常O（LG n）がより漸近的に大きく、漸近的であるK平均深度をO（lg n）に保ちながらツリーを作ることができます。
'w'は小文字のオメガを意味します。 – Gumbo
@Gumboはい、ありがとう。 – meteorgan