Problem Set 3

Read Chapter 8.

 

1.      Prove that the smallest height for any tree on n nodes is Ω(lg n) = - 1 + lg(n+1).

 

하한은 높이가 h인 완전 이진 트리를 살펴봄으로써 증명 가능하다. 

완전 이진 트리? 높이가 k일 때 레벨 1부터 k-1 까지는 노드가 모두 채워져 있다

(=leaf node가 아닌 모든 노드는 2개의 자식을 가지고 있다)

-> 추가 노드를 leaf node에 연결하게 된다면 ?  높이도 증가함. 같은 수의 노드를 가진 이진 트리에서 최소 높이를 가진다! 

깊이(h), 노드의 개수(n) h=0, 최대 n=1 h=1, 최대 n=2 (최소 1개) h=2, 최대 n=4 (최소 2개) ...  -> 트리의 깊이가 h면, 노드의 개수는 2^h개  n <= 1 + 2 + 2^2 + .... 2^h

 1 + 2 + 2^2 + .... 2^h  = 2^(h+1) - 1 ( : 깊이가 h인 완전 이진 트리에서 n개의 노드를 가진다) 

(그럼 어떻게  1 + 2 + 2^2 + .... 2^h  = 2^(h+1) - 1 되는가 ? )

 

**시그마로 등식 표기 : (k=0부터 h까지, 2^n+1 표기하면 동일)

- 귀납기초 : d=0, 2^0 = 1 = 2^(0+1) - 1 - 귀납과정 : 임의의 음이 아닌 정수 d에 대해서 다음 등식이 성립한다고 가정 ->  2^0 + 2^1 + 2^2 + .... 2^d  = 2^(d+1) - 1  - 귀납단계 :  2^0 + 2^1 + 2^2 + .... 2^(d+1)  = 2^((d+1)+1) - 1  -> 성립하나요 ?  2^0 + 2^1 + 2^2 + .... 2^(d+1)  = 2^0 + 2^1 + 2^2 + .... 2^d + 2^(d+1)                                                         = 2^(d+1)  - 1 + 2^(d+1)                                                        = 2 *  2^(d+1) - 1                                                        = 2^((d+1)+1) -1

==> 이렇게 해서,  n <= 2^(h+1) - 1 

 

 

n <  2^(h+1) 

lg n < h + 1 

lg n <= h 

 

n <= 2^(h+1) -1

lg n <= h + 1 - lg

lg (n+1) -1 <= h 

 

==> Ω(lg n) = lg(n+1) -1 

 

https://math.stackexchange.com/questions/1355163/proving-that-a-binary-tree-of-n-nodes-has-a-height-of-at-least-logn

Proving that a Binary Tree of $n$ nodes has a height of at least $\log(n)$.

https://www.quora.com/The-height-of-any-binary-tree-of-n-nodes-is-between-log-n-and-n-1-What-is-the-proof-for-this-observation

The height of any binary tree of n nodes is between log(n) and n-1. What is the proof for this observation?

---

2.      When you shrink the space of direct access arrays, you might want to use a linked list data structure. What would be the problem if you use the linked list? Show your answer with explaining the time complexity.

 

->  what is the linked list ? ; 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 데이터를 저장하는 자료 구조

 

접근(Access) 시간 복잡도: O(n)

• 인덱스 x에 있는 노드에 접근하려면? Head에서 다음 노드로 x번 이동
• 마지막 노드에 접근하려면 ?  Head에서 마지막 노드까지 n-1번 가야된다.
• 최악의 경우 시간 복잡도 : O(n)

탐색(Find) 시간 복잡도: O(n) 

• Head 노드부터 다음 노드를 하나씩 보면서 원하는 데이터를 가진 노드 찾기 (배열을 탐색할 때와 같은 방법, 선형 탐색 이용)
• 연결 리스트안에 찾는 데이터가 없거나 or 찾으려는 데이터가 마지막 노드에 있는 경우 ? n개의 노드를 다 봐야한다.
• 최악의 경우 시간 복잡도 : O(n)

삽입/삭제(Insertion/Deletion) 시간 복잡도: O(1)

• 삽입, 삭제할 노드의 주변 노드들의 Link만 수정하면 된다.
• 따라서 삽입, 삭제가 실행되는 시간은 특정 값에 비례하지 않고 항상 일정하다.
• 시간 복잡도 : O(1)

==> 삽입, 삭제 연산을 위해서는 탐색 연산이 필요함 !! (어떤 노드를 삭제, 삽입할지..)

즉, 결국 삽입, 삭제 연산 자체는 O(1)의 시간 복잡도를 가지지만, 탐색 연산 때문에 최악의 경우 O(n)의 시간 복잡도가 필요하다는 문제가 발생한다. 

 

 

https://hyeinisfree.tistory.com/64

[Data Structure] 연결 리스트(Linked List)

https://codingstudyroom.tistory.com/24

[자료구조]싱글 링크드 리스트(단순 연결 리스트)의 시간 복잡도

 

3.      In the hash family function, a should not equal to 0. Why? Please give me a simple answer (one sentence).

4.      Use the birthday dataset, Do the followings:

4.1.            Put them into your unordered array using set.

4.2.            Put them into the sorted array set.

4.3.            Put them into the direct access array set

4.4.            Put them into the hash table set.  

4.5.            Compare their size.

4.6.            Compare their interfaces: build, find, insert, delete, find_min, find_max, find_next, find_prev.