트리

그래프의 하위 구조

​

1. 연결그래프, 사이클이 없음, 무방향

2. 1개 이상의 노드

3. 노드 a와 b를 잇는 길이 유일하다.

4. 간선 개수 = 노드 개수 - 1

5. 대가리 = root node : 모든 노드가 루트가 될 수 있다.

6. 루트 노드를 제거하면 그 밑에 각각 서브트리가 생기는 구조.

7. 부모노드 자식노드

8. 부모노드는 최대 하나

​

용어

1. degree = 자식 노드의 개수 : degree 0 = 맨 끝에 있는 노드 = leaf 노드

2. level : 루트가 1이면 자식으로 내려갈수록 +1

3. depth, hight : 가장 높은 레벨

​

이진트리 binary tree

1. 자식노드가 최대 2개

2. left, right 자식 노드가 분리됨

​

포화이진트리 full binary tree

트리 깊이가 k면 2^k-1개의 노드로 구성 ( 피라미드 꽊꽊 )

​

완전이진트리 complete binary tree

리프 바로 위까지 피라미드 꽊꽊이고, 리프는 왼쪽부터 채워져 있는 트리

트리 깊이가 h -> 노드 개수는 2^(h-1)개 이상, 2^h-1개 이하

전체 노드가 n -> 트리 높이 log2(n+1) 의 올림값

​

자료구조 표현법

1. pair 배열로 표현 가능

2. vector 배열로도 물론 가능

​

순회 알고리즘

1. 전위 순회 (preorder)

2. 중위 순회 (inorder)

3. 후위 순회 (postorder)

​

이진 트리 관련 자료구조 - heap

1. 삽입 (push) : O(logn)

맨 마지막 노드 뒤에다가 새로운 노드를 붙임.

부모노드와 우선 순위를 비교하면서 타고 올라간다.

2. 삭제 (pop) : O(logn)

루트 값 삭제

가장 마지막 노드를 루트로 올려주고 자식 노드들과 비교하면서 타고 내려간다.

​

Priority Queue

우선순위가 높은 순서대로 뱉는다.

heap으로 구현가능

STL도 있음ㅎㅎ