# Tree

Author: Dion

## 트리 자료구조 공부

### 트리 개괄

트리는 응용 분야가 굉장히 다양한 자료구조입니다.

어떤 트리는 조직도 같이 계층적인 데이터를 표현하는데 사용되고, 어떤 트리는 수식을 표현할 때 사용됩니다.

또 어떤 트리는 집합을 나타내는데 사용되며, 심지어는 데이터의 탐색을 위한 트리도 있습니다.

트리의 가장 중요한 응용 분야 중 하나는 **탐색**인데, 탐색 트리는 공부할 것도 많고 탐색 알고리즘을 이해해야 하기 때문에 어렵다고 볼 수 있습니다.

### 트리의 기초

트리(Tree)는 나무를 닮은 자료구조라고 하지만, 정확히는 뿌리를 중심으로 뻗어나오는 그 구조를 닮았습니다.

컴퓨터 과학에서 트리는 굉장히 활용도가 높은 자료구조입니다.

운영체제의 파일 시스템이 트리 구조로 이루어져 있고, HTML, XML을 다룰 때 사용하는 DOM(Document Object Model)도 트리 구조로 이루어져 있습니다.[그래서 DOM Tree라고 함]

검색 엔진이나, 데이터 베이스도 트리 자료구조에 기반해서 구현됩니다. (여기에 사용되는 트리 자료구조가 바로 탐색 트리라고 하는 것임.)

### 트리의 구조

트리는 뿌리(Root), 가지(Branch), 잎(Leaf)의 세 가지 요소로 이루어져 있습니다.


뿌리, 가지, 잎 모두가 똑같은 Node라는 것을 염두에 둬야합니다. 이들은 그저 트리 내의 위치에 따라 명칭만 달라질 뿐입니다.

뿌리인 Root Node는 트리의 가장 위에 있는 Node를 가리키고 가지(Branch)는 뿌리와 잎 사이에 있는 모든 노드를 일컫는 말입니다.

그리고 가지의 끝에 매달려 있는 노드를 잎(Leaf)이라고 부릅니다. 끝에 있다고 해서 단말(Terminal) 노드라고 부르기도 합니다.


B에서 D, E, F가 나오게 되는데 B를 D, E, F의 부모(Parent)라고 부르고, D, E, F를 자식(Child, Children)이라고 부릅니다.

B와 C는 같은 부모(A)를 가진 형제(Sibling)라고 부릅니다.

B와 G는 아무런 관계를 가지고 있지 않습니다.

### 트리의 경로(Path)

트리에서 경로는 한 노드에서부터 다른 한 노드까지 이르는 길 사이에 놓여있는 순서입니다.


예를 들어서 A노드에서 J노드까지 이른다면 A노드에서 출발하여, B노드를 거치고, E노드를 거친다음 J노드에 도착하게 됩니다.

이 때 "A-B-E-J"를 A에서 J까지의 경로라고 합니다. (Path between A & J)

경로는 길이(Length)라는 속성을 가지는데, 출발하는 노드에서 목적지 노드까지 거쳐야하는 노드의 개수를 얘기합니다.

이 때, 출발하는 노드는 포함하지 않기 때문에 A에서 J까지의 경로는 3의 길이를 가집니다.

노드의 깊이(Depth)는 루트 노드에서 해당 노드까지의 경로의 길이를 뜻합니다.


A에서 H까지의 경로가 "A-D-H" 이므로 경로의 길이는 2입니다. 따라서 깊이는 2입니다.

그렇다면, 루트의 깊이는 얼마일까요? 0입니다.

깊이와 비슷한 개념의 용어로 레벨(Level)과 높이(Height)가 있습니다. 비슷한 것입니다. 같은 것이 아닙니다.

레벨은 깊이가 같은 노드의 집합을 일컫는 말입니다.

트리의 높이는 '가장 깊은 곳'에 있는 잎 노드까지의 깊이를 뜻합니다. 그럼 위 그림에 있는 트리의 높이는 얼마일까요?

3입니다.

마지막으로 설명할 개념은 차수(Degree)입니다. 노드의 차수라함은 그 노드의 자식 노드 개수를 말하는 것이고, 트리의 차수라함은 트리 내에 있는 노드들 가운데 자식 노드가 가장 많은 노드의 차수를 말하는 것입니다.

위의 그림에서는 A노드의 차수는 3이고, B 노드의 차수는 2입니다. 트리 전체적으로 보면 자식이 가장 많은 노드는 A이므로 위 트리의 차수는 3입니다.

### 트리의 표현

트리는 여러가지 방법으로 표현이 가능합니다. 거꾸로 된 나무 그림이 대표적이지만, 그 외에도 여러 방법들이 사용됩니다.

#### 중첩된 괄호(Nested Parenthesis) 표현법

같은 레벨의 노드들을 괄호로 같이 묶어 표현하는 방법입니다.

읽기는 다소 어렵지만, 트리를 하나의 공식처럼 표현할 수 있는 장점이 있습니다.

#### 중첩된 집합(Nested Set) 표현법

트리가 하위 트리의 집합이라는 관계를 잘 표현할 수 있음


#### 들여쓰기(Indentation) 표현법

마지막으로 트리는 들여쓰기 (Indentation)로도 표현이 가능합니다.

들여쓰기 표현법은 자료의 계층적인 특징을 잘 나타냅니다.

### 노드의 표현

노드의 표현은 부모와 자식, 그리고 형제 노드를 서로 연결짓는 방법입니다.

트리 노드를 표현하는 방법에는 두 가지가 있습니다. 하나는 'N-링크(N-Link)' 표현법이고, 다른 하나는 '왼쪽 자식-오른쪽 형제(Left Child-Right Sibling)' 표현법입니다.

#### N-Link

N-Link는 노드의 차수가 N이라면, 노드가 N개의 링크를 가지고 있어서 이 링크들이 각각 자식 노드를 가리키도록 노드를 구성하는 방법입니다.

이 노드로 트리를 이룬다면 트리는 다음과 같은 모습이 됩니다.


이 표현법은 언뜻 봤을 때에는 쓸만해 보이지만, 차수(Degree)가 노드마다 달라지는 트리에는 적용하기가 어려운 단점이 있습니다.

### Left Child-Right Sibling 표현법

위의 문제를 해결하기 위한 표현법입니다. 이 방법을 사용하면 N개의 차수를 가진 노드의 표현이 두 개의 포인터, 왼쪽 자식-오른쪽 형제만으로 가능하게 됩니다.


이 표현법을 사용하는 트리에서 어느 한 노드의 모든 자식 노드를 얻으려면 왼쪽 자식 노드에 대한 포인터만 있으면 됩니다.

이 포인터를 이용해서 왼쪽 자식 노드의 주소를 얻고, 또 그 다음 오른쪽 형제 노드의 주소를 계속해서 얻어 나가면 결국에는 모든 자식 노드를 얻을 수 있습니다.

### 추가로 공부할 내용

#### 이진 트리

##### 수식트리

#### 이진 탐색 트리

#### 레드 블랙 트리

### References

뇌를 자극하는 알고리즘

http://www.btechsmartclass.com/data_structures/tree-terminology.html

https://adrianmejia.com/data-structures-for-beginners-trees-binary-search-tree-tutorial/

https://en.wikipedia.org/wiki/Nested_set_model

소감

Dion
다 하고 적기

Ever
다 하고 적기

Hamill
다 하고 적기

Lynn
다 하고 적기

Sunny
다 하고 적기