[데이터베이스] 자료구조 - 트리(Tree)의 개념(비선형 구조)

오늘은 자료 구조 중 비선형 구조에 해당하는 트리(Tree)에 대해 포스팅을 하려고 합니다.

선형구조 자료 구조에 대해 확인을 하시고 싶으면 아래의 링크를 참고 부탁드립니다.
2022.10.22 - [Intelligence Technology] - [데이터베이스] 자료구조 - 스택(Stack), 큐(Queue), 데크(Deque)의 개념 및 처리 방법 비교

[데이터베이스] 자료구조 - 스택(Stack), 큐(Queue), 데크(Deque)의 개념 및 처리 방법 비교

2022.10.22 - [Intelligence Technology] - [데이터베이스] 자료구조의 개념 및 리스트(List)의 특징(선형 구조)

[데이터베이스] 자료구조의 개념 및 리스트(List)의 특징(선형 구조)

트리(Tree)란

노드(Node), 가지(Branch)를 이용하여 하단으로 뻗어나가는 형식의 자료 구조 형태를 의미합니다. 가족 간의 관계를 나타내는 족보나 기업 조직도를 연상하시면 쉽게 이해하실 수 있을 겁니다.

<트리 구조>

그럼 트리 구조를 이루는 각각의 요소들을 어떻게 부르는지 알아보겠습니다.
우선 노드(Node)는 트리의 기본 요소로 자료를 의미합니다. 위 트리 구조에서 노드는 A, B, C, D, E, F, G, H, I, J, K, L, M으로 된 동그란 원이 해당됩니다. 그중 가장 위에 있는 노드 A는 근 노드(Root Node)라고 부릅니다.
디그리(Degree)는 차수라고도 부르며 각 노드에서 뻗어 나온 가지(Branch)의 수를 의미합니다. A, D노드의 디그리는 3이 되며, B노드의 경우는 2, I노드의 경우는 디그리가 1이 됩니다.
만약 트리의 디그리를 묻는다면 노드들 중 가장 차수가 많은 디그리 하나를 의미합니다. 따라서 위 트리를 예시로 보면 트리의 디그리는 3이 됩니다.

트리의 깊이에 따라 레벨(Level)과 깊이(Depth)로 표현을 하기도 합니다.
레벨(Level)은 근 노드가 1이 되며 하단에 위치한 노드(B, C, D)는 레벨 2가 됩니다. 밑으로 갈수록 +1이 됩니다.
깊이(Depth)는 트리에서 노드가 가질 수 있는 최대 레벨을 뜻합니다. 따라서 위 트리 구조의 전체 깊이는 4로 볼 수 있습니다.


각 노드 간의 관계 따라 단말 노드와 비단말 노드, 조상 노드, 자식 노드, 부모 노드, 형제 노드로 구분을 합니다.
단말 노드(Terminal Node)는 리프 노드(Leaf Node)라고도 부르며 자식 노드가 하나도 없는 노드를 의미합니다. 즉 차수(Degree)가 0인 노드입니다.
비단말 노드(Non-Terminal Node)는 자식이 하나라도 있는 노드를 의미하며 차수(Degree)가 0이 아닌 노드입니다.
조상 노드(Ancestors Node)는 특정 노드에서 루트 노드까지 이동할 때 경로상에 있는 노드들을 의미합니다. 예를 들어, M의 조상 노드는 I, D, A가 됩니다.
자식 노드(Son Node)는 특정 노드와 가지로 연결된 다음에 오는 노드들을 의미합니다. 예를 들어 D의 자식 노드들은 H, I, J가 됩니다.
부모 노드(Parent Node)는 상위 단계에 위치한 노드들 중 가지로 연결된 노드를 의미합니다. 예를 들어 I의 부모 노드는 D가 됩니다.
형제 노드(Brother Node)는 동일한 부모를 갖는 노드들을 의미합니다. 예를 들어 H노드의 형제 노드들은 I, J가 됩니다.

이상으로 기본적인 트리에 대한 포스팅을 마치겠습니다.
다음 시간에는 이진트리 및 트리의 자료 처리 순서에 대해 포스팅을 할 계획입니다.
트리는 정보처리기사 및 시험 문제로도 자주 등장을 하니 용어들은 꼭 숙지를 하시는 게 좋습니다.

오늘도 똑구의 꿀팁 블로그를 방문해 주셔서 감사합니다.