저는 이진 트리와 배열 목록 표현에 대한 연구를 해왔습니다. 나는 최악의 공간 복잡성이 O (2^n)라는 것을 이해하기 위해 고심하고있다. 특히이 책에서는 공간 사용량이 O (N) (N = 배열 크기)라고 말하면서 최악의 경우 O (2^n)입니다. 나는 각 노드가 O (2^n)가 아닌 두 개의 자식 (인덱스)을 가지고 있기 때문에 최악의 경우 2n이 될 것이라고 생각했을 것이다. 여기서 n은 no이다. 요소의이진 트리 배열 목록 표현
예 I 7 개 노드 이진 트리 있었다면, 그 공간은 2N 것이다 = 14되지 2^N = 128 
를 참조하십시오이 배열에 힙 구현입니다. Where
A[1..n]
left_child(i) = A[2*i]
right_child(i) = A[2*i+1]
parent(i) = A[floor(i/2)]
이제 우주로 오십시오.
당신이 위치 = 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]로 이동합니다, 첫 번째 요소 N = 1을 삽입 할 때, 직관적으로 생각하십시오. 따라서 공간 복잡도는 O(n)입니다.
플러그인을 코딩 할 때 마지막에 삽입 할 요소는 A[n+1]이고 말은 floor((n+1)/2)입니다.
를 참조하십시오 http://en.wikipedia.org/wiki/Binary_heap#Heap_implementation
힙이 거의 완전한 나무입니다 트리의 요소 때문에 총 수는 2h-1 < n <= 2h+1-1 될 것이며,이 배열의 길이는 당신이 필요합니다 것입니다. 참조 : this
이진 트리의 최악의 공간 복잡도는 O (인 n) (O (2^n) 질문에),하지만 이진 트리를 나타 내기 위해 배열을 사용하면 거의 완전한 이진 트리라면 포인터의 공간을 절약 할 수 있습니다.
I 이것이 특히 힙의 구현 예에서, 정상적으로 완료 또는거의 완전한 이진 트리에 사용되는 배열 표현에 임의 이진 트리를 저장 지칭 생각한다. 이 표현
이 루트는 어레이 인덱스0에 저장되고 인덱스 n 어떤 노드에, 그 좌측 및 우측 아이는 각각 인덱스 2n+1 및 2n+2에서 저장된다. 올바른 노드가없는 퇴화 트리가있는 경우 (트리는 사실 링크 된 목록 임), 첫 번째 항목은 0, 1, 3, 7, 15, 31, ...에 저장됩니다. 일반적으로이 목록의 n 항목 (0부터 시작)은 2n-1 색인에 저장되므로이 경우 배열 표현은 θ(2n) 공간이 필요합니다.
'힙'이라고도합니다. 그리고 당신이 공간이 (2^n)이라고 말했을 때, 당신은'2^높이'를 의미 했습니까? – Nishant