0

素結合では、高さがそれぞれ h1 と h2 である 2 つのツリーをマージする必要があるとします。この手法を使用すると、結果のマージされたツリーの高さは、h1 が h2 と等しくない場合は max(h1, h2) になり、h1 == h2 の場合は h1+1 になります。初期状態から始まるマージ操作の任意のシーケンスの後にこの手法を使用すると、「k」個のノードを含むツリーの高さは最大 (logk のフロア) になります。これは帰納法により次のように証明される.

ベース: k=1 の場合、高さは 0. 0<= (floor(log 1))

誘導ステップ: を考えk >1て、仮説により、 となるすべての m に対して定理が真であるとし1<=m<kます。kノードを含むツリーは、2 つの小さなサブツリーをマージすることによって取得できます。これらの 2 つの小さなツリーには、一般性を失うことなく想定できる「a」ノードと「b」ノードがそれぞれ含まれているとしa<=bます。したがってa>=1、初期状態から始まるノードが 0 のツリーを取得する方法はなく、k=a+b です。そして、、、 両方、 、、 したがって、 と続きますa<=k/2b<=k+1。k>1k/2 < k(k-1) < ka<kb<k

上記の私の質問は

  1. 上記の「a<=k/2 and b<=k+1」というステートメントをどのようにして得たのか。

ありがとう！

4

1 に答える 1

1

と仮定しましょうa > k/2、それb > k/2から、b>=a。次にa + b > k/2 + k/2。したがって、a + b > k。しかし、私たちは持っていk = a + bます！a > k/2したがって、それは矛盾につながり、したがって誤りであるという仮定。これは「それを証明する」a <= k/2。

英語で：k2つの部分に分割したa場合、半分が大きいb場合は、の半分未満である必要があります。bak

于 2011-10-03T11:45:10.127 に答える