트리(Tree) 자료구조: 윈도우 폴더 구조가 사실은 알고리즘이라고?

그래프(Graph)가 점과 선을 이용해 무법지대처럼 모든 것을 자유롭게 얽히게 내버려 둔다면, '트리(Tree)'는 이 그래프에 '계급'과 '방향성'이라는 강력한 족쇄를 채운 특수한 형태의 그래프입니다. 회사 조직도의 사장-부장-사원 관계, 가계도의 조상-후손 관계, 그리고 우리가 매일 쓰는 윈도우(Windows) 운영체제의 C: 드라이브 아래에 폴더와 파일들이 끝없이 뻗어나가는 계층적 디렉토리 구조가 바로 완벽한 트리 자료구조의 표본입니다. 나무의 뿌리에서 시작해 나뭇잎으로 끝없이 뻗어나가는 이 위대한 계층형 데이터 구조를 낱낱이 파헤쳐 봅니다.

1. 트리의 절대적 족보 (계층과 용어)

트리는 가족이나 군대처럼 상하 관계가 명확하게 정해져 있습니다.

• 루트(Root) 노드: 트리의 맨 꼭대기에 군림하는 단 하나의 최고 조상입니다. (예: C:\ 드라이브)
• 부모-자식(Parent-Child) 관계: 나를 바로 위에서 낳아준 노드가 부모, 내가 바로 밑으로 거느리는 노드가 자식입니다. 트리의 핵심은 "한 노드의 부모는 무조건 단 1명뿐이어야 한다"는 것입니다. (부모가 2명 이상이면 그건 트리가 아니라 일반 그래프입니다.)
• 리프(Leaf) 노드: 가지의 끝자락에 매달려 자식이 하나도 없는 노드입니다. 윈도우 폴더 속 가장 깊숙한 곳에 있는 '단일 파일(txt, jpg)'들이 바로 리프 노드입니다.
• 깊이(Depth)와 높이(Height): 루트에서 특정 노드까지 내려가는 데 거친 간선의 개수를 깊이라 하고, 트리 전체의 가장 깊은 깊이를 트리의 높이라고 부릅니다.

2. 트리의 기하학적, 수학적 진실

트리가 일반 그래프와 차별화되는 가장 큰 특징은 "순환(Cycle)이 절대 존재하지 않는다"는 점입니다.

2-1. 사이클이 없는 연결 그래프 (Acyclic Connected Graph)

A에서 시작해 간선을 타고 돌아다니다가 다시 A로 되돌아올 수 있는 고리(Cycle) 구조가 트리에 형성되는 순간, 그것은 트리의 자격을 박탈당합니다. 족보로 치면 내가 낳은 자식의 자식이 다시 나의 부모가 되는 패륜적인 상황이 벌어지는 것입니다.

2-2. 정점과 간선의 절대 공식

이러한 엄격한 트리 규칙 때문에 수학적으로 매우 아름다운 공식 하나가 성립합니다. "트리를 구성하는 노드(정점)가 $N$개라면, 트리의 간선은 무조건 $N-1$개이다." 노드가 100개인 트리는 반드시 99개의 간선으로 이어져 있습니다. 간선이 하나라도 추가되면 순환(Cycle)이 생겨버리고, 간선이 하나라도 빠지면 트리가 두 동강(단절) 나버리는 완벽한 균형 상태, 이것이 바로 트리 자료구조의 본질입니다.

[핵심 요약]
1. 트리(Tree)는 노드들이 부모-자식 관계로 이루어져 계층(Hierarchy)을 형성하는 비선형 자료구조로, 컴퓨터 파일 시스템이나 조직도에 쓰입니다.
2. 트리는 수학적으로 순환(Cycle)이 없는 연결 그래프로 정의되며, 임의의 두 노드를 잇는 경로는 오직 단 1개만 존재합니다.
3. 트리의 노드 개수가 $N$개라면 간선의 개수는 반드시 $N-1$개라는 절대적인 수학적 특성을 지닙니다.