지금까지 배운 배열, 스택, 큐는 모두 데이터가 한 줄로 나열되는 선형(Linear) 자료구조였습니다. 하지만 현실 세계의 모든 정보가 한 줄로 서 있을까요? 여러분 컴퓨터의 폴더 구조를 생각해 보세요. '내 문서' 안에 '사진' 폴더가 있고, 그 안에 다시 '여행' 폴더와 '가족' 폴더가 나뉩니다. 회사 조직도는 어떤가요? 사장님 아래 본부장, 그 아래 팀장, 팀원으로 뻗어 나갑니다. 이처럼 데이터 간에 계층(Hierarchy)이 존재하고, 1:N의 관계를 가지는 구조를 표현하기 위해 트리(Tree)라는 자료구조가 탄생했습니다.
트리는 데이터베이스의 인덱싱부터 HTML의 DOM 구조, 인공지능의 의사결정 트리까지 컴퓨터 과학 전반에 걸쳐 핵심적으로 사용됩니다. 오늘은 이 나무 모양의 구조를 이해하기 위한 필수 용어들을 완벽하게 정리해 보겠습니다.
1. 트리(Tree)란 무엇인가?
트리는 이름 그대로 나무를 거꾸로 뒤집어 놓은 듯한 모양을 하고 있습니다. 가장 위에 뿌리(Root)가 있고, 밑으로 가지(Branch)가 뻗어 나가며 잎(Leaf)이 달리는 구조입니다. 트리는 노드(Node)와 그 노드들을 연결하는 간선(Edge)으로 구성됩니다. 가장 중요한 특징은 '순환(Cycle)이 없다'는 점입니다. 즉, 둥글게 연결되어 다시 제자리로 돌아오는 길이 존재하지 않는, 계층적인 방향성을 가진 그래프의 일종입니다.
2. 트리 해부하기: 필수 용어 정리
트리를 다루기 위해서는 가족 관계에 비유된 용어들을 명확히 알아야 합니다.
2-1. 노드의 종류
- 루트 노드 (Root Node): 트리의 가장 최상단에 있는 시작 노드입니다. 트리 하나당 루트는 오직 하나만 존재합니다. (나무의 뿌리)
- 부모 노드 (Parent Node): 특정 노드의 바로 상위에 연결된 노드입니다. 나를 낳아준 부모와 같습니다.
- 자식 노드 (Child Node): 특정 노드의 바로 하위에 연결된 노드입니다. 부모는 여러 자식을 가질 수 있습니다.
- 형제 노드 (Sibling Node): 같은 부모를 둔 노드들입니다.
- 리프 노드 (Leaf Node / Terminal Node): 자식 노드가 하나도 없는, 트리의 가장 끝자락에 있는 노드입니다. (나뭇잎)
2-2. 깊이와 높이
- 깊이 (Depth): 루트 노드에서 특정 노드까지 도달하기 위해 거쳐야 하는 간선의 개수입니다. 루트의 깊이는 보통 0으로 봅니다.
- 레벨 (Level): 같은 깊이에 있는 노드들의 집합입니다.
- 높이 (Height): 트리의 최고 깊이를 의미합니다. 트리가 얼마나 깊게 뻗어 있는지를 나타냅니다.
3. 왜 트리를 사용할까?
굳이 복잡한 트리를 사용하는 이유는 '효율적인 탐색'과 '계층 표현' 때문입니다.
3-1. 탐색의 효율성 (이진 탐색 트리)
데이터가 순서대로 나열된 배열에서 특정 값을 찾으려면 O(n)의 시간이 걸립니다. 하지만 트리를 특정한 규칙(왼쪽 자식은 작게, 오른쪽 자식은 크게)으로 정렬해 두면, 한 번 단계가 내려갈 때마다 탐색 범위가 절반으로 줄어듭니다. 이를 이진 탐색 트리(BST)라고 하며, 평균적으로 O(log n)이라는 엄청나게 빠른 속도로 데이터를 찾을 수 있습니다. 10억 개의 데이터가 있어도 약 30번의 비교만으로 원하는 값을 찾아낼 수 있다는 뜻입니다.
3-2. 계층적 데이터의 자연스러운 표현
컴퓨터의 파일 시스템(디렉터리 구조)을 배열로 구현한다고 상상해 보세요. 어느 파일이 어느 폴더에 속해 있는지 관리하기가 매우 어려울 것입니다. 트리는 이러한 포함 관계를 구조 자체적으로 완벽하게 표현합니다. 우리가 웹 개발 시 보는 HTML 코드도 `` 안에 ``, 그 안에 `
4. 가장 많이 쓰이는 트리: 이진 트리 (Binary Tree)
트리 중에서도 각 노드가 최대 2개의 자식 노드(왼쪽, 오른쪽)만을 가질 수 있는 트리를 '이진 트리'라고 합니다. 구현이 간단하고 컴퓨터로 처리하기 가장 적합하여, 대부분의 트리 알고리즘은 이 이진 트리를 기반으로 발전했습니다.
1. 트리는 노드와 간선으로 이루어진 계층적 비선형 자료구조로, 순환(Cycle)이 없습니다.
2. 루트(시작), 부모, 자식, 리프(끝) 등의 용어를 통해 노드 간의 관계를 정의합니다.
3. 파일 시스템 같은 계층 구조 표현이나, 이진 탐색 트리(BST)를 이용한 고속 데이터 검색에 핵심적으로 사용됩니다.