[자료구조] 트리(Tree) 구조의 개념, 용어, 특징에 대해 알아보자!

반응형

 
 
Computer Science 모아보기 👉🏻 https://github.com/seoul-developer/CS

GitHub - seoul-developer/CS: 주니어 개발자를 위한 전공 지식 모음.zip

GitHub - seoul-developer/CS: 주니어 개발자를 위한 전공 지식 모음.zip

 
 
 

💋 트리 자료구조란?

• 데이터를 탐색하기 쉽도록 하기 위해서 계층적인 방식으로 정리한 구조
• 계층적인 관계의 노드들이 edge로 연결된 형태
• 각 노드는 값(value) + 다른 노드의 레퍼런스(ref)로 구성

 
A tree data structure is a hierarchical structure that is used to represent and organize data in a way that is easy to navigate and search. It is a collection of nodes that are connected by edges and has a hierarchical relationship between the nodes.
 

💋 트리 자료구조 용어

 

이미지 출처: https://www.geeksforgeeks.org/introduction-to-tree-data-structure-and-algorithm-tutorials/

 

✔️ 구조 용어

• 간선(edge)
• 노드와 노드를 연결하는 선 (link, branch)
• 구현 관점에서는 레퍼런스를 의미
• 루트 노드(Root Node)
• 위 예시에서 A 는 루트 노드
• 트리의 최상단 노드로 시작점 ⇒ Parent Node가 없음
• A non-empty tree must contain exactly one root node and exactly one path from the root to all other nodes of the tree.
• 자녀 노드(Child Node)
• D, E는 B의 자녀 노드
• 모든 노드는 0개 이상의 자녀 노드를 가진다.
• 부모 노드(Parent Node)
• 자녀 노드를 가지는 노드
• B는 D, E의 부모 노드
• The node which is a predecessor of a node is called the parent node of that node. {B} is the parent node of {D, E}.
• 형제 노드(Sibling)
• 같은 부모를 가지는 노드들
• D,E는 형제 노드
• 조상 노드(Ancestor of a Node)
• 부모 노드를 따라, 루트 노드까지 올라가며 만나는 모든 노드
• A,B는 E의 조상 노드
• 자손 노드(Descendant)
• 자녀 노드를 따라 내려가며 만날 수 있는 모든 노드
• I, M, N은 E의 자손 노드
• 내부 노드(Internal node)
• 자녀 노드를 가지는 노드
• Leaf Node를 제외한 모든 노드
• 외부 노드(Leaf Node / External Node)
• 자녀 노드가 없는 노드
• K, L, M, N, O, P, G는 외부 노드

 

✔️ 계산 용어

• 경로(Path)
• 한 노드에서 다른 노드 사이의 노드의 시퀀스(sequence)
• A에서 J노드의 경로는 A - C - F -J
• 경로 길이(length of path)
• 경로에 있는 노드의 수
• A에서 J노드의 경로 길이는 4
• 노드의 높이(height)
• 노드에서 리프 노드까지 가장 긴 경로의 간선 수 (때에 따라 노드의 수로 세기도 한다)
• D의 높이는 2
• 리프 노드의 높이는 0
• 트리의 높이(height of the tree)
• 루트 노드의 높이
• 위 그림에서 트리의 높이는 4
• 노드의 깊이(depth)
• 루트 노드에서 해당 노드까지 경로의 간선 수
• D의 깊이는 2
• 루트 노드의 깊이는 0
• 트리의 깊이(depth of the tree)
• 트리에 있는 노드의 깊이 중 가장 긴 깊이
• 위 그림에서 트리의 깊이는 4
• 트리의 깊이 = 트리의 높이
• 노드의 차수(degree)
• 노드의 자녀 노드 수
• H의 차수는 2
• 트리의 차수(degree of the tree)
• 트리에 있는 노드들의 차수 중 가장 큰 차수
• 위 그림에서 트리의 차수는 2
• 두 노드 사이의 거리(distance)
• 두 노드의 최단 경로의 간선 수
• L과 O의 거리는 8
• 노드의 레벨(level)
• 노드와 루트 노드 사이의 경로에서 간선 수
• 루트 노드의 레벨은 0 (또는 1로 보는 경우도 있다)
• 넓이(width)
• 어떤 레벨에 있는 노드의 수
• Level 2의 width는 4
• 노드의 크기(size)
• 자신을 포함한 자손 노드의 수
• C의 크기는 C, G, F, J, O, P를 모두 센 6
• 트리의 크기(size of the tree)
• 트리의 모든 노드의 수
• 위 그림에서 트리의 크기는 16

 
 

• 서브 트리(Subtree)
• 각 노드의 자녀 노드들은 재귀적으로 서브 트리를 구성한다.
• Any node of the tree along with its descendant.

 

이미지 출처: https://www.geeksforgeeks.org/introduction-to-tree-data-structure-and-algorithm-tutorials/

 
이런식으로, 트리는 재귀적으로 내부적으로 수많은 서브트리를 가지면서 만들어진다.
 

struct Node
{
   int data;
   struct Node *first_child;
   struct Node *second_child;
   struct Node *third_child;
   .
   .
   .
   struct Node *nth_child;
};

 

💋 트리 구조의 특징

• 루트 노드는 딱 1개만 존재한다.
• 트리 내에 사이클은 존재하지 않는다.
• 자녀 노드는 하나의 부모 노드만 가진다.
• 데이터를 순차적으로 저장하지 않는 비선형 구조
• 트리에 서브 트리가 있는 재귀적 구조
• 계층적 구조

 
 

💋 참고자료

• https://www.geeksforgeeks.org/introduction-to-tree-data-structure-and-algorithm-tutorials/
• https://www.youtube.com/watch?v=ohrwGtqeW-I&list=PLcXyemr8ZeoR82N8uZuG9xVrFIfdnLd72&index=9

 

도움이 되었다면, 공감/댓글을 달아주면 깃짱에게 큰 힘이 됩니다!🌟
비밀댓글과 메일을 통해 오는 개인적인 질문은 받지 않고 있습니다. 꼭 공개댓글로 남겨주세요!