[자료구조] 8-1. 트리의 개요

목표: 트리에 대해 알아보자

앞서 소개된 선형 자료구조들과 달리 트리는 비선형 자료구조이기 대문에 많이 다르게 느껴질 수 있고, 트리는 고급 자료구조로 구분이 되는 만큼 학습에 집중을 요한다.

 

<트리의 개요>

트리는 계층적 관계(Hierarchical Relationship)을 표현하는 자료구조이다.

컴퓨터의 디렉터리 구조나 집안의 족보, 기업 및 정부의 조직도가 트리의 예가 된다.

삼우애드 회사조직도-트리의 예

위 그림도 그렇지만, 사실 트리 구조는 나무처럼 보이지는 않는다. 그럼에도 트리 구조라 하는 이유는 '가지를 늘려가며 뻗어나간다'는 공통점이 있기 때문이다.

타이타닉 호 탑승객의 생존 여부를 나타내는 결정 트리 - 위키 백과

위 유형의 트리를 가리켜 의사 결정 트리(decision tree)라고 한다. 의사 결정 트리는 위 사진 처럼, 다양한 데이터 분석 기법의 유용한 도구가 되며, 경영학 등 공학 이외의 영역에서도 유용하게 사용되는 도구이다.

 

<트리 관련 용어의 소개>

- 파이썬 알고리즘 인터뷰

노드(node): 트리의 구성요소에 해당하는 A, B, C, D, E, F, ...와 같은 요소

간선(edge): 노드와 노드를 연결하는 연결선

루트 노드(root node): 트리 구조에서 최상위에 존재하는 A와 같은 노드

단말 노드(terminal node): 아래로 또 다른 노드가 연결되어 있지 않은 E, F, G, H, I와 같은 노드, 나무의 구조상 잎에 해당한다 하여 '잎사귀 노드(leaf node)'라고도 불린다.

내부 노드(internal node): 단말 노드를 제외한 모든 노드로 A, B, C, D와 같은 노드, 단말 노드가 아니라 하여 '비단말 노드(noninternal node)'라고도 불린다.

 

노드 간에는 부모(parent), 자식(child), 형제(sibling)의 관계가 성립된다. 부모와 자식의 관계는 상대적이며, 트리 구조상 위에 있을수록 촌수가 높다.

ㄴ노드 A는 노드 B, C의 부모 노드(parent node)이다.

ㄴ노드 B, C는 노드 A의 자식 노드(child node)이다.

ㄴ노드 B, C는 부모노드가 같으므로, 서로가 서로에게 형제 노드(sibling node)이다.

 

조상(Ancestor), 후손(descendant)의 관계도 있다.

ㄴ노드 A, B, D는 노드 E의 조상 노드이다.

ㄴ노드 B, C, D, E, F, G, H, I는 모두 노드 A의 후손 노드이다.

 

서브 트리(sub tree): 큰 트리에 속하는 작은 트리.

ㄴA가 루트 노드인 서브트리에는 B를 루트 노드로 하는 서브트리와 C를 루트 노드로 하는 서브트리가 있다. 서브트리 아래에 더 작은 서브트리가 있기도 하는데,  B를 루트 노드로 하는 서브트리에 D를 루트 노드로 하는 서브트리가 존재한다.

 

레벨(level): 각 층별로 매긴 숫자

높이(height): 트리의 최고 레벨

 

<이진 트리>

이진 트리(binary tree): 간단히 말하면, 자식 노드가 두 개씩 달린 트리.

-다음의 두 조건을 만족해야 함.

ㄴ루트 노드를 중심으로 두 개의 서브 트리로 나뉘어 진다.

ㄴ나뉘어진 두 서브 트리도 모두 이진 트리이어야 한다.(정의에 이진트리라는 단어가 나오는 이유는, 이진 트리의 조건 자체가 재귀적이기 때문)

-노드가 위치할 수 있는 곳에 노드가 존재하지 않는다면, 공집합 노드가 존재하는 것으로 간주한다. 공집합 노드는 이진 트리의 판단에 있어서 노드로 인정한다.

 

포화 이진 트리(full binary tree): 모든 레벨이 꽉 찬 이진트리. 노드를 더 추가하려면 레벨을 추가해야 함. 위에 사진에서 노드 H, I가 없다고 가정한다면, 포화 이진트리라고 할 수 있다.

완전 이진 트리(complete binary tree): 포화 이진 트리처럼 모든 레벨이 꽉 찬 상태는 아니지만, 차곡차곡 빈 틈 없이 노드가 채워진 이진트리. 노드가 위에서 아래로, 왼쪽에서 오른쪽의 순서대로 채워진 상태. 위의 사진의 트리는 완전 이진 트리라고 할 수 있다.

 

 

본 글은 윤성우의 열혈 자료구조를 읽으며 개인 공부 용으로 작성되었음을 밝힙니다.

book.naver.com/bookdb/book_detail.nhn?bid=6809127

윤성우의 열혈 자료구조