트리 데이터 구조란 무엇인가?
트리(Tree)는 조직도, 파일 시스템처럼 계층적인 구조를 표현하는 대표적인 비선형 데이터 구조입니다. 배열이나 연결 리스트가 선형으로 데이터를 나열하는 것과 달리, 트리는 하나의 시작점에서 여러 갈래로 뻗어 나가는 부모-자식 관계를 통해 데이터를 저장합니다.
실제로 우리가 다루는 많은 것들이 트리 구조로 되어 있습니다. 예를 들어 웹 개발자라면 매일 접하게 되는 HTML DOM이 바로 트리의 전형적인 예이며, JSON 데이터, 폴더와 파일로 이루어진 디렉터리 구조, 회사의 조직도 등도 모두 트리로 모델링할 수 있습니다.
트리의 재귀적(Recusive) 정의
좀 더 형식적으로 정의하면, 트리는 루트(root) 노드에서 시작되는 노드(node)들의 집합으로 재귀적으로, 즉 지역적으로 정의할 수 있습니다. 여기서 각 노드는 다음 두 가지 요소로 구성된 자료구조입니다.
- 값(value): 해당 노드가 담고 있는 실제 데이터
- 참조 목록(references): 자식(children)이라 불리는 다른 노드들을 가리키는 참조들의 리스트
이 정의가 '재귀적'인 이유는, 각 자식 노드 역시 자신만의 값과 자식 노드 목록을 가진 또 하나의 트리(부분 트리, subtree)이기 때문입니다. 이러한 특성 덕분에 트리 순회(traversal) 알고리즘은 반복문보다 재귀 호출로 자연스럽게 구현되는 경우가 많습니다.
트리가 만족해야 하는 핵심 제약 조건
모든 노드 집합이 트리가 되는 것은 아닙니다. 유효한 트리가 되려면 다음 제약 조건을 만족해야 합니다.
- 참조의 중복 금지: 어떤 노드도 동일한 자식 노드를 두 번 참조해서는 안 됩니다.
- 단일 부모 원칙: 결과적으로 각 자식 노드는 정확히 하나의 부모만 가져야 합니다. 두 부모를 가지는 노드가 존재하면 그것은 트리가 아니라 그래프(graph)에 가까운 구조입니다.
이 제약 조건 덕분에 루트에서 임의의 노드까지 도달하는 경로는 항상 유일하며, 사이클(cycle)이 발생하지 않는다는 보장이 생깁니다. 이것이 트리를 탐색, 정렬, 검색 문제에 활용할 수 있는 핵심 근거입니다.
정리
트리는 값과 자식 노드에 대한 참조를 가진 노드들이 루트에서부터 재귀적으로 연결된 계층형 자료구조입니다. '각 노드는 단 하나의 부모를 가진다'는 단순한 규칙이 트리의 본질을 이루며, 자바스크립트에서 DOM 조작, UI 컴포넌트 렌더링, 파일 탐색기 구현 등 다양한 영역에서 이 구조를 이해하고 있으면 큰 도움이 됩니다.