[Python] 비선형 자료구조 - 트리(Tree)

자료구조는 선형 구조와 비선형 구조로 나눌 수 있다.

자료구조 중 대표적인 비선형 구조로는 그래프가 있다. 이 글에는 자료구조 그래프의 특수한 형태 중 하나인 트리에 대해 간단하게 정리했다.

트리의 장점 중 하나는 자료에 대한 삽입, 삭제, 탐색 등의 연산이 다른 자료구조에 비해 유리한 경우가 많다는 점이다. 이진 탐색 트리를 이용하면 아래와 같이 정렬된 상태를 유지하는 배열보다 시간 복잡도가 유리하다.

	삽입	삭제	탐색
정렬된 배열	O(N)	O(N)	O(logN)
이진 탐색 트리	O(logN)	O(logN)	O(logN)

 

1. 그래프와 트리

1) 그래프

정점(vertex)과 간선(edge)으로 이루어져 있는 자료구조

(1) 정점(vertex): 자료, 상태 등 무언가를 담고 있는 요소. 노드라고도 표현함.

(2) 간선(edge): 정점 간의 관계를 나타내는 요소. 방향이 있을 수도, 없을 수도 있음.

(3) 경로: 어떤 정점에서 다른 정점으로 이동하기 위해 거치는 모든 정점

- 간선에서 방향이 존재하는 그래프는 '유향 그래프'라고 칭한다.

- 어떤 정점에서 출발하여 자기 자신으로 돌아오는 경로를 '사이클'이라고 표현한다.

그림의 출처와 더 자세한 그래프 내용: https://medium.com/@gwakhyoeun/til-%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-graph-%EC%9D%B4%ED%95%B4%ED%95%98%EA%B8%B0-6f92fd87a0bd

 

2) 트리

트리는 위와 같은 구조를 가지며, 아래와 같은 특성을 가진 그래프 자료구조다.

(1) 트리의 간선들은 모두 방향성을 갖는다.

(2) 어떤 정점을 가리키는 정점의 개수는 최대 1개이다.

(3) 어떤 정점에서 다른 정점으로 이동할 수 있는 경로는 1개이다.

(4) 트리는 사이클을 갖지 않는다.

- 디렉터리(폴더 구조)가 대표적인 트리 구조의 예시이다.

 

3) 트리 용어

(1) 루트 노드(Root Node): 다른 어떠한 정점도 가리키지 않는 정점

(2) 리프 노드(Leaf Node): 가리키는 정점이 없는 정점

(3) 깊이: 루트 노드로부터의 거리

(4) 부모 노드(Parent Node), 자식 노드(Child Node): 임의의 정점 A가 다른 정점 B를 가리킬 때, A는 부모 노드, B는 자식 노드.

 

 

2. 트리 종류

이진 트리의 여러 유형

1) 이진 트리

- 각 정점들이 자식 노드를 최대 2개까지만 갖는 트리

- 이진 탐색 트리 등 유용하게 활용되는 트리 중에는 대부분 이진 트리를 응용한 것이 많다.

 

2) 포화 이진 트리

- 리프 노드를 제외한 모든 정점이 항상 자식을 2개씩 갖고 있으면서 모든 리프 노드의 깊이가 동일한 트리

- 포화 이진 트리의 높이를 h라고 하면, 정점의 개수는 항상 (2^h - 1)개다.

 

3) 완전 이진 트리

- 마지막 깊이를 제외하고 모든 정점이 완전히 채워져 있으며, 마지막 깊이의 정점들은 가능한 한 왼쪽에 있는 트리

- 포화 이진 트리에서 마지막 깊이의 정점이 오른쪽에서부터 일부 제거된 트리라고 볼 수 있다.

- 높이를 h라고 하면, 정점의 개수는 2^(h-1)개 이상 (2^h - 1)개 이하이다.

 

4) 정 이진 트리

- 리프 노드를 제외한 모든 노드들이 2개의 자식 노드를 갖고 있는 이진 트리

- 모든 정점은 0개 또는 2개의 자식 노드를 가진다.

 

 

3. 트리 순회

트리를 순회하는 방법은 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS)이 있다. 이런 순회 방법은 여러 알고리즘 문제에서도 유용하게 사용할 수 있는데, 다른 글에서 더 자세하게 정리해야지.

1) 깊이 우선 탐색(DFS, Depth First Search)

2) 너비 우선 탐색(BFS, Breadth First Search)