트리와 힙, 그리고 그래프
자료구조 복습하기 3탄
자료구조 포스팅 하며 복습하기 📦
트리란?
한 노드가 여러 노드를 자식으로 거느리는 계층 구조입니다.
1탄에서 본 구조들은 한 줄이라 다음이 하나뿐이었습니다. 트리는 아래로 갈라집니다. 갈라지되 위로 되돌아가는 길은 없어서, 어느 노드에서 출발해도 결국 아래로만 내려갑니다.
용어부터 정리하고 가겠습니다.
- 루트: 맨 위 노드. 하나뿐입니다.
- 부모와 자식: 바로 위아래로 연결된 관계입니다.
- 잎(leaf): 자식이 없는 노드입니다.
- 높이: 루트에서 가장 깊은 잎까지의 거리입니다.
자식이 최대 두 개인 트리를 이진 트리라고 하고, 아래에서 볼 것들은 전부 이진 트리입니다.
프론트엔드에서 매일 보는 트리도 있습니다. DOM이 그렇습니다. document가 루트고 각 엘리먼트가 자식을 가지며, 텍스트 노드처럼 자식이 없는 것이 잎입니다.
이진 탐색 트리
값을 넣을 때 규칙을 하나 두면 트리가 탐색용 구조가 됩니다.
왼쪽 자식은 부모보다 작고, 오른쪽 자식은 부모보다 큽니다. 이 규칙을 지키면 찾을 때 절반씩 버릴 수 있습니다. 찾는 값이 현재 노드보다 작으면 오른쪽은 볼 필요가 없기 때문입니다.
코드
class Node {
constructor(value) {
this.value = value;
this.left = null;
this.right = null;
}
}
class BinarySearchTree {
constructor() {
this.root = null;
}
insert(value) {
const node = new Node(value);
// 비어 있으면 새 노드가 루트가 된다
if (!this.root) {
this.root = node;
return;
}
let current = this.root;
while (true) {
// 작으면 왼쪽, 크면 오른쪽으로 내려간다
const direction = value < current.value ? 'left' : 'right';
// 그쪽이 비어 있으면 거기가 제자리다
if (!current[direction]) {
current[direction] = node;
return;
}
current = current[direction];
}
}
has(value) {
let current = this.root;
while (current) {
if (current.value === value) {
return true;
}
// 비교 결과에 따라 한쪽을 통째로 버리고 내려간다.
// 한 번 내려갈 때마다 후보가 절반으로 줄어든다
current = value < current.value ? current.left : current.right;
}
return false;
}
}
const tree = new BinarySearchTree();
[8, 3, 10, 1, 6].forEach(value => tree.insert(value));
console.log(tree.has(6)); // true
console.log(tree.has(7)); // false위 값들을 넣으면 이런 모양이 됩니다.
8
/ \
3 10
/ \
1 6
6을 찾을 때 8보다 작으니 오른쪽 가지를 통째로 버리고, 3보다 크니 왼쪽을 버립니다. 다섯 개가 들어 있는데 두 번만 내려가면 도착합니다.
시간 복잡도
- 균형이 잡혀 있으면 한 번 내려갈 때마다 남은 후보가 절반씩 줄어듭니다. 트리 높이만큼만 내려가면 되므로 O(logn) 입니다.
- 문제는 균형이 항상 잡히지는 않는다는 점입니다.
이미 정렬된 값을 순서대로 넣으면 한쪽으로만 자랍니다.
const tree = new BinarySearchTree();
[1, 3, 6, 8, 10].forEach(value => tree.insert(value));1
\
3
\
6
\
8
\
10
갈라지지 않고 한 줄이 되어버려 연결 리스트와 같아집니다. 이 경우 탐색은 O(n)입니다. 퀵 정렬이 pivot을 잘못 골라 한쪽으로 쏠렸을 때와 똑같은 상황입니다. AVL 트리나 레드블랙 트리처럼 실무에서 쓰이는 트리들이 넣을 때마다 노드를 회전시켜 균형을 맞추는 이유가 이것입니다.
힙
부모와 자식 사이에만 크기 규칙이 있는 완전 이진 트리입니다.
정렬편 6탄에서 힙 정렬을 하며 만들었던 구조입니다. 그때는 정렬을 위한 도구로 봤지만, 힙 자체가 쓸모 있는 자료구조입니다.
이진 탐색 트리와 헷갈리기 쉬운데 규칙이 다릅니다.
- 이진 탐색 트리: 왼쪽 < 부모 < 오른쪽. 좌우가 구분됩니다.
- 힙: 부모가 자식보다 크기만(또는 작기만) 하면 됩니다. 좌우 구분이 없습니다.
그래서 힙은 정렬된 상태가 아닙니다. 형제끼리는 아무 관계가 없습니다. 대신 루트가 항상 최댓값(또는 최솟값)이라는 것만 보장합니다.
우선순위 큐
1탄의 큐는 먼저 들어온 것이 먼저 나왔습니다. 우선순위 큐는 들어온 순서와 상관없이 우선순위가 가장 높은 것이 먼저 나옵니다.
힙이 정확히 이 일을 합니다. 루트가 항상 최댓값이니 꺼내기만 하면 됩니다.
코드
6탄에서 만든 heapify를 그대로 씁니다.
class PriorityQueue {
constructor() {
this.items = [];
}
// 맨 뒤에 넣고 제자리를 찾을 때까지 위로 올린다
push(value) {
this.items.push(value);
let index = this.items.length - 1;
while (index > 0) {
const parent = Math.floor((index - 1) / 2);
// 부모가 더 크면 이미 규칙을 지키고 있다
if (this.items[parent] >= this.items[index]) {
break;
}
[this.items[parent], this.items[index]] = [this.items[index], this.items[parent]];
index = parent;
}
}
// 루트(최댓값)를 꺼내고 마지막 값을 루트로 올린 뒤 다시 내려보낸다
pop() {
if (this.items.length <= 1) {
return this.items.pop();
}
const top = this.items[0];
this.items[0] = this.items.pop();
this.heapify(0);
return top;
}
heapify(index) {
const size = this.items.length;
let largest = index;
const left = index * 2 + 1;
const right = index * 2 + 2;
if (left < size && this.items[left] > this.items[largest]) {
largest = left;
}
if (right < size && this.items[right] > this.items[largest]) {
largest = right;
}
if (largest === index) {
return;
}
[this.items[index], this.items[largest]] = [this.items[largest], this.items[index]];
this.heapify(largest);
}
}
const queue = new PriorityQueue();
[3, 10, 1, 8].forEach(value => queue.push(value));
console.log(queue.pop()); // 10
console.log(queue.pop()); // 8
console.log(queue.pop()); // 3넣은 순서가 3, 10, 1, 8인데 큰 값부터 나옵니다.
넣을 때는 맨 뒤에 붙인 뒤 부모와 비교하며 위로 올라가고, 꺼낼 때는 루트를 빼낸 자리에 마지막 값을 올린 뒤 아래로 내려보냅니다. 양쪽 모두 트리 높이만큼만 움직이므로 O(logn)입니다.
매번 전체를 훑어 최댓값을 찾으면 O(n)이고, 정렬해두면 넣을 때마다 O(n)이 듭니다. 힙은 넣기와 꺼내기 모두 O(logn)이라 둘 사이의 균형이 좋습니다.
그래프
앞에서 트리는 아래로만 갈라지고 위로 되돌아가는 길이 없다고 했습니다. 그 제약을 풀면 그래프가 됩니다.
정점끼리 자유롭게 연결되고, 돌아오는 길이 생겨도 됩니다. 즉 트리는 사이클이 없고 모든 정점이 하나로 이어진 그래프의 특수한 경우입니다.
- 정점(vertex): 노드에 해당합니다.
- 간선(edge): 정점을 잇는 선입니다.
- 방향의 유무: 한쪽으로만 갈 수 있으면 방향 그래프, 양쪽 다 오갈 수 있으면 무방향 그래프입니다.
- 사이클: 출발한 정점으로 되돌아오는 경로입니다. 트리에는 없고 그래프에는 있을 수 있습니다.
표현하는 두 가지 방법
그래프 자체는 개념이라 코드로 옮기려면 담을 그릇을 정해야 합니다. 방법이 두 가지인데, 고르는 기준이 1탄의 배열과 연결 리스트를 고르던 것과 같습니다.
인접 행렬은 정점 수만큼의 2차원 배열을 만들고 연결 여부를 칸에 적습니다. matrix[a][b]만 보면 되니 연결 확인이 O(1)이지만, 간선이 몇 개든 정점 수의 제곱만큼 메모리를 씁니다.
인접 리스트는 정점마다 이웃 목록을 들고 있습니다. 실제로 있는 간선만큼만 메모리를 쓰지만, 연결 여부를 알려면 그 목록을 뒤져야 합니다.
간선이 촘촘하면 행렬이, 듬성듬성하면 리스트가 유리합니다. 현실의 그래프는 대개 듬성듬성해서 리스트를 더 많이 씁니다.
코드
class Graph {
constructor() {
// 정점 -> 이웃 목록. 인접 리스트 방식이다
this.adjacency = new Map();
}
addVertex(vertex) {
if (!this.adjacency.has(vertex)) {
this.adjacency.set(vertex, new Set());
}
}
addEdge(a, b) {
this.addVertex(a);
this.addVertex(b);
// 무방향 그래프라 양쪽에 서로를 등록한다.
// 방향 그래프라면 a -> b 한 줄만 남긴다
this.adjacency.get(a).add(b);
this.adjacency.get(b).add(a);
}
neighbors(vertex) {
return [...(this.adjacency.get(vertex) ?? [])];
}
hasEdge(a, b) {
return this.adjacency.get(a)?.has(b) ?? false;
}
}
const graph = new Graph();
graph.addEdge('a', 'b');
graph.addEdge('a', 'c');
graph.addEdge('b', 'c');
console.log(graph.neighbors('a')); // ['b', 'c']
console.log(graph.hasEdge('b', 'c')); // true
console.log(graph.hasEdge('a', 'z')); // false이웃 목록을 배열이 아니라 Set으로 담은 이유가 있습니다. 배열이면 hasEdge가 목록을 훑어야 하는데, 2탄에서 본 대로 Set은 해시 기반이라 평균 O(1)에 확인됩니다. 같은 간선을 두 번 넣어도 알아서 하나로 유지되는 것도 덤입니다.
프론트엔드에서의 그래프
번들러가 다루는 모듈 의존 관계가 그래프입니다. 파일이 정점이고 import가 간선입니다.
컴포넌트 구조는 트리인데 의존 관계는 왜 그래프냐면, import는 서로를 가리킬 수 있기 때문입니다. A가 B를 부르고 B가 다시 A를 부르면 사이클이 생깁니다. 순환 참조 경고가 바로 이것이고, 트리에는 애초에 생길 수 없는 모양입니다.
정리
- 트리는 아래로 갈라지는 계층 구조이고, DOM이 대표적인 예입니다.
- 이진 탐색 트리는 좌우 규칙 덕분에 절반씩 버리며 찾지만, 한쪽으로 쏠리면 연결 리스트가 됩니다.
- 힙은 부모와 자식 사이에만 규칙이 있어 정렬된 상태가 아니고, 루트가 최댓값이라는 것만 보장합니다.
- 그 성질을 그대로 쓰면 우선순위 큐가 됩니다.
- 트리에서 사이클 제약을 풀면 그래프입니다. 담는 방법은 인접 행렬과 인접 리스트 두 가지입니다.
그래프는 만들어 두는 것보다 훑는 것이 본론입니다. 어떤 정점에서 다른 정점까지 갈 수 있는지, 가장 짧은 길은 무엇인지는 다음 시리즈인 탐색편에서 다루겠습니다.