Tree, Graph, DOM Tree
배열은 데이터를 한 줄로 세우고, Map 은 키와 값을 짝지어 둡니다. 둘 다 "무엇이 어디에 있나"는 잘 표현하지만, "무엇이 무엇과 이어져 있나"는 표현하지 못합니다.
폴더 안의 폴더, 댓글의 답글, 지하철 노선처럼 관계가 중요한 데이터가 있습니다. 이런 데이터를 담는 자료구조가 그래프와 트리입니다.
이 글은 그래프에서 시작해 트리로 좁혀 가고, 트리를 훑는 두 가지 방법(DFS, BFS)을 본 다음, 프론트엔드가 매일 다루는 트리인 DOM 트리로 넘어갑니다.
1. 그래프: 점과 선으로 관계를 표현하기
그래프는 노드(node) 와 노드를 잇는 간선(edge) 으로 이루어진 자료구조입니다. 노드는 대상이고, 간선은 둘 사이의 관계입니다.
| 예시 | 노드 | 간선 |
|---|---|---|
| 지하철 노선도 | 역 | 두 역을 잇는 선 |
| SNS 팔로우 | 사용자 | 팔로우 |
| 모듈 import 관계 | 파일 | import 문 |
간선에 방향이 있으면 방향 그래프, 없으면 무방향 그래프라고 합니다. 지하철은 양쪽으로 오갈 수 있으니 무방향이고, 팔로우는 한쪽만 할 수도 있으니 방향 그래프입니다.
1.1 코드로 표현하기
그래프는 보통 "노드마다 이웃 목록"을 두는 방식(인접 리스트)으로 표현합니다.
// 무방향 그래프: A-B, B-C, C-A, C-D, C-E
const graph = new Map([
["A", ["B", "C"]],
["B", ["A", "C"]],
["C", ["A", "B", "D", "E"]],
["D", ["C"]],
["E", ["C"]],
]);
graph.get("C"); // ['A', 'B', 'D', 'E'] → C 와 이어진 노드
이웃을 찾을 때 graph.get(node) 한 번이면 되니 탐색 코드가 단순해집니다.
1.2 그래프에는 사이클이 생길 수 있습니다
위 그래프에서 A → B → C → A 로 가면 출발점으로 돌아옵니다. 이렇게 한 바퀴 도는 길을 사이클(cycle) 이라고 합니다.
사이클이 있으면 탐색할 때 같은 노드를 계속 돌 수 있습니다. 그래서 그래프를 탐색할 때는 이미 방문한 노드를 기록해 둬야 합니다. 이 내용은 3장에서 코드로 봅니다.
2. 트리: 사이클 없이 위에서 아래로 갈라지는 그래프
트리는 그래프의 한 종류입니다. 사이클이 없고, 모든 노드가 하나로 연결된 그래프를 트리라고 부릅니다.
트리에는 맨 위에 시작점이 하나 있고, 거기서 아래로만 갈라집니다. 그래서 위치를 부르는 이름이 생깁니다.
| 용어 | 뜻 | 그림에서 |
|---|---|---|
| 루트 (root) | 맨 위 노드. 부모가 없음 | A |
| 부모 / 자식 | 바로 위 노드 / 바로 아래 노드 | B 는 D 의 부모 |
| 형제 | 부모가 같은 노드 | D 와 E |
| 리프 (leaf) | 자식이 없는 노드 | D, E, F |
| 깊이 (depth) | 루트에서 몇 단계 내려왔는지 | D 의 깊이는 2 |
사이클이 없다는 건 루트에서 어떤 노드까지 가는 길이 딱 하나라는 뜻입니다. 그래서 모든 노드는 부모가 정확히 하나입니다(루트만 없음). 폴더 경로 /src/components/Button 이 하나로 정해지는 것도 같은 이유입니다.
코드로는 노드가 자기 자식 배열을 들고 있는 모양이 가장 흔합니다.
const tree = {
value: "A",
children: [
{ value: "B", children: [{ value: "D", children: [] }, { value: "E", children: [] }] },
{ value: "C", children: [{ value: "F", children: [] }] },
],
};
서버에서 받는 카테고리, 메뉴, 댓글과 답글 데이터가 대부분 이런 모양입니다.
그래프와 트리 비교
| 그래프 | 트리 | |
|---|---|---|
| 연결 방식 | 자유롭게 | 부모 하나에 자식 여럿 |
| 사이클 | 있을 수 있음 | 없음 |
| 시작점 | 정해져 있지 않음 | 루트 하나 |
| 간선 수 | 제한 없음 | 노드가 n 개면 n − 1 개 |
| 예시 | 지하철, 팔로우, 모듈 의존성 | 폴더, 메뉴, 댓글, DOM |
3. 트리를 훑는 두 가지 방법: DFS 와 BFS
트리의 모든 노드를 한 번씩 방문하는 걸 순회라고 합니다. 방문 순서에 따라 두 가지로 나뉩니다.
3.1 DFS: 깊이 우선 탐색
DFS(Depth-First Search)는 한 가지를 끝까지 내려간 다음, 돌아와서 옆 가지로 갑니다. "자기 자신을 처리하고, 자식마다 같은 일을 반복"하면 되니 재귀로 짧게 쓸 수 있습니다.
function dfs(node) {
console.log(node.value);
for (const child of node.children) dfs(child);
}
dfs(tree); // A B D E C F
3.2 BFS: 너비 우선 탐색
BFS(Breadth-First Search)는 루트에서 가까운 층부터 차례로 훑습니다. 먼저 발견한 노드를 먼저 처리해야 하니 큐(먼저 넣은 것이 먼저 나오는 줄)를 씁니다.
function bfs(root) {
const queue = [root];
while (queue.length > 0) {
const node = queue.shift(); // 앞에서 꺼내고
console.log(node.value);
queue.push(...node.children); // 자식은 뒤에 줄 세움
}
}
bfs(tree); // A B C D E F
3.3 그래프에서는 방문 기록이 필요합니다
트리는 사이클이 없어서 위 코드가 끝납니다. 그래프에 그대로 쓰면 A → B → A → B … 처럼 끝나지 않습니다. 방문한 노드를 Set 에 기록하고 건너뛰면 됩니다.
function bfsGraph(graph, start) {
const visited = new Set([start]);
const queue = [start];
while (queue.length > 0) {
const node = queue.shift();
console.log(node);
for (const next of graph.get(node)) {
if (visited.has(next)) continue; // 이미 본 노드는 건너뜀
visited.add(next);
queue.push(next);
}
}
}
bfsGraph(graph, "A"); // A B C D E
3.4 언제 무엇을 쓸까
| 상황 | 고를 것 | 이유 |
|---|---|---|
| 모든 노드를 한 번씩 처리 (렌더링, 검색) | DFS | 재귀로 짧게 쓸 수 있음 |
| 가장 가까운 것, 최소 단계 찾기 | BFS | 가까운 층부터 보니 처음 찾은 것이 최단 |
두 방법 모두 노드를 한 번씩 방문하니 시간복잡도는 O(n) 입니다.
4. DOM 트리: 브라우저가 HTML 을 다루는 방식
4.1 HTML 은 트리가 됩니다
브라우저는 HTML 문자열을 받으면 위에서부터 읽어(파싱) 트리를 만듭니다. 이것이 DOM(Document Object Model) 트리입니다.
태그가 서로를 감싸는 관계가 그대로 부모와 자식이 됩니다. <ul> 이 <li> 를 감싸니 ul 이 부모, li 가 자식입니다. 루트는 document 입니다.
노드 종류는 여러 가지지만 자주 만나는 건 둘입니다.
- 요소 노드:
<li>같은 태그 - 텍스트 노드: 태그 안의 글자.
"사과"는li의 자식입니다.
JavaScript 에서 document.querySelector 로 꺼내는 것, React 가 결국 만들어 내는 것이 모두 이 트리의 노드입니다. 개발자 도구의 Elements 탭이 보여 주는 것도 원본 HTML 이 아니라 이 DOM 트리입니다.
4.2 트리 용어가 그대로 API 가 됩니다
2장의 부모, 자식, 형제가 DOM API 이름에 그대로 들어 있습니다.
const ul = document.querySelector("ul");
ul.parentElement; // <body> 부모
ul.children; // [<li>, <li>] 자식 (요소만)
ul.firstElementChild; // 첫 번째 <li>
ul.firstElementChild.nextElementSibling; // 두 번째 <li> 형제
children 은 요소 노드만 돌려줍니다. 텍스트 노드까지 포함하려면 childNodes 를 씁니다. 태그 사이 줄바꿈도 텍스트 노드라서 childNodes 에는 예상보다 많은 노드가 들어 있습니다.
3장의 DFS 를 DOM 에 그대로 쓸 수도 있습니다. 노드 구조만 children 으로 바뀝니다.
function printTree(el, depth = 0) {
console.log(" ".repeat(depth) + el.tagName);
for (const child of el.children) printTree(child, depth + 1);
}
printTree(document.documentElement);
// HTML
// HEAD
// TITLE
// BODY
// UL
// LI
// LI
querySelector 가 "첫 번째로 맞는 요소"를 고를 때의 순서도 이 DFS 순서(문서 순서)입니다.
4.3 이벤트는 트리를 따라 올라갑니다
li 를 클릭하면 클릭 이벤트는 li 에서 끝나지 않고 부모를 따라 ul → body → html → document 까지 올라갑니다. 이를 이벤트 버블링이라고 합니다.
이 성질 덕분에 자식마다 리스너를 달지 않고, 부모 하나에만 달아서 처리할 수 있습니다(이벤트 위임).
const list = document.querySelector("ul");
list.addEventListener("click", (event) => {
const item = event.target.closest("li"); // 클릭한 곳에서 부모 방향으로 li 찾기
if (!item) return;
console.log(item.textContent);
});
closest 는 자기 자신부터 루트까지 부모 방향으로만 거슬러 올라가며 찾습니다. 트리에서는 부모가 하나뿐이라 이 길이 하나로 정해집니다. 나중에 추가되는 li 도 따로 리스너를 달 필요가 없습니다.
4.4 React 는 DOM 을 어떻게 바꿀까
DOM 을 바꾸면 브라우저는 요소의 위치와 크기를 다시 계산합니다. 노드 하나가 커지면 그 아래 자식과 옆 형제의 위치도 달라지기 때문입니다. 그래서 DOM 은 적게 바꿀수록 빠릅니다.
React 는 DOM 을 바로 바꾸지 않습니다. 순서는 이렇습니다.
- 상태가 바뀌면 화면을 JS 객체 트리로 새로 만듭니다. 이것이 가상 DOM 입니다.
- 바로 전 가상 트리와 새 가상 트리를 비교합니다. 루트부터 3장의 DFS 순서로 내려가며, 같은 자리의 노드끼리 봅니다.
- 달라진 노드만 실제 DOM 에 반영합니다.
비교하는 건 가상 트리 두 개입니다. 실제 DOM 은 마지막에 결과만 받습니다.
같은 자리의 노드를 비교할 때 React 는 두 가지 규칙을 씁니다.
① 태그가 같으면 고치고, 다르면 새로 만듭니다.
<div className="a"> 가 <div className="b"> 로 바뀌면 className 만 고치고 자식으로 내려가 비교를 계속합니다.
태그 자체가 바뀌면 그 아래는 비교하지 않습니다.
// 이전 // 이후
<div> <span>
<Counter /> <Counter />
<input /> <input />
</div> </span>
안쪽은 그대로인데도 React 는 div 를 자식까지 지우고 span 을 처음부터 만듭니다. 그래서 Counter 의 숫자와 input 에 쓰던 글자가 사라집니다. isMobile ? <MobileLayout> : <DesktopLayout> 처럼 감싸는 컴포넌트를 바꿀 때 안쪽 상태가 초기화되는 이유입니다.
② 목록에서는 key 로 같은 항목을 알아봅니다.
[사과, 배] 목록 맨 앞에 딸기 를 추가해 보겠습니다.
// 이전 // 이후
<li>사과</li> <li>딸기</li>
<li>배</li> <li>사과</li>
<li>배</li>
key 가 없으면 React 는 위에서부터 줄 번호대로 비교합니다. 첫째 줄은 사과 가 딸기 로, 둘째 줄은 배 가 사과 로 바뀌었다고 보고, 셋째 줄 배 는 새로 생겼다고 봅니다. 딸기 하나만 추가했는데 세 줄을 모두 손보는 셈입니다.
key 를 붙이면 줄 번호 대신 key 로 같은 항목을 찾습니다.
<li key="strawberry">딸기</li>
<li key="apple">사과</li>
<li key="pear">배</li>
apple 과 pear 는 전에도 있었으니 그대로 두고, 처음 보는 strawberry 만 만들어 맨 앞에 넣습니다. 리스트에 key 를 넣으라고 하는 이유가 이것입니다.
두 규칙 덕분에 React 는 노드마다 한 번씩만 보고 비교를 끝냅니다(O(n)).
5. 실무에서 트리 데이터 그리기
서버에서 받은 카테고리나 댓글처럼 깊이가 정해지지 않은 트리는 컴포넌트가 자기 자신을 부르는 방식으로 그립니다. 3장의 재귀 DFS 와 같은 구조입니다.
function CommentItem({ comment }) {
return (
<li>
<p>{comment.text}</p>
{comment.replies.length > 0 && (
<ul>
{comment.replies.map((reply) => (
<CommentItem key={reply.id} comment={reply} />
))}
</ul>
)}
</li>
);
}
답글의 답글이 몇 단계든 같은 컴포넌트가 반복되며 내려갑니다. 리프(답글 없음)에서 멈추는 조건이 replies.length > 0 입니다.
서버가 트리 대신 parentId 가 담긴 평평한 배열을 주는 경우도 많습니다. 이때는 Map 으로 한 번에 트리를 만들 수 있습니다.
const comments = [
{ id: 1, parentId: null, text: "좋은 글이네요" },
{ id: 2, parentId: 1, text: "감사합니다" },
{ id: 3, parentId: 2, text: "저도요" },
{ id: 4, parentId: null, text: "질문 있어요" },
];
function buildTree(list) {
const byId = new Map(list.map((c) => [c.id, { ...c, replies: [] }]));
const roots = [];
for (const node of byId.values()) {
if (node.parentId === null) roots.push(node);
else byId.get(node.parentId).replies.push(node); // 부모를 O(1) 로 찾아 자식으로 붙임
}
return roots;
}
부모를 배열에서 find 로 찾으면 O(n²) 이지만, Map 으로 찾으면 O(n) 에 끝납니다.
6. 정리 및 Q&A
6.1 한눈에 보기
| 그래프 | 트리 | DOM 트리 | |
|---|---|---|---|
| 정체 | 노드와 간선의 모음 | 사이클 없는 연결 그래프 | 브라우저가 HTML 로 만든 트리 |
| 특징 | 사이클 가능, 시작점 없음 | 루트 하나, 부모 하나 | 루트는 document |
| 탐색 | DFS / BFS + 방문 기록 | DFS / BFS | children, closest, querySelector |
| 프론트 예시 | 모듈 의존성, 라우팅 경로 | 메뉴, 댓글, 폴더 | 화면 그 자체, 이벤트 버블링 |
6.2 복습 질문
① 트리와 그래프의 차이는 무엇인가요?
트리는 그래프의 한 종류로, 사이클이 없고 모든 노드가 연결되어 있습니다. 그래서 루트가 하나이고, 루트를 뺀 모든 노드는 부모가 정확히 하나입니다. 그래프는 이런 제약 없이 자유롭게 연결됩니다.
② DFS 와 BFS 는 어떻게 다르고, 언제 무엇을 쓰나요?
DFS 는 한 가지를 끝까지 내려간 뒤 돌아오고(재귀, 스택), BFS 는 가까운 층부터 훑습니다(큐). 모든 노드를 처리하는 일에는 짧게 쓸 수 있는 DFS, 최소 단계로 닿는 것을 찾을 때는 BFS 를 씁니다.
③ 그래프를 탐색할 때 visited 가 왜 필요한가요?
그래프에는 사이클이 있을 수 있어서, 기록하지 않으면 같은 노드를 계속 돌며 탐색이 끝나지 않습니다. 트리는 사이클이 없어서 없어도 됩니다.
④ DOM 트리는 무엇이고, Elements 탭과 HTML 소스가 다를 수 있는 이유는?
DOM 트리는 브라우저가 HTML 을 파싱해 만든 노드 트리입니다. Elements 탭은 원본 HTML 이 아니라 현재 DOM 을 보여 주므로, 브라우저가 고친 부분이나 JavaScript 가 바꾼 부분이 반영되어 있습니다.
⑤ 이벤트 위임이 가능한 이유는?
이벤트가 발생한 노드에서 부모 방향으로 루트까지 전파되기 때문입니다(버블링). 부모 하나에 리스너를 달고 event.target.closest() 로 실제 대상을 찾으면, 자식마다 리스너를 달지 않아도 되고 나중에 추가된 자식도 처리됩니다.
⑥ React 리스트에 key 가 필요한 이유는?
React 는 이전 트리와 새 트리를 비교해 바뀐 부분만 DOM 에 반영합니다. 형제 목록에서는 key 로 같은 노드를 찾기 때문에, key 가 없거나 인덱스면 순서가 바뀔 때 다른 항목을 같은 것으로 보고 잘못 고칠 수 있습니다.