私は二分木と配列リスト表現についていくつかの研究を行ってきました。最悪の場合の空間の複雑さが O(2^n) であることを理解するのに苦労しています。具体的には、この本では、スペースの使用量は O(N) (N = 配列サイズ) であり、最悪の場合は O(2^n) であると述べています。各ノードには O(2^n) ではない 2 つの子 (インデックス) があり、n = no であるため、最悪の場合は 2n になると考えていました。要素の。
たとえば、7 つのノードを持つバイナリ ツリーがある場合、スペースは 2^n = 128 ではなく 2n = 14 になります。
これは、配列に対するヒープの実装です。どこ
A[1..n]
left_child(i) = A[2*i]
right_child(i) = A[2*i+1]
parent(i) = A[floor(i/2)]
さあ、宇宙へ。直感的に考え、
同様に、最初の要素 n=1、location=A[1] を挿入すると、
n=2 @A[2] left_child(1)
n=3 @A[3] right_child(1)
n=4 @A[4] left_child(2)
n=5 @A[5] right_child(2)
ほら、n番目の要素が に入りA[n]ます。したがって、空間の複雑さはO(n)です。
コーディングするときは、最後に挿入する要素をプラグインするだけで、 atA[n+1]と言って、それが の子であると言うだけですfloor((n+1)/2)。
参照: http://en.wikipedia.org/wiki/Binary_heap#Heap_implementation
ヒープはほぼ完全なツリーであるため、ツリー内の要素の総数は になり、これが必要な配列の長さになります。参考：これ2h-1 < n <= 2h+1-1
バイナリ ツリーの最悪の場合のスペースの複雑さは O(n) (質問では O(2^n) ではありません) ですが、配列を使用してバイナリ ツリーを表すと、ほぼ完全なバイナリ ツリーであればポインターのスペースを節約できます。
これは、特にヒープの実装において、完全またはほぼ完全なバイナリ ツリーに通常使用される配列表現で任意のバイナリ ツリーを格納することを指していると思います。
この表現では、ルートは0配列の index に格納され、 index を持つ任意のノードについてn、その左と右の子はそれぞれインデックス2n+1と2n+2に格納されます。
どのノードにも適切な子がない縮退ツリーがある場合 (ツリーは実質的にリンクされたリストです)、最初の項目は index に格納されます0, 1, 3, 7, 15, 31, ...。一般に、nこのリストの 4 番目の項目 ( から始まる0) は index に格納されるため、この場合、配列表現にはスペースが必要です。2n-1θ(2n)