티스토리 뷰
주의 사항!
- 이 글은 제가 직접 공부하는 중에 작성되고 있습니다.
- 따라서 제가 이해하는 그대로의 내용이 포함됩니다.
- 따라서 이 글은 사실과는 다른 내용이 포함될 수 있습니다.
지금부터 배우게 될 트리는 고급 자료구조로 구분이 됩니다. 그리고 앞서 설명한 선형 자료구조들과 달리 비선형 자료구조이기 때문에 어렵게 느껴질 수 있습니다.
자료구조라고 하면 보통은 데이터를 저장하고 정리하고 꺼내는 것이 전부인 것으로 생각하기 쉽습니다. 물론 지금까지 배운 리스트, 스택, 큐, 덱의 경우는 그래 왔습니다. 하지만 이를 트리에 대해서도 동일하게 생각하면 안 됩니다.
트리는 단순히 데이터를 저장하고 꺼내는 자료구조가 아닙니다. 트리는 계층적 관계를 표현하는 자료구조입니다. 때문에 나중에 보게 될 트리의 ADT를 볼 때, 데이터의 저장, 검색, 삭제가 유용한지의 관점에서 보면 안 됩니다. 트리의 구조로 이루어진 무언가를 표현하기에 적절히 정의되어 있는가의 관점으로 바라봐야 합니다.
트리는 위와 같은 구조를 가집니다. 사실 트리는 주변에서도 쉽게 접할 수 있는 자료구조입니다. 컴퓨터의 디렉터리 구조도 트리의 예가 되고, 집안의 족보나 기업 및 정부의 조직도도 트리의 예가 됩니다.
트리에 관해서 제법 많은 용어가 정의되어 있습니다. 위 그림을 대상으로 트리 관련 용어들을 정리해 보겠습니다.
- 트리의 구성 요소 A, B, C, D, E, F와 같은 요소들을 '노드(node)'라고 합니다.
- 노드와 노드를 연결하는 붉은 선을 '간선(edge)'이라고 합니다.
- 트리 구조에서 최상위에 존재하는 A와 같은 노드를 '루트 노드(root node)'라고 합니다.
- 아래로 또 다른 노드가 연결되어 있지 않은 E, F, C, D와 같은 노드를 '단말 노드(terminal node)'라고 합니다.
- 단말 노드를 제외한 모든 노드로 A, B와 같은 노드를 '내부 노드(internal node)'라고 합니다.
그리고 노드 간에는 부모, 자식, 형제의 관계가 성립되어 다음과 같이 표현할 수 있습니다.
- 노드 A는 노드 B, C, D의 부모 노드(parent node)이다.
- 노드 B, C, D는 노드 A의 자식 노드(child node)이다.
- 노드 B, C, D는 부모가 같으므로 서로가 서로에게 형제 노드(sibling node)이다.
여기서 조금 더 나아가서 조상과 후손의 개념도 있습니다. 특정 노드의 위에 위치한 모든 노드를 가리켜 '조상 노드'라고 하며, 특정 노드의 아래에 위치한 모든 노드를 가리켜 '후손 노드'라고 합니다. 즉, 노드 A와 B는 노드 E의 조상 노드입니다. 반면 노드 B, C, D, E, F는 모두 노드 A의 후손 노드입니다.
큰 트리는 작은 트리로 구성됩니다. 위 그림은 루트 노드가 A인 트리이지만, 위 트리는 루트 노드가 B인 트리와, 루트 노드가 C인 트리로 구성되어 있습니다. 이렇듯 큰 트리 안의 작은 트리를 '서브 트리'라고 합니다.
위 그림과 같은 트리를 '이진 트리'라고 합니다. 위 그림을 보면 이진 트리에 대해 다음과 같이 생각할 수 있습니다.
"하나의 노드에 대해 두 개의 노드가 자식으로 달린 트리를 이진 트리라고 하는구나"
얼추 맞는 말이지만 완전하지는 않습니다. 이진 트리는 다음의 두 조건을 만족해야 합니다.
- 루트 노드를 중심으로 두 개의 서브 트리로 나뉜다.
- 나뉜 두 서브 트리도 모두 이진 트리여야 한다.
이진 트리의 조건을 정의하는데 이진 트리라는 단어가 사용되었습니다. 따라서 위 정의는 옳지 못하다고 생각할 수 있습니다. 하지만 이는 온전한 정의입니다. 왜냐하면 이진 트리 자체가 재귀적이기 때문입니다. 그런데 이진 트리의 조건이 여기 까지라면 다음의 트리는 이진 트리로 볼 수 없을 것입니다.
하지만 위 트리도 이진 트리입니다. 왜냐하면 이진 트리와 관련해서 다음의 내용이 추가로 정의되어 있기 때문입니다.
"노드가 위치할 수 있는 곳에 노드가 존재하지 않는다면, 공집합 노드가 존재하는 것으로 간주한다. 물론 공집합 노드도 이진 트리의 판단에 있어서 노드로 인정한다."
이 정의로 인해 위의 이진 트리 같지 않은 트리는 다음과 같은 형태가 됩니다.
이렇게 공집합 노드가 추가됨에 따라 이진 트리가 될 수 있는 것입니다. 이 정의로 인해 다음과 같은 트리도 이진 트리가 됩니다.
공집합 노드로 인해서 다음과 같은 형태가 되기 때문입니다.
이렇듯 이진 트리는 생각보다 그 폭이 넓음을 알 수 있습니다. 따라서 이진 트리도 그 특성에 따라서 보다 세분화됩니다.
이진트리의 몇몇 분류를 소개하기에 앞서 트리 관련 용어인 '레벨'과 '높이'를 설명하겠습니다. 트리에서는 각 층별로 숫자를 매겨서 이를 트리의 '레벨'이라고 하고, 트리의 최고 레벨을 가리켜 '높이'라고 합니다.
위 트리의 최고 레벨은 2이며, 높이 또한 2가 됩니다.
이제 '완전 이진 트리'에 대해 설명하겠습니다. 완전 이진 트리란, 마지막 레벨을 제외한 모든 레벨의 노드가 완전히 채워져 있으며, 마지막 레벨에 대해서는 가능한 한 왼쪽부터 채워져 있는 트리를 말합니다. 따라서 위의 그림의 트리는 완전 이진 트리가 됩니다.
물론 다음의 트리도 완전 이진 트리입니다.
마지막 레벨을 제외한 모든 레벨의 노드가 완전하게 채워져 있고, 마지막 레벨에 대해서는 가능한 한 왼쪽부터 노드가 채워져 있기 때문입니다.
'포화 이진 트리'란, 다음의 트리와 같이 모든 레벨에 대해서 노드가 완전히 채워져 있는 트리를 말합니다.
'공부 일지 > 자료구조 공부 일지' 카테고리의 다른 글
| Chapter 08. 이진 트리의 순회 (0) | 2021.03.16 |
|---|---|
| Chapter 08. 이진 트리의 구현 (0) | 2021.03.16 |
| 연습문제 07. 1 덱을 기반으로 큐를 구현하기 (0) | 2021.03.16 |
| Chapter 07. 덱(Deque)의 이해와 구현 (0) | 2021.03.16 |
| Chapter 07. 큐의 활용 (16) | 2021.03.15 |