지금까지 배운 배열, 스택, 큐는 데이터가 한 줄로 나란히 서 있는 '선형(Linear)' 구조였습니다. 하지만 현실 세계의 데이터는 이렇게 단순하지 않습니다. 여러분의 컴퓨터 폴더 구조, 회사의 조직도, 웹사이트의 HTML 구조, 그리고 가족 관계까지. 이들은 모두 계층(Hierarchy)을 가지고 뻗어 나가는 형태입니다. 이러한 계층적 데이터를 컴퓨터로 표현하기 위해 고안된 자료구조가 바로 트리(Tree)입니다. 오늘은 트리의 난해한 용어들을 우리가 흔히 보는 '가계도(족보)'에 빗대어 아주 쉽게 정복해 보겠습니다.
1. 트리(Tree)란 무엇인가?
트리는 노드(Node)들이 간선(Edge)으로 연결된 비선형 자료구조입니다. 이름이 '나무'인 이유는, 데이터를 그려놓고 보면 나무를 거꾸로 뒤집어 놓은 모양(뿌리가 위, 가지가 아래)과 똑같기 때문입니다. 트리의 가장 큰 특징은 순환(Cycle)이 없다는 점입니다. 즉, 둥글게 연결되어 뱅글뱅글 도는 구간이 없으며, 위에서 아래로 흐르는 명확한 방향성이 존재합니다.
2. 가계도로 이해하는 트리의 핵심 용어
트리의 구성 요소는 가족 관계 용어와 완벽하게 일치합니다. 할아버지-아버지-나의 관계를 생각하며 읽어보세요.
2-1. 노드(Node)의 역할에 따른 명칭
- 루트 노드 (Root Node): 트리의 가장 꼭대기에 있는 시조(始祖)입니다. 모든 데이터의 시작점이며, 트리 하나당 루트는 오직 하나뿐입니다. (예: 시조 할아버지)
- 부모 노드 (Parent Node): 나에게 연결된 바로 위의 노드입니다. (예: 아버지)
- 자식 노드 (Child Node): 나에게 연결된 바로 아래의 노드들입니다. 부모는 여러 자식을 가질 수 있습니다. (예: 아들, 딸)
- 형제 노드 (Sibling Node): 같은 부모를 둔 노드들입니다. (예: 형, 누나, 동생)
- 리프 노드 (Leaf Node): 자식이 하나도 없는, 트리의 가장 끝자락에 있는 노드입니다. '단말 노드'라고도 합니다. (예: 아직 자식이 없는 막내)
2-2. 위치와 거리에 따른 명칭
- 깊이 (Depth): 루트 노드에서 '나'까지 내려오는 데 거쳐야 하는 단계 수입니다. 루트는 깊이가 0입니다. (예: 3세손, 4세손 할 때의 촌수)
- 레벨 (Level): 같은 깊이에 있는 노드들의 집합입니다. (예: 항렬)
- 높이 (Height): 트리가 얼마나 깊게 뻗어 있는지를 나타내는, 가장 깊은 리프 노드까지의 길이입니다.
3. 트리는 왜 중요할까? (활용 사례)
개발자가 트리를 몰라도 코딩은 할 수 있지만, 시스템을 이해할 수는 없습니다. 컴퓨터의 근간이 트리로 되어 있기 때문입니다.
- 파일 시스템: 윈도우 탐색기나 맥의 Finder에서 폴더 안에 폴더가 있고, 그 안에 파일이 있는 구조가 전형적인 트리입니다.
- HTML DOM: 웹페이지는 `` 태그 아래 ``, ``가 있고, 그 아래 `
`들이 달리는 거대한 트리 구조(DOM Tree)입니다. 자바스크립트로 요소를 찾을 때 우리는 트리를 탐색하고 있는 것입니다.
- 데이터베이스 인덱스: 수백만 건의 데이터에서 원하는 값을 0.01초 만에 찾아내는 마법(B-Tree)도 트리 구조 덕분입니다.
4. 트리의 종류 (맛보기)
트리는 자식을 몇 개 가질 수 있느냐, 어떻게 정렬하느냐에 따라 다양하게 나뉩니다. - 이진 트리 (Binary Tree): 자식을 최대 2명까지만 낳을 수 있는 트리. (가장 기본이 됨) - 이진 탐색 트리 (BST): 왼쪽 자식은 나보다 작고, 오른쪽 자식은 나보다 큰 트리. (검색용) - 힙 (Heap): 부모가 자식보다 무조건 크거나 작은 트리. (우선순위 큐 구현용)
1. 트리는 계층적(Hierarchy) 데이터를 표현하는 비선형 자료구조로, 순환이 없습니다.
2. 루트(시작), 부모, 자식, 리프(끝) 등 가족 관계 용어를 사용하여 노드 간의 관계를 정의합니다.
3. 파일 시스템, 웹페이지 구조(DOM), 검색 엔진 인덱스 등 컴퓨터 시스템 전반의 뼈대가 됩니다.