[Section2] 자료구조(Tree, Graph)

Tree

 

자료구조 Tree는 단방향 그래프의 한 구조로, 하나의 뿌리로부터 가지가 사방으로 뻗은 형태가 나무와 닮아 있다고 해서 트리 구조라고 부릅니다.

 

출처 - 코드스테이츠

트리 구조는 데이터가 바로 아래에 있는 하나 이상의 데이터에 무방향으로 연결된 계층적 자료구조이다.

데이터를 순차적으로 나열시킨 선형 구조가 아니라, 하나의 데이터 아래에 여러 개의 데이터가 존재할 수 있는 비선형 구조이다.

 

Tree의 구조와 특징

 

출처 - 코드스테이츠

트리 구조는 루트(root) 라는 하나의 꼭짓점 데이터를 시작으로 여려 개의 데이터를 간선(edge)으로 연결한다.

각 데이터를 노드(Node)라고 하며, 두 개의 노드가 상하 계층으로 연결되면 부모/자식 관계를 가진다.

위 그림에서 A와 B와 C는 부모 노드(Parent Node)이고, B와 C는 A의 자식 노드(Child Node)이다.

자식이 없는 노드는 나무의 잎과 같다고 하여 리프 노드(Leaf Node)이다.

 

출처 - 코드스테이츠

Tree는 깊이, 높이, 레벨 등을 측정할 수 있다.

 

깊이(depth)

트리 구조에서는 루트로부터 하위 계층의 특정 노드까지의 깊이(depth)를 표현할 수 있다. 루트 노드는 지면에 있는 것처럼 깊이가 0이며 자식 노드인 B와 C의 깊이가 1, B와 C의 자식노드인 D, E, F, G의 깊이가 2이다.

 

레벨(Level)

트리 구조에서는 같은 깊이를 가지고 있는 노드를 묶어서 레벨(level)로 표현할 수 있다. depth가 0인 루트 A는 level1

depth가 1인 B와 C의 level은 2이다. 같은 레벨에 나란히 있는 노드를 형제노드라 한다.(B와 C는 형제노드이다)

 

높이(Height)

트리 구조에서는 리프 노드를 기준으로 루트까지의 높이(height)를 표현할 수 있다.

위 그림에서의 리프노드인 J를 높이 0으로 보고 j의 부모노드인 G가 높이 1, G의 부모노드인 C가 높이 2, 루트인 A가 높이 3이다. 즉 부모노드의 높이는 자식노드의 높이+1로 볼 수 있다.

 

 

 

Graph

그래프는 여러개의 점들이 서로 복잡하게 연결되어 있는 관계를 표현한 자료구조이다.

우리가 일반적으로 그래프에 대해서 생각한다면 수학적인 그래프를 생각할 것이다.

수학적 그래프 예시

X축과 Y축이 존재하고 X축의 값에 따라 Y축의 값을 나타내는 것.

그러나 자료구조의 그래프는 거미줄처럼 여러개의 점들이 선으로 이어져 있는 복잡한 네트워크망 같은 모습을 가지고 있다.

자료구조 그래프 예시

 

Graph의 구조

• 직접적인 관계가 있는 경우 두 점 사이를 이어주는 선이 있다.
• 간접적인 관계라면 몆 개의 점과 선에 걸쳐 이어진다.
• 하나의 점을 그래프에서는 정점(vertex)이라고 표현하고, 하나의 선은 간선(edge)이라고 한다.

 

인접 행렬

두 정점을 바로 이어주는 간선이 있다면 이 두 정점은 인접하다라고 이야기한다.

인접행렬은 서로 다른 정점들이 인접한 상태인지를 표시한 행렬로 2차원 배열의 형태로 이루어져 있다.

만약 A라는 정점에서 B라는 정점이 이어져 있다면 1(true) 이어져 있지 않다면 0(false) 으로 표시한 일종의 표이다.

 

출처 - 코드스테이츠

다음의 경우일 때 아래와 같이 나타낸다.

{0, 0, 1} - A의 진출차수는 한개이다. A  -> C

{1, 0, 1} - B의 진출차수는 두개이다. B -> A, B -> C

{1, 0, 0} - C의 진출차수는 한개이다. C -> A

 

인접행렬은 가장 빠른 경로(shortest path)를 찾고자 할 때 주로 사용된다.

 

 

인접 리스트

인접 리스트는 각 정점이 어떤 정점과 인접하는지를 리스트의 형태로 표현한다.

각 정점마다 하나의 리스트를 가지고 있으며, 이 리스트는 자신과 인접한 다른 정점을 담고 있다.

위 사진의 그래프를 인접 리스트로 표현하면 아래와 같다.

 

출처 - 코드스테이츠

여기서 한가지 의문을 품자면 B에서 이어지는 간선은 A와 C 두개가 있는데 왜 A를 먼저가는지이다.

여기에 대한 답은 "보통은 중요하지 않다"이다.

그래프, 트리, 스택, 큐 등 모든 자료구조는 구현하는 사람의 편의와 목적에 따라 기능을 추가/삭제할 수 있다. 그래프를 인접 리스트로 구현할 때, 정점별로 살펴봐야 할 우선 순위를 고려해 구현할 수 있다. 이때, 리스트에 담겨진 정점들을 우선 순위별로 정렬할 수 있다. 우선 순위가 없다면, 연결된 정점들을 단순하게 나열한 리스트가 된다.

 

우선 순위를 다뤄야 한다면 더 적한한 자료구조(queue, heap 등)를 사용하는 것이 합리적이다.

 

인접 리스트는 언제 사용하는가?

메모리를 효율적으로 사용하고 싶을 때 인접 리스트를 사용한다.

인접 행렬은 연결 가능한 모든 경우의 수를 저장하기 때문에 상대적으로 메모리를 많이 차지한다.