배열은 일렬로 늘어놓지만, 트리(Tree)는 위에서 아래로 가지를 뻗으며 계층을 만들어요. 이 구조 덕분에 정렬 유지와 빠른 검색이 동시에 가능해집니다. 특히 이진 탐색 트리(BST)를 감으로 잡아봐요.
꼭 알아야 할 기본 용어를 정리해볼게요.
| 용어 | 뜻 |
|---|---|
| 루트(root) | 맨 위에 있는 시작 노드. 트리에 딱 하나뿐이에요. |
| 부모/자식(parent/child) | 바로 위 노드가 부모, 바로 아래로 이어진 노드가 자식이에요. |
| 리프(leaf) | 자식이 없는 끝 노드. 잎사귀에 해당해요. |
| 간선(edge) | 부모와 자식을 잇는 선이에요. |
| 깊이/높이 | 루트에서 얼마나 아래로 내려갔는지를 나타내는 층수예요. |
[ 10 ] ← 루트(root)
/ \
[ 5 ] [ 15 ] ← 10의 자식(child)
/ \ \
[ 3 ] [ 8 ] [ 20 ] ← 리프(leaf): 자식 없음10은 루트, 5·15는 그 자식이고, 3·8·20은 자식이 없는 리프예요.
이진 트리(binary tree)는 각 노드가 자식을 최대 2개(왼쪽·오른쪽)만 갖는 트리예요. 그래서 노드마다 left(왼쪽 자식)와 right(오른쪽 자식)를 가리키죠. 자식이 없으면 리프고요.
class Node {
constructor(value) {
this.value = value; // 이 노드가 담은 값
this.left = null; // 왼쪽 자식 (없으면 null)
this.right = null; // 오른쪽 자식 (없으면 null)
}
}순회(traversal)는 트리의 모든 노드를 빠짐없이 방문하는 방법이에요. 배열은 앞에서 뒤로 한 줄이면 끝이지만, 트리는 가지가 갈라지므로 방문 순서를 정해야 해요. 대표적으로 세 가지가 있어요.
function inorder(node) {
if (node === null) return; // 없으면 되돌아감
inorder(node.left); // 1) 왼쪽 먼저
console.log(node.value); // 2) 그다음 나(루트)
inorder(node.right); // 3) 마지막 오른쪽
}이진 탐색 트리(BST · Binary Search Tree)는 규칙 하나를 지키는 이진 트리예요. 어떤 노드를 기준으로 왼쪽 서브트리는 모두 그 노드보다 작고, 오른쪽 서브트리는 모두 큼이에요. 한 줄로 쓰면 왼쪽 < 노드 < 오른쪽이죠.
[ 10 ]
/ \
(작다) (크다)
[ 5 ] [ 15 ]
/ \ / \
[ 3 ][ 8 ][ 12 ][ 20 ]
// 10의 왼쪽(5,3,8)은 전부 10보다 작음
// 10의 오른쪽(15,12,20)은 전부 10보다 큼15 기준으로도 왼쪽 12는 작고 오른쪽 20은 커요.
3, 5, 8, 10, 12, 15, 20이에요. 정렬된 결과가 공짜로 나오는 셈이죠.| 쓰임 | 설명 |
|---|---|
| 정렬 유지 + 빠른 검색 | BST는 값을 넣는 동시에 정렬 상태를 유지하면서 평균 O(log n)으로 찾아요. |
| 파일 시스템 | 폴더 안에 폴더, 그 안에 파일 — 전형적인 트리 구조예요. |
| 웹의 DOM | HTML 문서도 <html>을 루트로 하는 트리예요(요소 안에 요소). |
| 우선순위·인덱스 | 힙·데이터베이스 인덱스 등도 트리 계열 구조를 활용해요. |