Tree

트리(Tree)는 노드(Node)들이 계층적(Hierarchical)으로 부모-자식 관계로 연결된 형태를 갖는 비선형 자료구조입니다.

트리는 방향 그래프로도, 무방향 그래프로도 볼 수 있습니다.
- 그래프 이론에서는 트리를 하나의 연결 그래프이자 사이클이 없고 모든 노드가 연결된 무방향 비순환 그래프로 정의합니다.
- 반면, 컴퓨터 과학(자료구조)에서는 트리를 부모에서 자식으로 향하는 방향성을 가진 방향 비순환 그래프(DAG)로 정의합니다.

Tree 구성요소

이름	설명
Node (노드)	트리를 구성하는 각각의 요소입니다.
Edge (간선)	노드 간의 연결선입니다.
Root Node (루트 노드)	트리에서 최상위에 있는 노드이자 부모가 없는 노드입니다.
Sibling Node (형제 노드)	동일한 부모를 가진 노드들입니다.
Leaf Node (Terminal Node, 단말 노드)	자식이 없는 노드입니다.
Internal Node (내부 노드, 비단말 노드)	Leaf Node를 제외한 모든 노드를 의미하며, 루트 노드도 포함됩니다.
Degree (차수)	특정 노드의 자식 수입니다.
Depth (깊이)	루트에서 특정 노드까지 간선 수 (`0`부터 시작)입니다.
Level (레벨)	트리의 각 층을 나타내는 번호 (`Depth + 1`의 값)입니다.
Height (트리의 높이)	루트에서 가장 깊은 노드까지의 깊이입니다.

자료구조 관점에서, 트리의 루트 노드를 제외한 모든 노드는 반드시 하나의 부모 노드를 갖습니다.
그래프 이론 관점에서, 트리의 루트 노드에서 특정 노드로 가는 경로나 임의의 두 노드 사이의 경로는 항상 유일합니다. 다시 말해, 트리는 무방향 비순환 그래프의 일종이므로 두 노드 사이에는 반드시 하나의 경로만 존재합니다.
그래프 이론과 자료구조 관점 모두에서, 트리는 모든 정점이 간선으로 연결되어 있으며, 정점의 수가 N개일 때 간선의 수는 항상 N - 1개입니다.

트리를 균형 상태를 기준으로 분류하면 균형 트리(Balanced Tree)와 불균형 트리(UnBalanced Tree)로 나눌 수 있습니다.

균형 트리(Balanced Tree)

불균형 트리(Unbalanced Tree)

서브트리의 높이

어떤 노드를 루트로 하는 서브트리에서 가장 깊은 리프 노드까지의 거리입니다.

각 노드가 가질 수 있는 자식의 수를 기준으로 m-ary 트리, 완전 m-ary 트리, 전 m-ary 트리, 포화 m-ary 트리로 나눌 수 있습니다.

m-ary 트리 (m-진 트리)

각 노드가 최대 m개의 자식을 가질 수 있는 트리입니다.
- 이진 트리 (Binary Tree)는 각 노드가 최대 2개의 자식(왼쪽, 오른쪽)만 가질 수 있는 트리입니다.
- 삼진 트리 (3-ary Tree)는 각 노드가 최대 3개의 자식만 가질 수 있는 트리입니다.

완전 m-ary 트리 (Complete m-ary Tree)

노드들이 왼쪽부터 순서대로 채워지는 m-ary 트리로, 마지막 레벨을 제외한 모든 레벨이 노드로 완전히 채워져 있고, 마지막 레벨은 왼쪽부터 순차적으로 노드가 채워져 있습니다.
- 전 이진 트리(Complete Binary Tree)는 이진 트리 중에서도 마지막 레벨의 노드들이 왼쪽부터 순서대로 채워져 있으며, 그 위에 모든 레벨은 노드로 완전히 채워져 있습니다.

전 m-ary 트리 (Fully m-ary 트리)

모든 노드가 0개 또는 m개의 자식을 갖는 트리입니다.
- 전 이진 트리(Fully Binary Tree)는 모든 노드가 0개 또는 2개의 자식을 갖는 트리입니다.

포화 m-ary 트리 (Perfect m-ary 트리)

모든 노드가 정확히 m개의 자식을 가지고, 모든 리프 노드가 동일한 깊이(Depth)에 존재하는 m-ary 트리입니다. 쉽게 말해, 전 m-ary 트리이면서 완전 m-ary 트리를 만족하는 트리입니다.
- 포화 이진 트리(Perfect Binary Tree)는 모든 노드가 정확히 2개의 자식을 가지며, 모든 리프 노드가 같은 깊이에 있는 이진 트리입니다.

노드의 상대적 위치나 삽입 규칙, 순서 제약 조건에 따라 이진 탐색 트리, 힙, 트라이 등으로 나눌 수 있습니다.

왼쪽 < 부모 < 오른쪽 또는 왼쪽 > 부모 > 오른쪽 자식의 관계를 만족하는 이진트리입니다.
정렬된 데이터를 트리 형태로 구성하여 탐색, 삽입, 삭제 연산을 효율적으로 수행할 수 있습니다.
단, 트리가 불균형해질 경우 최악의 경우 탐색, 삽입, 삭제에 O(N)이 걸릴 수 있습니다.
- 이를 해결하기 위해 AVL, RB Tree(Red-Black Tree) 와 같은 균형 이진 트리가 도입되었습니다.
- 최악의 경우에도 탐색, 삽입, 삭제에 O(log N)을 보장합니다.