[자료구조] 트리 (Tree)

 

트리란?

트리(Tree)는 나무입니다. 데이터의 자료를 나무의 형태처럼 나타냈다고 해서 트리라는 이름이 붙었습니다. 물론 데이터들을 정말 2차원 형태의 나무 그림으로 표현하는 것이 아니고, 앞에서 살펴본 연결 리스트에서 노드를 만들었듯이 여기서도 노드를 만들어서 서로 연결하며 구조를 만들면 됩니다.

 

나무를 자세히 살펴보면 나뭇가지가 나있는 것을 알 수 있는데, 이 형태를 뒤집어보면 가장 위에 뿌리가 오고 맨 아래에 나뭇잎이 매달려 있는 것을 상상해볼 수 있습니다. 이런 구조는 컴퓨터에서 자주 사용됩니다.

 

파일의 구조. 상위에 있는 폴더 밑에 하위 폴더들이 존재함.

파일의 구조가 트리의 형태와 유사합니다. 이 곳에서는 UX가 폴더로 이루어져있어 트리라고 생각하지 못할 수도 있지만 노드로 표현한다면 트리처럼 나타낼 수 있어 결국 계층적인 데이터 구조를 표현할 수 있습니다.

 

트리의 용어 정리

트리(Tree) 한 개 이상의 노드로 이루어진 유한 집합입니다. 이들 중 제일 위에 있는 노드는 루트(Root)라 부릅니다. 나머지 노드들은 서브트리(subtree)라 부릅니다.

노드(node) 트리를 구성하는 각각의 요소(1, 2, 3, ...)들을 말합니다.

간선(edge) 노드와 노드를 잇는 선입니다. 트리 외에 앞으로 나올 그래프도 노드와 간선을 그대로 사용합니다.

루트(root) 계층적인 구조에서 가장 높은 곳에 있는 노드입니다. 그림에서 루트는 6이고, 오른쪽 아래에 있는 서브트리의 루트는 7입니다.

서브트리(subtree) 루트를 제외한 나머지 노드입니다.

레벨(level) 트리의 각 층에 번호를 매기는 것입니다. 루트의 레벨은 0입니다.

다른 곳에서는 루트의 레벨을 1로 설명하는 곳도 있는데, 둘 다 맞습니다. 통상적으로 루트 노드 레벨을 0이라고 하는 것이 일반적이라고 합니다. 이 포스트에서는 루트 레벨을 0이라고 하겠습니다.
https://stackoverflow.com/questions/59151282/what-is-level-of-root-node-in-a-tree

부모 노드(parent node) 특정 노드보다 상위 레벨에 있는 노드입니다. 그림에서 3의 부모 노드는 2입니다.

자식 노드(children node) 특정 노드보다 하위 레벨에 있는 노드입니다. 그림에서 2의 부모 노드는 3입니다.

단말 노드(terminal node / leaf node) 자식 노드가 없는 노드입니다. 리프 노드라고도 부릅니다. 그림에서 1, 3, 5, 8, 10, 11이 단말 노드입니다.

비단말 노드(nonterminal node) 단말 노드가 아닌 노드들입니다.

형제 관계(sibling) 같은 부모 아래서 나온 자식 노드들입니다. 그림에서는 8과 9가 형제 관계라고 볼 수 있겠습니다. 그 외 여러 노드들이 형제 관계에 속해있습니다.

조상 노드(ancestor node) 루트 노드에서 임의의 노드까지의 경로를 이루고 있는 노드들입니다. 그림에서 1의 조상 노드들은 2, 4, 6입니다.

차수(degree) 어떤 노드가 가지고 있는 자식 노드의 개수입니다. 이 때, 손자들까지 내려가서 세지 않게 조심해야 합니다. 그림에서 9의 차수는 2입니다. 한편, 노드의 차수에서 가장 큰 차수가 트리의 차수가 됩니다. 따라서 그림의 트리 차수는 2입니다.

트리의 높이(height) 루트 노드에서 제일 끝에 있는 리프 노드가 떨어져 있는 정도를 나타냅니다. 그림의 트리 높이는 4입니다.

 

트리의 종류

이진 트리, 힙 트리, AVL 트리, 2-3 트리, 2-3-4 트리 등이 있습니다. 다음 포스팅에서는 이진 트리를 다루어보겠습니다.