[3주차] 비선형 자료구조 - 트리와 그래프

 

어느덧 5주 완결을 보고 시작한 스터디도 반절을 지나간다.

나도 누군가를 많이 가르치기도 하지만, 누군가의 문제 해결 방식에 나도 감명을 많이 받는다.

내가 바라는 스터디의 이상향에 한 층 더 가까워지는 중이다.

 

이번 주차는 자료구조 중 비선형 자료구조인 '트리'와 '그래프'에 대해 알아보며, 이들에 대한 탐색법까지 나아간다.

전체 주차가 5주밖에 안 되어서 무척 금방금방 지나오는 느낌인데, 사실 시작하고 보니 5주 가지고는 안되겠다며 아차 싶더라고.

 

---

1. 그래프 (Graph)

 

제목은 '트리'가 먼저 나와있지만, 트리도 결국 그래프의 일종이다.

이에 대한 자세한 설명은 차치하고, 우선 그래프부터 알아보자.

 

 

그래프는 우리가 아는 수치를 나타내는 그 그래프가 아닌, 그래프 이론에서 다루는 수학적 대상이다.

정점(Vertex or Node)과 여러 정점을 연결하는 변(Edge)으로 구성된다. 

 

아래에서는 종류와 표현 방식에 대해 알아보는데, 인접 행렬과 인접 목록에 대한 깊이 있는 이야기는 작성하지 않겠다.

현재 수준의 스터디에서 그래프 이론을 해결하는 데에 있어서 인접 행렬을 깊이 아는 것은 아직 필요치 않은 이야기이기 때문이다.

 

그래프의 종류

• 무방향 그래프 (Undirected Graph)
• 방향 그래프 (Directed Graph) - 여기에 tree가 속한다.
• 하나 이상의 사이클이 있는 그래프 (Cyclic Graph)
• 사이클이 없는 그래프 (Acyclic Graph) - 여기에 tree가 속한다.

그래프의 표현 방식

• Adjacency Matrix (인접 행렬) : 2차원 행렬으로 그래프를 나타내는 방법
• Adjacency List (인접 리스트) : Linked List로 그래프를 나타내는 방법

Adjacency Matrix - 2차원 행렬로 그래프를 나타내기

 

그래프에서 각 정점 (Vertex)의 연결 관계, 그러니까 간선(edge)의 존재 여부를 행렬로 표현한 것이다.

그래프에서 정점이 n개일 때, 각 정점을 행과 열로 하는 n차 정사각행렬이다.

 

Adjacency List - 인접 리스트로 그래프를 나타내기

 

인접 리스트 (혹은 인접 목록)으로 그래프를 나타내는 방법은 단순하게 각 정점에 대해 자신과 연결된 정점을 2차원 배열의 형태로 나열한 목록이다. 

 

간선의 개수가 m이라고 할 때, 총 node의 갯수는 2m으로 표현할 수 있다.

 

 

2. 트리

 

트리는 그래프의 일종이다.

그래프 중에서도 사이클이 없는 연결 그래프를 tree라고 한다. 

 

트리 용어

1. 루트 (Root) - 부모가 없는 최상의 정점 (노드)
2. 노드와 간선 (Node, Edge) 
3. 부모, 자식, 형제, 조상 노드 (Parent, Child, Sibling, Ancestor)
   1. 정점 A에서 정점 B로 가는 간선이 있을 경우 A는 B의 '부모'
   2. 정점 A에서 정점 B로 가는 간선이 있을 때 B는 A의 '자식'
   3. 정점 A를 부모로 갖는 자식 정점 B와 정점 C는 '형제'
4. 단말 노드, 간 노드 (Terminal, Nonterminal)
   1. 리프 (Leaf) - 자식이 없는 정점, 단말 노드라는 말도 쓰임.
5. 차수 (Degree) - 정점의 자식의 개수
   1. 트리의 차수 (Degree of Tree) - 트리의 최대 차수
6. 레벨과 깊이 (Level, Depth) - 루트에서 해당 정점으로 가는 최단 경로의 길이
7. 트리의 높이 (Height) - 정점들의 깊이의 최대값
8. 트리의 너비 (Weight) - 각 레벨에 속한 정점의 수의 최댓값

트리의 종류

 

1. 이진 트리 (Binary Tree)

• 각 노드에 자식이 최대 2개인 트리를 말한다.

 

2. 이진 검색 트리 (Binary Search Tree)

 

이진 검색 트리 (Binary Search Tree) 는 정점을 기준으로 왼쪽 자식은 부모보다 작은 값을, 오른쪽 자식은 부모보다 큰 값을 갖는 이진 트리를 말한다.

 

3. Balanced Binary Tree vs Unbalanced Binary Tree

 

트리의 균형을 이야기한다.

사진의 왼쪽처럼 부모가 자식을 가질 거면 왼쪽과 오른쪽 자식이 모두 있거나, 자식을 갖지 않을 거면 아예 갖지 않는 상태를

균형잡힌 이진 트리라고 이야기한다.

 

balanced binary tree에는

• Red-Black Tree
• AVL Tree

등이 있다.

 

4. 완전 이진 트리 (Complete Binary Tree)

 

완전 이진 트리는 마지막 레벨이 왼쪽과 오른쪽 자식을 모두 갖거나, 하나의 자식을 가질 경우 왼쪽부터 채워진 트리를 이야기한다.

 

5. Full Binary Tree (정이진트리)

 

모든 노드가 0개 또는 2개의 자식 노드를 갖는다. 자식 노드가 1개인 노드는 존재해서는 안된다.

즉, 이진 트리에서 리프 노드를 제외한 모든 노드들이 2개의 자식을 가져야 한다.

 

6. Perfect Binary Tree (포화 이진 트리)

이진 트리의 완벽한 형태이다. 

모든 내부 노드가 두 개의 자식 노드를 가지고 모든 리프 노드가 동일한 레벨을 갖는 이진 트리를 말한다.

즉, 모든 레벨이 노드로 완전히 채워져있는 상태를 이야기한다.

 

height가 h인 포화 이진 트리는

전체 노드의 수가 2^h+1 - 1 개이며,

리프 노드의 수는 2^h개,

리프 노드가 아닌 내부 노드의 수는 2^h - 1개이며

항상 완벽하게 균형이 잡혀있는 balanced tree이기 때문에 효율적인 연산이 가능하다는 특징이 있다.

 

출처

트리(그래프) (나무위키) : https://namu.wiki/w/%ED%8A%B8%EB%A6%AC(%EA%B7%B8%EB%9E%98%ED%94%84)

트리 구조(위키백과) : https://ko.wikipedia.org/wiki/%ED%8A%B8%EB%A6%AC_%EA%B5%AC%EC%A1%B0

그래프(이산수학) (나무위키) : https://namu.wiki/w/%EA%B7%B8%EB%9E%98%ED%94%84(%EC%9D%B4%EC%82%B0%EC%88%98%ED%95%99)

그래프 (자료구조) (위키백과) : https://ko.wikipedia.org/wiki/%EA%B7%B8%EB%9E%98%ED%94%84_(%EC%9E%90%EB%A3%8C_%EA%B5%AC%EC%A1%B0)

트리의 종류 (Youtube - 엔지니어 대한민국) : https://youtu.be/LnxEBW29DOw?si=uXEir8AsLIN9G1YD

그래프에 대해서 (Youtube - 엔지니어 대한민국) : https://youtu.be/fVcKN42YXXI?si=n1V73XkDpHexssBr