[Section 4] 트리(Tree)의 개념 이해 _ 트리 용어 정리

자료구조와 알고리즘 목차 보기

[INTRO] 자료구조와 알고리즘

0. INTRO

비-선형 자료구조는 자료가 순차적이지 않는 자료구조를 의미한다. 비-선형 자료구조는 대표적으로 트리와 그래프가 존재하는데, 이번에는 트리 자료구조 개념을 이해해보도록 하자.

1. 비-선형 자료구조 _ 트리의 개념

연결 리스트 자료구조에서 각 노드의 포인터가 가리키는 곳은 하나뿐이었다. 만약 데이터를 트리 형태로 저장하게 된다면, 각 노드의 포인터는 2개 이상의 노드를 지칭하게 된다. 다음의 그림을 참고하자.

 

트리의 개념

그림에서 처럼 데이터가 계속해서 뻗어나갈수록 데이터의 총량은 기하급수적으로 증가할 것이다. 따라서 트리에는 데이터와 관련된 다양한 용어들이 존재한다. 위에서 보인 레벨 1과 레벨 2가 그 예이다. 각각의 데이터에 해당하는 레벨 계층을 통해서 데이터의 위치를 짐작할 수 있다. 또 연결 리스트에서 보였던 헤드(head) 포인터는 룻트(root)라고 지칭한다. 즉, 모든 트리는 룻트라 불리는 가장 근본이 되는 데이터를 갖고 있다. 그리고 이 룻트가 지칭하는 데이터는 부모(paaents) 데이터가 존재하지 않는다. 

 

이외에 트리에 사용되는 용어를 간략히 정리해 두도록 하자.

2.  트리 용어 정리

• 간선(Edge)은 부모 데이터와 아이(child) 데이터를 이어주는 포인터 라인이다.
• 아이 데이터가 존재하지 않는 데이터를 잎(leaf) 노드라고 부른다.
• 자손(siblings) 데이터는 같은 계층(level)에서 같은 부모를 가지고 있는 데이터 집단을 의미한다.
• 잎 노드에 해당하는 데이터들은 모두 조상(ancestor) 데이터라 불리는 집단을 가지고 있다. 이 집단은 룻트부터 잎 노드까지를 이어주는 라인에 해당되는 데이터들을 의미한다. 그리고 이 조상 데이터 집단에서 특정 데이터 집단까지를 구분해주기 위해 어떤 데이터의 후손(descendant), 어떤 데이터의 조상(ancestors)이라고 부른다. 예를 들어 다음의 그림을 참고하자. (Ex; A, B는 C의 조상이고 D는 C의 후손이다.) 

트리 용어 설명 _ 조상과 후손

• 룻트는 레벨 0이라 부르기도 한다.
• 노드의 깊이(depth)는 룻트에서부터 임의의 노드까지의 길이를 의미한다. 여기에서 길이는 경로의 개수이다. 예를 들어, 위 그림에서 Root-A-B-C-D까지의 총 경로 개수는 4이다. 
• 노드의 높이(height)는 어떤 노드에서부터 그 노드의 후손에 해당하는 데이터들 중 잎 노드에 해당하는 데이터까지의 깊이를 의미한다. 예를 들어, 위 그림에서 데이터 C의 조상은 A, B이며 후손은 D이다. 따라서 데이터 C의 높이라 함은 C-D의 경로 개수인 1이다. 때때로 트리의 높이(Height of Tree)라는 용어를 사용하는데 이때는 최대 높이(Maximum height)에 해당하는 길이를 의미한다. 예를 들어, 위 그림에서 트리의 높이는 4이다. (Root-A-B-C-D)
• 어떤 노드의 사이즈(size)라 함은 그 노드 자신을 포함하는 총후손의 수를 의미한다. 예를 들어, 위 그림에서 데이터 C의 높이는 1이었지만, 데이터 C의 사이즈는 2가 된다. 
• 하위 트리(Subtree)는 트리의 룻트가 특정 노드가 되는 트리를 의미한다. 예를 들어, 하위 트리 C는 C-D 혹은 C- 흰 구슬을 일컫는 말이 된다. 
• 트리에서 매 노드(every node)는 룻트 노드에서부터 잎 노드를 제외한 노드까지의 하위 트리를 의미한다. 예를 들어, 다음의 그림을 참고하자. 데이터를 간단히 숫자로 표기하면, 매 노드는 Root-1-2와 Root-1-3을 지칭한다. 즉, 잎 노드를 제외하고 룻트의 후손 데이터 집단을 지칭하게 된다. 그리고 매 노드 역시 하위 트리가 된다.

매 노드 용어 _ 예시

• 매 노드는 가장 왼쪽의 하위 트리와 가장 오른쪽의 하위 트리를 지칭하는 용어가 있다. 각각 왼쪽 사선 트리(Left Skew Tree)와 오른쪽 사선 트리(Right Skew Tree)이다. 이 하위 트리에 해당하지 않는 매 노드에 해당하는 트리는 모두 사선 트리(Skew Tree)라고 부른다.

하위 트리 종류