[자료구조] 트리(Tree)란?

트리란

• 트리는 그래프의 일종으로, 노드로 이루어진 계층적 구조이다.
• 한 노드를 시작으로 다른 노드를 순회하며 자기 자신에게 돌아오는 순환 없는 연결 그래프이다.

트리의 용어

• 루트 노드(Root Node): 트리 구조의 최상위 노드로, 모든 다른 노드들은 이 루트 노드에서 시작된다.
• 부모 노드(Parent Node): 다른 노드에게 연결된 상위 노드를 가리킨다.
• 자식 노드(Child Node): 부모 노드에 의해 직접적으로 연결된 하위 노드를 말한다.
• 잎 노드(Leaf Node): 자식 노드가 없는 노드로, 트리 구조의 끝에 위치한다.
• 서브 트리(Subtree): 트리 안에서 다른 트리를 포함하는 부분 트리를 의미한다.
• 형제(Sibling): 같은 부모를 가진 노드를 의미한다.
• 간선(edge): 노드를 연결하는 선으로 link나 branch라고도 부른다.
• 노드의 크기(size): 자신을 포함한 모든 노드의 개수를 말한다.
• 노드의 깊이(depth): 해당 노드가 루트에서 몇 개의 간선을 거쳐야 하는지 의미한다.
• 노드의 레벨(level): 트리의 특정 깊이를 가지는 노드의 집합을 의미한다.
• 노드의 차수(degree): 하위 트리 개수 / 간선 수, 즉 각 노드가 갖고있는 가지의 수를 의미한다.
• 트리의 차수(degree of tree): 트리의 최대 차수를 의미한다.
• 트리의 높이(height): 루트에서 가장 깊숙하게 있는 노드의 깊이를 의미한다.

트리의 특징

• 트리는 부모-자식으로 이루어지는 계층적 구조이다.
• 각 노드는 하나의 부모노드를 갖거나 자신이 루트 노드임을 의미한다.
• 트리는 특정 노드로 가는 길이 정해져있으며, 이러한 특징으로 인해 사이클이 존재하지 않는다. 
• 트리는 데이터 저장보다 효과적인 탐색을 위해 사용된다.
• 노드가 N개인 트리는 N-1개의 간선을 가진다.

트리의 장단점

1. 장점
   • 계층적인 구조로, 데이터를 관리하는데 효율적이다.
   • 특정 데이터를 검색하는데 뛰어나다.
2. 단점
   • 구현이 상대적으로 어렵다.
   • 트리는 데이터가 정렬되어있지 않다면 검색 효율이 떨어진다.

출처 : 트리 구조 - 위키백과, [자료구조] 트리란