개발 공부 - [검색트리] 트리와 이진트리

 섹션 4. 검색트리 - 이진검색트리

검색트리 (search tree)

* 트리와 이진트리 

Tree and Binary Tree

트리 : 계층적인 구조를 표현 

- 조직도

- 디렉토리와 서브디렉토리 구조

- 가계도

트리는 노드(node)들과 노드들을 연결하는 링크(link) 들로 구성됨.

맨 위의 노드를 "루트" 라고 부름 

- 부모 - 자식 관계 

parent 와 child 노드를 기재 

-형제관계

루트노드를 제외한 트르이 모든 노드들은 유일한 부모 노드를 가짐

부모가 동일한 노드들을 형제(sibling)라고 부름

- 리프 노드

자식이 없는 노드는 leaf 노드 (가지가 끝나서)

리프노드가 아닌 노드는 내부 노드 라고 부름(internal)

- 조상 - 자손 관계

부모 - 자식 관계를 확장하면 조상 - 자손 관계도 성립함 

ancestor - descendant 관계 (root는 다른 애들의 ancestor)

- 부트리

트리 전체를 잘라서 부분적으로 보면 부트리

트리에서 어떤 한 노드와 그 노드의 자손들로 이루어진 트리 (부트리)

- 트리의 기본적인 성질

노드가 N개인 트리는 항상 N-1개의 링크(link)를 가진다.

트리에서 루트까지 어떤 노드로 가는 경로는 유일하다.

또한 임의의 두 노드간의 경로도 유일하다. (같은 노드 두번이상 방문하지 않는 경우) 

- 이진 트리

이진 트리에서 각 노드는 최대 2개의 자식을 가진다

각각의 자식 노드는 자신이 부모의 왼쪽 자식인지 오른쪽 자식인지가 지정된다.

한 명의 자식인 경우에도 왼쪽 / 오른쪽을 지정해야 한다.

- 이진 트리 응용시 Expression Tree

(x+y) * ((a + b ) / c) 를 tree 형태로 나타냄

- Huffman code

예제를 보여주었다.

- Full and Complete Binary Trees

이거 예전에 한 Full과 Complete 개념과 똑같음.

- Full Binary Tree는 높이가 h일때 2^h -1 개의 노드를 가진다.

- 노드가 N개인 full이나 Complete 이진 트리의 높이는 O(logN)이다.

* 최악의 경우 노드 N개일 경우에 N 높이를 가질수도 있다.

- 연결구조 (linked structure) 표현

예제를 보여주었다.

- 이진트리의 순회 (traversal)

중순위 (inorder) 

선순위 (preorder)

후순위 (postorder) 후위표기

* 레벨오더 순회

- level-order 순회

레벨 순으로 방문, 동일 레벨에서는 왼쪽에서 오른쪽 순서로 

큐를 이용하여 구현

                    3

        1                    5

0            2        4        6

        7        8

이런 식으로 되어 있다면

3 1 5 0 2 4 6 7 8 순으로 방문