7. 탐색의 하한값탐색에 있어 최악의 경우의 비교횟수는 트리의 깊이.내부 노드 수가 m개인 결정트리T1이 있을때,n개의 원소를 갖는 리스트를 탐색하는 어떠한 알고리즘이라도최악의 경우에는이 결정트리의 각 노드를 최소한 한 번씩은 비교해야 함.따라서 m≥n깊이 d를 갖는 모든 이진 트리는 최대 2d+1-1개의 노드m개의 노드를 갖는 모든 포화 이진 트리의 깊이는 최소 이상
8. 탐색의 하한값내부 노드 수가 m개인 결정트리T1.n개의 원소로 된 리스트의 탐색.트리 T1에서 리프노드 제거하면 m≥n인m개의 노드로 이루어진 트리 T2.T2. 는 d ≥ ≥ 인 깊이를 가진다따라서 T1은 d ≥ 인 깊이를 가진다n개의 원소로 된 리스트를 탐색하는 모든 알고리즘은 최악의 경우 적어도 의 비교횟수를 갖는다.
9. 이진 탐색 트리각 노드의 값이 그 노드의 왼쪽 부분 트리에 속한 모든 노드의 값들보다는 커야 하며, 오른쪽 부분 트리에 속한 모든 노드의 값들보다는 작아야 한다.1.첫번째 원소를 루트 노드에 삽입2. 다음 원소는 루트와 비교하여 작으면 왼쪽 자식, 크면 오른쪽 자식을 만들어 삽입
11. 정렬리스트 L에 있는 n개의 원소들을 순차적으로 정렬하는 알고리즘을 결정트리로 표현해보자내부노드:L(i):L(j) L의 i번째와 j번째 원소를 비교하는 행동아크:<, >리프노드:L(1) < L(2) < L(3) 등의 최종 결과리프노드는모든 원소들의 조합(combination)인 n! 개의 정렬 순서를 나타낸다.
12. 정렬생성될 수 있는 정렬 순서 n!리프노드의수를 p 라 하면 p≥n!트리의깊이를 d라 하면 p≤2d,n개의 원소로 된 리스트를 정렬하는 모든 알고리즘은 최악의 경우 적어도의 비교횟수를 갖는다.
13. Huffman 코드문자 인코딩대표적인 고정길이 인코딩.ASCII데이터 압축자주 발생하는 문자들에게 더 적은 비트 할당파일의 내용에 대해 잘 알아야 함
14. 데이터 압축50000개의 a,c,g,k,p,? 문자고정길이라면, 글자당 3비트, 총 150,000비트 필요위와 같이 하면50000(0.48*1 + 0.01*4 + 0.12*3 + 0.04*4 + 0.17*3 + 0.1*3)= 108,500비트
15. 접두사 코드고정길이 인코딩을n비트씩 잘라서 디코딩.가변길이는 다른 구분 법이 필요하다.하나의 코드가 다른 코드의 접두사가 되지 않는 코드깊이 d(i), 빈도 f(i) 총 문자수S최적의 이진트리T를 찾으려면를 최소화 하면 된다.acgk? p
16. Huffman 코드자세한 알고리즘은 책.463p~464p이 알고리즘은 E(T)에 대해 항상 최소값을 제공한다.m개의 문자들에 대해 최적 트리 T가 있다면,가장 낮은 빈도수를 갖는 노드들은 항상 어떤 노드의왼쪽·오른쪽 자식 노드가 된다.가장 낮은 빈도수 x,y를 갖는 두개의노드가 있을 때.x,y가 형제 노드가 아니라면,가장 낮은 레벨의 형제노드p,q가 있을 것.x,y 가 이 레벨에 있지 않다면…
