5. Tree

-그래프의 특수한 경우

- Connected Graph with no cycle

 *정의

1. 하나 이상의 노드로 이루어진 자료구조

2. 노드들 중 하나는 root이다.

3. root를 제외한 나머지 노드들은 subtree들로 분할된다.

4. root와 subtree의 root 사이에는 edge가 있다.

 *용어

- node의 subtree root를 node의 child라고 부른다.

- degree(차수) : node의 child 수

- degree가 0인 node : leaf, terminal

- A가 B의 child => B는 A의 parent

- parent가 같은 node들 => 형제(sibling)

- root level : 1, node level : parent level + 1, 제일 큰 level : heght or depth

- parent, parent의 parent, ,,,,,, => 조상(ancestor)

- child, child의 child, ...... => 자손(descendant)

 

5.1.1 Tree의 표현(child를 표현하는 방법)

1) 배열 방법 

2) Left child - Right sibling

3) Binary Search Tree

5.2 Binary Tree

 - child가 최대 2개인 tree

5.2.3 Binary tree의 표현

 - 배열에 embeded.

 - 배열의 i에 있는 node의 children은 2i, 2i+1에 존재

5.3 Tree Traversal

-정의 : root에서 시작해서 node들을 "지정된 순서"에 따라서 "방문"하는 것

-종류 : preorder, inorder, postorder

-트리에 다항식을 넣으면 전위/중위/후위 연산자 표현이 가능하고, 변수를 넣으면 기계어를 만들 수 있다.

5.6 Heap

 - 우선 순위 큐를 만들 때 사용

 - Complete Binary Tree.

 - 어떤 노드의 키 값은 children의 키 값보다 작다.

 - Heap Insert : up-heap. leaf중에서 제일 오른쪽에 추가한 후, parent와 비교해서 조건에 안 맞으면 교환. 그리고 반복

 - Heap Delete : down-heap. root를 보내주고, leaf중에서 제일 오른쪽에 있는 것을 root로 올린 후, children과 비교해서 조건에 안 맞으면 교환. 그리고 반복.

 - tree는 재귀적으로 코딩하면 더 쉬워진다.

5.7 Binary Search Tree 

- Binary tree

- left, right의 children

- node a의 left subtree : a의 키보다 작은 키 값

- node a의 right subtree : a의 키보다 큰 키 값

- Insert : Search를 한 후, 실패했다면 그곳에 새 child로 insert

- Delete : leaf일 때는 그냥 삭제, one child 일때는 child를 parent에 붙여주고 삭제, two children 일때는 오른쪽으로 한번, 왼쪽으로 계속 내려가서 만나는 leaf랑 해당 노드를 바꾼 후, 바뀐 leaf를 삭제.

5.10 Union-Find

-집합의 연산 중 합집합과 대표 원소 찾기(집합 이름 찾기, 두 원소가 같은 집합에 있는지 확인)

-Minimum Spanning Tree 문제

-연결을 유지하면서 최소 비용 쓰기

방법1 : 한 노드르 찍고, 최소 비용 edge를 추가 해나감.

방법2 : 전체 edge를 sorting한 다음, 최소 비용 edge부터 추가 해나감

-항상 사이클을 만들지 않는다.

-사이클 검사 : 방법1 일때는 Tree에 이미 포함된 노드 둘을 연결할 때 사이클이 생기고, 방법2 일때는 같은 덩어리에 있는 노드 둘을 연결할 때 사이클이 생김.

-구현 : 배열상에서 구현. 포인터는 index, 무제한 tree, 포인터 방향은 child->parent. 즉 해당 node는 자신의 parent의 index의 값을 가지고 있음.

- 성능 : Find와 Union 둘 다 tree depth에 비례.

- Path Compression 사용