대엉코딩

1. 트리[Tree] 란?

- computer science에서 계층구조(hierarchical structure)를 가진 추상자료형

- 트리는 노드로 구성되어 있는데, 노드들은 부모-자식 (parent-child)관계를 가진다.

- 직장에서 부장-과장(1,2,3)-(대리1,2,3,4,5,6) 이 업무연관성에 따라 그려진 조직도를 떠올려보면 좋다.

- File System, Programming enviroment 등에서 사용된다.

2. 용어(Terminology)

- Root (node) : parent가 없는 노드

- Internal node : 적어도(at least) 자식을 하나이상 가지는 노드

- External node : 자식이 없는 노드

- Ancestors of a node(a) : node(a)의 parent,grand parent, grand-grandparent........etc

- Depth of a node(a) : number of ancestors (조상노드의 수)

- Height of a tree(a) : maximum depth of any node (가장 큰 깊이를 가진 노드의 깊이가 트리의 높이)

- Descendant of a node : child, grandchild, ..... etc

3. Method

-기본적인 methods 

-(1) Generic methods

     - int size()

     - bool empty()

-(2) Accessor methods

     - position root()

     - listh<position> positions()

-(3) Position-based methods

     - position parent()

     - list<position> children

-(4) Query methods

     - bool isRoot()

     - bool isExternal()

4. 탐색(순회)

- 트리 자료구조를 탐색하는 방법은 많지만 여기서는 기본적인 2개만 다루겠다.

-(1) 전위순회

     - descendants들을 방문하기 전에 자신의 노드부터 방문처리 하는 것이다.

-(2) 후위순회

     - descendants를 먼저 방문하고 자신을 마지막에 방문처리하는 것이다.

0. heap?

 - 구조 조건과 순서 조건을 가지고 있는 자료구조 이다.

 - 구조 조건 : 이진트리인데 갚이가 h 일 때 h-1까지는 full binary tree 이고 h번째에는 왼쪽부터 차례대로 채운다.

 - 순서 조건 : 부모노드는 자식노드 보다 크다 (max-heap 일 때) , 직계가 아닌 노드 끼리는 상관이 없다.

1. heap sort?

 - 위에서 언급한 heap 이라는 자료구조를 이용한 sort 방법이다.

 - heap의 특성을 생각 한다면 ? n개의 정보를 sort하기 위해선

 - data를 heap 구조로 construct 하면 root 노드 에 있는 값이 가장 큰 값이므로 그 값을 빼오면 된다. 

    (n번의 삭제연산을 수행 하면 sort가 완료된다.)

2. delete(root) and fixheap ? (downheap)

 - 루트에 있는 노드(제일 큰값을) 가져갔다고 하자. 그러면 남은 노드들로 다시 heap을 만족하도록

   트리를 구성해야 그 다음 루트노드를 또 삭제할 수 있다 (두 번째로 큰값이겠죠? 전체에서? )

 - 그렇다면 생각 해보자 ..... 루트를 제외하고 남은 트리에서 heap이 되게 하려면

 - 구조 조건과 순서 조건을 만족해야 하는데...... 어떤 것을 만족하는게 더 쉬울까 ? ----> (구조조건?)

 - 왜?? 만약에 n-1개의 노드가 남아 있다고 할때 heap의 구조조건을 만족하도록 만드는 모양은 하나뿐이다.

    ( 즉 위치로 보자면 어디 위치의 노드가 없어지느냐 ? 맨 밑 리프 노드 열에서 가장 오른쪽의 노드 !)

    ( 이 위치는 O(1) 에 바로 찾을 수 있다...! ....왜? heap은 배열로 구현 하기 때문에 맨 마지막 index의 노드!)

 - 그럼 일단 가장 오른쪽에 위치한 리프노드를 루트 노드로 덮어 쓰자 ! --->구조 조건은 만족 !

 - 이제 순서조건을 생각해보자 .... 일단 루트노드로 덮어쓴 가장 오른쪽 리프 노드가 다시 자신의 자리를 

 - 찾아갈 수 있도로 해야 하는데 이 과정이 fixheap이다 !

3. fixheap 하자

 - 이제 루트노드로 올라온 가장 오른쪽에 위치한 리프노드가 다시 자기 자리를 찾아가야 한다.

 - 자식노드들 중 값이 큰 노드와 자신을 비교해서 자신이 더 작다면 그 노드의 위치로 내려간다 (그 자식노드는 올라옴)

 - 이 과정을 자신의 위치를 찾을 때 까지 반복하여 수행 한다.(recursive하게)

 - 한번의 과정에 2번의 연산 수행 (자식들 끼리 누가 더 큰지 비교, 그 큰 자식과 자신과 비교 )

 - full binary tree 이므로 h = log n  ---->  W(n) : 2logn -->Θ(logn)

4. Algorithm

지금까지 입력으로 부터 힙이 구성된 상태에서 sort를 어떻게 할 수 있는지 에 대하여 배웠습니다.

(2)에서는 입력으로 부터 heap을 어떻게 construct하고 성능분석과

힙소트의 성능을 올릴 수 있는 방법에 대하여 알아봅시다.

1. DNS란?

 - 사람들은 각각을 구분해주는 예를들면 주민등록번호 같은 것 들이 있다 

 - IP address와 name을 binding

 - IP address를 직접 다루는 건 어렵기 때문에 다루기 쉽게 name으로 변환

2. Domain Name System

 - distributed database

 - application-layer protocol 이다.

 (core internet function 이지만 5계층 application-layer에 구현되어 있다.)

3. DNS services

 - 1. hostname to IP address translation

 - 2. host aliasing

 - 3. mail server aliasing

 - 4. load distribution (traffic을 분산시킨다.)

4. why not centralize DNS?

 (centralized DNS라면 )

 - single point of failure (그 서버하나가 죽으면 끝이다 이럴경우)

 - traffic volume (traffic이 몰림)

 - distant centralized database (먼 곳에서는 속도가 저하)

 - maintenance (유지보수가 어려움)

 - doesn't scale ! (확장성이 낮다)

5. a distributed, hierarchical database (관리가 편하다나는 장점)

6. DNS : root name servers

 - local name server에 접근해보고 없을 경우 root name server로 올라간다.

 - 전 세계적으로 13개의 root name servers가 있다.

 - 우리랑 가까운 지역의 root name server는 도쿄에 있다.

7. Local DNS name server

 - doesn't not strictly belong to hierarchy

 - " default name server"라고도 불리운다

 - 일단 여기서 찾아보고 없을경우 top level로 간다.

 - proxy server가 하는 역할과 비슷하다.

8. local DNS - root DNS

 - iterated query 방식 (local DNS에 로드가 많이 걸린다.)

 - recursive query 방식 ( like stack )