트리, 힙, 그래프

1. 비선형 문제 

계층적 문제 

순환 종속성 

 

2. 트리 : 상하 반전된 형태 

트리 순회

: 루트 노드를 기준으로 지어진 용어

 A

B C

1. preorder

A B C

2. inorder

B A C

3. postorder

B C A

3. 다양한 트리 구조

이진 검색 트리 ( Binary search tree) 

(1) 원소 검색 

(2) 새 원소 삽입하기

(3) 원소 삭제하기

(4) 시간복잡도

검색의 경우 매번 검색 범위가 절반으로 줄어든다. T(N) = T(N/2) + 1 => T(N) = O(log N)

균형 트리

 N 항 트리

 

4. 힙

완전 이진 트리 : 마지막 레벨의 노드를 제외하고는 모두 두 개의 자식 노드가 존재

최대 힙 (max heap) : 부모 노드가 두 자식노드보다 항상 커야 한다는 불변성 유지

 

(1) 힙 연산 

-원소 삽입하기

-원소 삭제하기

-초기화하기

 

5. 그래프 

가중 그래프

방향 그래프 

무방향 그래프 

(1) 인접 행렬로 그래프 표현하기

(2) 인접 리스트로 그래프 표현하기