자료구조 - 그래프, 트리

Graph 

꼭지점 node - vertex

edge - 모서리

 

아래그림)

 

아래그림)

node 인접해있다.

graph 탐색시 이동한 족적이 walk

 

A-C-B-D-E

열린 Walk - 처음과 끝이 다른 walk

닫힌 Walk - 처음과 끝이 같은 walk

 

Path

- walk 중에 중복된게 없으면 path

cycle

- 닫힌 walk와 path의 조건을 모두 만족하면 cycle

 

아래그림)

중복되서 cycle 아님

 

Tree

다음의 두조건을 만족하는 경우를 tree라고 함

1) graphy가 연결 graphy일때

2) 주어진 graphy는 cycle이 없다.

tree는 자식 node와 부모 node의 관계로 이어져 있다. 

보통, 독립적인것은 cycle되기힘듬

 

아래그림)

Root Node - 부모 node가 없으면

Leaf Node - 자식node가 없으면

나머지 - 내부 node

 

이진 tree - 모든 node가 자식 node가 최대 2개일때 

               - 세개가 자식인게 하나라도 있으면 이진트리 아님

 

포화 이진 tree (Perfect Binary Tree) - 완벽히 꽉차있어서

- 꼭 자식이 (직계자식) 최대 두개여야함

1. 모든곳이 빈틈없이 채워진 이진 tree

2. 모든 내부 node의 자식이 둘이며 ,

모든 leaf node의 깊이가 동일한 이진 tree

 

아래그림)

 

완전 이진 Tree

(Complete Binary Tree)

Perfect Binary에서 일부 node를 제거

최하단의 leaf node가 좌측에 몰려있을경우 완전 이진 tree(왼쪽부터 채워져서)- 크기상관없이 왼쪽부터 채워짐