[자료구조&알고리즘 | WEEK03] 그래프/트리(비선형 자료구조) 개념정리

그래프(Graph)

---

비선형 자료구조인 그래프 또는 트리에서 자료를(원소) 보관하는 것을 정점(Vertex) 혹은 노드(Node)라고 부르며,
정점에서 다른 정점으로 가는 경로를 간선(Edge) 혹은 링크(Link, 다른 노드의 위치 정보)라고 부른다.

이를 통해 연결된 노드 간의 관계를 표현할 수 있다. 즉, 연결 관계를 표현하는 자료구조라고 할 수 있다.

아래의 이미지처럼 그래프는 트리보다 더 넓은 범위라고 할 수 있다.

 

그래프와 트리의 포함 관계

 

그래프의 종류

방향 그래프(Directed Graph), 무방향 그래프(Undirected Graph)

• 무방향 그래프는 간선을 통해 양방향으로 갈 수 있다.
• 방향 그래프는 간선의 방향이 존재하는 그래프로 한 방향으로만 갈 수 있다.
  • 노드 사이에 양방향으로 표시된 간선은 양방향으로 통행 가능

이외에도 그래프의 종류는 다양하게 있다.(가중치 그래프, 이분 그래프 등)

 

 

 

 

순환적(Cyclic), 비 순환적(Acyclic)

• 그래프 내부에 노드들이 방향을 이루어 하나 이상의 순환하는 원이 생성되어 있으면 Cyclic 그래프
• 그래프 내부에 노드들이 방향을 이루어 순환하는 원이 없다면 Acyclic 그래프라고 부른다.

 

 

그래프의 표현 방법

그래프의 표현 방법에는 아래와 같이 총 2가지 방법이 있다.

인접 행렬(Adjacency Matrix)

1. 2차원 배열에 표현하는 방법

인접 리스트(Adjacency List)

1. 배열의 노드들을 나열하고, 연결 리스트(Linked list)로 표현하는 방법

 

그래프의 표현 방법

이때 인접리스트의 개수는 간선의 수 * 2 만큼의 개수가 생기게 된다.

단, 위와 같은 무방향 그래프일 때 적용함

 

트리(Tree)

---

노드가 하나 이상의 자식을 가지고 있으면 트리라고 한다. 따라서 트리는 그래프와 다르게 루트(Root - 최상위 노드)를 가지고 있으며, 부모-자식의 관계를 가지는 구조이다. 

트리는 위에서 아래로만 흐르는 방향 그래프 중 하나라고 할 수 있다. 하지만 트리의 이런 특성 때문에 방향을 표시하지 명시적으로 표시하지 않는 경우가 일반적이다.

 

트리 용어

트리 또한  자료를(원소) 보관하는 것을 정점(Vertex) 혹은 노드(Node)라고 부르며, 정점에서 다른 정점으로 가는 경로를 간선(Edge)으로 구성된다. 이때 중요한 트리의 특징은 트리는 트리는 두 개의 노드 사이에 반드시 1개의 경로를 가진다.

 

특정 노드의 자식 수를 노드의 차수(Degree)라고 부르며,
트리의 모든 노드 중 가장 높은 차수를 트리의 차수라고 말한다. 그리고 차수가 0인(자식이 없는) 노드를 단말(Terminal) 혹은 리프(Leaf)라고 부른다.

 

자신의 자식을 루트로 하는 트리를 서브 트리(Sub Tree)라고 부르며, 차수와 서브 트리의 개수는 같다.

 

이 외 정보는 아래의 링크와 이미지를 확인하면 좋을 것 같다.

트리 용어

7.1 트리의 용어 – 언제나 휴일

 

트리의 각 명칭

 

트리의 종류

이진 트리(Binary Tree)

이진 트리는 단순하게 자식 노드가 두 개까지만 붙는 트리를 이진 트리라고 부른다.  두 개까지 붙어 있을 수 있는거지, 하나만 붙어 있어도 이진 트리라고 부른다. 하지만 자식이 2개만 붙으라는 법은 없는 것이고, 더 많은 수의 자식을 가질 수 있으며, 트리 자식 수에 따라 붙여지는 이름이 다르다. 여기서 우리는 이진 트리를 가장 관심 있게 공부할 예정이다.

 

자식이 3개인 트리와 이진 트리

 

이진 검색 트리(Binary Search Tree)

이진 검색 트리는 현재 자신의 노드에서(부모) 왼쪽을 기준으로 그 이하 자식 노드들은 현재 노드보다 작아야하며,

현재 자신의 노드에서(부모) 오른쪽을 기준으로 그 이하 자식 노들들은 현재 노드보다 커야한다.

이러한 특성 덕분에 현재 기준으로 더 큰 값을 찾을 땐, 오른쪽을 탐색하면 되고, 현재 기준으로 더 작은 값을 찾을 땐 왼쪽을 탐색해보면 되는 것이다. 

 

아래 이미지에서도 확인할 수 있듯이 이진 트리(Binary Tree)에서는 8보다 큰 값 '12'을 찾기 위한 규칙성을 찾을 수 없지만, 이진 검색 트리(Binary Search Tree)에서는 8보다 큰 값 '11'을 찾기 위해 오른쪽으로 가면 바로 찾을 수 있다.

 

 

완전 이진 트리(Complete Binary Tree)

힙(Heap) 자료구조를 포스팅했을 때 공부했던 내용인데, 모든 노드들이 레벨별로 왼쪽부터 채워져 있으면 완전 이진 트리다. 여기서 다시 한번 언급하자면 '완전'이란 노드들이 왼쪽부터 채워지는 것을 뜻하고, '이진'은 자식이 2개라는 뜻이다.

쉽게 말해, 마지막 레벨을 제외한 서브트리들은 모두 채워져 있어야하며, 마지막 자식 노들들은 왼쪽부터 채워져있으면 됨!

 

 

이외에도 트리의 종류는 더 많다!(red-black Tree, AVL Tree, Full Binary Tree, Perfect Binary Tree 등)

 

이진 트리 순회 (Binary Tree Traversal)

이진 트리를 순회하면서 트리의 있는 모든 데이터를 가져오는 방법에는 3가지 방법이 있다.

전위 순회 - Preorder(Root, Left, Right)

자기 자신을 먼저 출력, 그리고 왼쪽, 오른쪽 순으로 출력하는 것을 의미한다.

(자기 자신을 먼저 출력하기 때문에 'pre'라는 키워드가 붙었다.)

 

전위 순회

 

중위 순회 - Inorder(Left, Root, Right)

자기 자신을 기준으로 왼쪽 노드를 먼저 출력하고, 자기 자신을 호출, 마지막으로 오른쪽 노드를 호출하는 것을 의미한다.

(자기 자신을 중간에 출력하기 때문에 'in'라는 키워드가 붙었다.)

 

중위 순회

 

 

후위 순회 - Postorder(Left, Right, Root)

자기 자신을 기준으로 왼쪽 노드를 먼저 출력하고, 오른쪽 노드를 출력하고, 마지막으로 자기 자신을 출력한다.

(자기 자신을 마지막으로 출력하기 때문에 'post'라는 키워드가 붙었다.)

 

후위 순회

 

그래프와 트리 비교

	그래프	트리
정의	노드(node)와 그 노드를 연결하는 간선(edge)을 하나로 모아 놓은 자료구조	그래프의 한 종류로, 방향성이 있는 비순환 그래프 DAG(Directed Acyclic Graph)
방향성	방향 그래프(Directed Graph) 무방향 그래프(Undirected Graph)	방향 그래프(Directed Graph)
순환성(사이클)	순환, 비순환, 자기순환	비순환
루트	루트 노드의 개념이 없음	한 개의 루트 노드만이 존재, 모든 자식 노드는 한개의 부모 노드만을 가짐
부모-자식	X	O
모델	네트워크 모델	계층적 모델
순회	DFS, BFS	DFS, BFS안의 Pre, In, Postorder
경로	-	임의의 두 노드간의 경로는 유일
간선 수	자유	N(노드) - 1개
예시 및 종류	지도, 지하철 노선도의 최단 경로, 도로(교차점과 일방 통행길), 선수 과목(위상정렬)	이진 트리, 이진 탐색 트리, 균형 트리(red-black 트리, AVL 트리), 이진 힙(최대 힙, 최소 힙) 등

 

 

---

Ref

파이썬알고리즘인터뷰

Directed Graphs vs. Undirected Graphs

Graphs & Graph Search Algorithms

그래프와 트리
트리의용어

유튜브 - 트리의 종류
이진 트리 순회: 전위, 중위, 후위, 레벨