트리, 힙, 그래프

트리, 힙, 그래프

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) 인접 리스트로 그래프 표현하기

from http://bohyeonstudy.tistory.com/92 by ccl(A) rewrite - 2021-07-30 11:00:43