[자료구조] 트리 구조의 기본 개념과 용어 정리

이민선(Jasmine)·2023년 2월 17일

선형 자료 구조는 어느 정도 살펴봤으니 이제 비선형 자료구조에 들어가자~~ 이진트리부터 시작해서 해시테이블까지 쭉 돌아보기 전에 트리와 그래프 기초부터 짚고 넘어가려고 한다.

1. 트리와 그래프와의 비교

그래프 : 정점과 간선으로 이루어진 자료구조.
트리 : 그래프 중 하나이다. 그래프의 특징처럼 정점과 간선으로 이루어저있고, 트리 구조로 배열된 일종의 계층적 데이터 집합이다.
노드들의 집합이며, 각 노드는 값(value)과 다른 노드들을 가리키는 레퍼런스들로 구성된다.

⭐️ 그래프와의 차이점

1) 부모 자식 계층 구조를 가진다.

2) 간선 수 = 노드 수 - 1

2. 트리 관련 주요 용어 정리

노드의 구분:
1) 루트 노드 : 트리의 최상단에 있는 노드. 트리의 시작점
2) 자녀 노드: 모든 노드는 0개 이상의 자녀 노드를 가진다!
3) 부모 노드: 자녀 노드를 가지는 노드
4) 형제 노드: 같은 부모를 가지는 노드들
5) 조상 노드 : 부모 노드를 따라 루트 노드까지 올라가며 만나는 모든 노드들
6) 자손 노드 : 자녀 노드를 따라 내려가며 만날 수 있는 모든 노드들
7) 내부 노드(internal node, branch node, inner node) : 자녀 노드를 가지는 모든 노드
8) 외부 노드(external node, leaf node, outer node, terminal node) : 자녀 노드가 없는 노드

경로: 한 노드에서 다른 노드 사이의 노드들의 시퀀스. 출발 노드와 도착 노드를 포함하여 표현함.
경로 길이(length): 경로에 있는 노드들의 수 (간선의 수가 아님!! 아래에 있는 그밖의 것들은 전부 간선의 수로 따진다.)
두 노드 사이의 거리(distance): 두 노드의 최단 경로의 간선 수

노드의 높이(height): 해당 노드에서 리프노드까지 가장 긴 경로의 간선 수(리프 노드의 높이 = 0, 트리의 높이 = 루트 노드의 높이 = 트리의 깊이)

노드의 깊이(depth): 루트 노드에서 해당 노드까지 경로의 간선 수(루트 노드의 깊이 = 0, 트리의 깊이 = 트리에 있는 노드들의 깊이 중 가장 긴 깊이 = 트리의 높이)

노드의 차수(degree): 노드의 자녀 노드 수 (트리의 차수 = 트리의 노드들의 차수 중 가장 큰 차수)

노드의 레벨(level): 노드와 루트 노드 사이의 경로에서 간선의 수 (루트 노드의 레벨 = 0). 보통 깊이와 비슷한 의미를 지닌다.

넓이(width): 임의의 레벨에서 노드의 수

노드의 크기(size): 자신을 포함한 자손 노드의 수 (트리의 크기 = 트리의 모든 노드의 수)

서브트리(subtree): 트리 내의 하위 집합. 또는 트리 내의 부분 집합. 각 노드의 자녀 노드들은 재귀적으로 서브 트리를 구성한다.