graph (그래프)

: vertex(정점)과 edge(간선)으로 구성된 자료구조

연결 구조를 모델링하는 데 유용함.

directed gragh(방향 그래프)

: 방향이 있는 edge를 가진 그래프

한 방향으로만 연결된 구조를 가짐.

→ 두 정점의 관계가 비대칭적일 수 있음.

undirected graph(비방향 그래프)

: edge에 방향이 없는 그래프

→ 두 정점의 관계가 대칭적임.

weighted graph(가중 그래프)

: edge에 가중치가 부여된 그래프

edge마다 비용, 거리 등을 나타내는 값이 있음.

unweighted graph(비가중 그래프)

: edge에 가중치가 없는 그래프

두 vertex가 연결되어 있는지만 나타냄.

tree (트리)

: node(노드)와 edge(간선)로 구성된 자료구조

각 node는 중복되지 않은 고유의 value(값)을 가짐.

root node(루트 노드)를 시작으로 자식 노드를 따라가며 계층 구조를 나타냄.

장점

계층적인 데이터 구조 표현하기 좋음.

검색, 삽입, 삭제가 빠름.

단점

트리의 불균형이 심하면 성능 떨어짐.

트리 구조 구현할 때 메모리 공간 필요함.

binary tree(이진 트리)

: 각 노드가 최대 2개의 자식 노드만 가질 수 있는 트리

완전 이진 트리, 포화 이진 트리, 편향 이진 트리 등의 종류가 있음.

검색, 삽입, 삭제가 평균적으로 O(log n)

https://upload.wikimedia.org/wikipedia/commons/thumb/f/f7/Binary_tree.svg/330px-Binary_tree.svg.png

heap(힙)