트리의 종류
트리를 이해하기 위한 좋은 방법 중 하나는 재귀적 설명법을 사용하는 것입니다. 트리는 노드로 이루어진 자료구조입니다. 트리가 가질 수 있는 몇 가지 특징이 있습니다. 여기서 가질 수 있는이라고 표현한 이유는 모든 트리가 동일한 형태와 구조로 구성이 되어 있지 않기 때문입니다.
- 트리는 하나의 루트 노드를 갖는다(그래프 이론에 따르면 반드시 루트 노드를 가져야 하는 것은 아니지만 트리를 구분할 수 있는 눈에 띄는 특징 중 하나입니다.)
- 루트 노드는 0개 이상의 자식 노드를 갖고 있다.
- 그 자식 노드 또한 0개 이상의 자식 노드를 갖고 있고, 이는 반복적으로 정의된다.
트리에는 사이클(cycle)이 존재할 수 없습니다. 노드들은 특정 순서로 나열될 수도 있을 수 있습니다. 각 노드를 어떤 자료형으로도 표현할 수 있습니다. 각 노드는 부모 노드로 연결되어 있을 수도 있지만 아닐 수도 있습니다.
이진트리
이진 트리(binary tree) 는 각 노드가 최대 두 개의 자식을 갖는 트리를 말합니다. 최대 두 개이기 때문에 자식 노드가 한 개이거나 없을 수 있습니다. 위 그림의 오른쪽 트리는 이진트리가 아니지만 트리를 다루다보면 이진 트리가 아닌 트리를 다루어야 할 때가 있습니다. 예를들어, 전화번호를 표현하기 위한 트리를 사용한다고 가정할 경우 각 노드가 10개의 자식을 갖는 10차 트리를 사용해야 할 수 있습니다.
완전 이진 트리
완전 이진 트리(complete binary tree) 는 트리의 모든 높이에서 노드가 꽉 차 있는 이진 트리를 의미합니다. 마지막 단계는 꽉 차 있지 않아도 되지만 노드가 왼쪽에서 오른쪽으로 채워져야 합니다. 오른쪽 트리는 비워져 있는 상태여도 되지만 왼쪽 트리가 비워진 상태일 경우 이는 완전 이진 트리의 조건을 달성한다고 할 수 없습니다.
완전 이진 트리는 노드들이 왼쪽부터 빈틈없이 채워지므로 1차원 배열로 완벽하게 표현을 할 수 있습니다. 이러한 특징으로 인해서 다음과 같은 사용이 가능합니다.
const left_index = idx * 2 + 1;
const right_index = idx * 2 + 2;
const parent = Math.floor(idx / 2);
이 특징 덕분에 완전 이진 트리는 메모리 사용이 효율적이고, 연속된 공간에 데이터가 저장되므로 캐시 지역성 측면에서도 유리합니다. 그래서 완전 이진 트리는 단순히 “모양이 예쁜 트리”가 아니라, 배열 기반 트리 자료구조를 구현하기에 가장 실용적인 형태라고 볼 수 있습니다.
완전 이진 트리가 가장 대표적으로 사용되는 곳은 힙(Heap) 입니다. 여기서 중요한 점은 힙은 단순한 완전 이진 트리가 아니라, 완전 이진 트리의 구조 위에 부모와 자식 사이의 우선순위 규칙이 추가된 자료구조라는 것입니다.
- 최소 힙(Min-Heap): 부모 노드의 값이 자식 노드의 값보다 작거나 같다.
- 최대 힙(Max-Heap): 부모 노드의 값이 자식 노드의 값보다 크거나 같다.
이 힙을 이용하면 우선순위가 가장 높은 원소를 빠르게 꺼낼 수 있는 우선순위 큐(Priority Queue) 를 구현할 수 있습니다.
class PriorityQueue {
constructor(comparator) {
this.heap = [];
this.comparator = comparator;
}
}
위 구현에서 heap 배열 자체가 곧 완전 이진 트리입니다. 배열의 0번 인덱스가 루트 노드가 되고, 각 원소의 왼쪽 자식과 오른쪽 자식은 앞서 본 인덱스 계산 규칙에 따라 결정됩니다. 따라서 별도의 Node 객체를 만들거나 포인터를 연결하지 않아도 트리를 다룰 수 있습니다.
bubbleUp(idx) {
while (idx >= 0) {
const parent = Math.floor((idx - 1) / 2);
if (
parent >= 0 &&
this.comparator(this.heap[idx], this.heap[parent]) < 0
) {
this.swap(parent, idx);
idx = parent;
} else {
break;
}
}
}
push(val) {
this.heap.push(val);
this.bubbleUp(this.size - 1);
}
push 연산은 새로운 값을 배열의 맨 뒤에 추가한 뒤, bubbleUp을 수행합니다. 배열의 맨 뒤에 원소를 추가하는 이유는 완전 이진 트리의 형태를 유지하기 위해서입니다. 마지막 자리에 새 노드를 붙인 뒤, 부모와 우선순위를 비교하면서 위로 올려 보내면 힙의 정렬 조건까지 함께 복원할 수 있습니다. 즉, bubbleUp은 완전 이진 트리의 구조는 유지한 채, 힙의 우선순위 규칙만 다시 맞추는 과정입니다.
bubbleDown(idx) {
while (idx < this.heap.length) {
const left = idx * 2 + 1;
const right = idx * 2 + 2;
let candidate = idx;
if (
left < this.size &&
this.comparator(this.heap[left], this.heap[candidate]) < 0
) {
candidate = left;
}
if (
right < this.size &&
this.comparator(this.heap[right], this.heap[candidate]) < 0
) {
candidate = right;
}
if (idx === candidate) break;
this.swap(idx, candidate);
idx = candidate;
}
}
shift() {
if (this.size === 0) return null;
const val = this.top;
this.swap(0, this.size - 1);
this.heap.pop();
this.bubbleDown(0);
return val;
}
반대로 shift 연산은 우선순위가 가장 높은 루트 노드를 제거하는 연산입니다. 루트 노드를 바로 제거하면 완전 이진 트리의 모양이 깨지기 때문에, 먼저 마지막 원소를 루트 위치로 가져온 뒤 마지막 원소를 제거합니다. 그 다음 bubbleDown을 수행하여 자식 노드들과 비교하면서 아래로 내려 보내면 다시 힙의 규칙이 맞춰집니다. 즉, bubbleDown은 루트 제거 이후 흐트러진 우선순위 구조를 아래 방향으로 복구하는 과정입니다.
이 과정을 통해 우선순위 큐는 다음과 같은 성능을 갖게 됩니다.
push: 원소 삽입 → O(log N)shift: 우선순위가 가장 높은 원소 제거 → O(log N)
왜 O(log N)이 되는지도 완전 이진 트리의 구조로 설명할 수 있습니다. 완전 이진 트리는 높이가 대략 log N이기 때문에, bubbleUp과 bubbleDown은 최악의 경우에도 루트에서 리프까지 한 경로만 이동하면 됩니다. 즉, 전체 배열을 매번 순회하지 않아도 우선순위를 유지할 수 있습니다.
따라서 완전 이진 트리는 단순한 트리의 한 종류를 넘어, 실제 알고리즘 문제나 시스템 구현에서 자주 사용되는 힙과 우선순위 큐의 기반 구조라고 이해하는 것이 가장 중요합니다.
전 이진 트리
전 이진 트리(full binary tree) 는 모든 노드의 자식이 없거나 정확히 두 개 있는 경우를 의미합니다. 즉, 자식이 하나만 있는 노드가 존재해서는 안된다는 것입니다. 이 트리를 활용되는 곳은 데이터 압축에 사용이 됩니다. ZIP 파일이나 JPEG 등에서 사용되는 무손실 압축 알고리즘인 허프만 코딩은 데이터의 출현 빈도수에 따라 가변 길이의 코드를 부여합니다. 이 코드를 생성하기 위해 트리를 구축할 때 전 이진 트리 형태가 만들어집니다.
class HuffmanNode {
constructor(char, freq, left = null, right = null) {
this.char = char; // 문자 (내부 노드는 null)
this.freq = freq; // 빈도수
this.left = left; // 왼쪽 자식
this.right = right; // 오른쪽 자식
}
}
하프만 코딩의 목적은 문자를 0과 1로 이루어진 이진 코드로 변환하는 것입니다. 트리가 완성된 후 루트에서부터 특정 문자가 있는 리프 노드까지 찾아 내려갈 때, 왼쪽 간선을 탈 때는, 0을 오른쪽 간선을 탈 때는 1을 코드에 덧붙이는 것이 보편적인 규칙입니다.
function buildHuffmanTree(freqMap) {
// 초기 노드 배열 생성
const nodes = Object.entries(freqMap).map(
([char, freq]) => new HuffmanNode(char, freq),
);
// 노드가 하나만 남을 때까지 반복
while (nodes.length > 1) {
// 빈도수 오름차순 정렬 (실제 프로덕션 환경에서는 성능을 위해 우선순위 큐/최소 힙 사용)
nodes.sort((a, b) => a.freq - b.freq);
// 가장 빈도수가 낮은 두 노드 추출
const left = nodes.shift();
const right = nodes.shift();
// 두 노드를 합친 새로운 내부 노드 생성
const merged = new HuffmanNode(null, left.freq + right.freq, left, right);
// 새 노드를 배열에 추가
nodes.push(merged);
}
// 트리의 루트 노드 반환
return nodes[0];
}
트리를 구축할 때 큐에서 빈도수가 가장 작은 두 개의 노드를 뽑아 부모 노드로 병합합니다. 이때 많은 구현체에서 빈도수가 더 작은 노드를 왼쪽 자식으로, 상대적으로 큰 노드를 오른쪽 자식으로 배치하는 관례를 따릅니다.
function generateCodeTable(node, currentCode = '', codes = {}) {
if (!node) return codes;
// 리프 노드에 도달하면 문자와 코드를 매핑
if (node.char !== null) {
codes[node.char] = currentCode;
}
// 왼쪽은 '0', 오른쪽은 '1'을 덧붙임
generateCodeTable(node.left, currentCode + '0', codes);
generateCodeTable(node.right, currentCode + '1', codes);
return codes;
}
하지만 이는 알고리즘의 필수 규칙이 아닙니다. 왼쪽과 오른쪽의 배치가 바뀌어도(즉, 0과 1이 반대로 할당되어도) 각 문자에 부여되는 코드의 '길이'는 동일하게 유지되므로 전체 파일의 압축률에는 전혀 영향을 주지 않습니다. 그래도 앞서 이야기한 것과 같이 관레에 따라 왼쪽 노드에는 0을 오른쪽 노드에는 1을 덧붙여서 코드 테이블을 구성합니다.
function encode(str, codeTable) {
return str
.split('')
.map((char) => codeTable[char])
.join('');
}
// 4-2. 디코딩 (압축 해제)
function decode(encodedStr, root) {
let decodedStr = '';
let currentNode = root;
for (const bit of encodedStr) {
// 비트에 따라 왼쪽 또는 오른쪽 자식으로 이동
if (bit === '0') currentNode = currentNode.left;
else currentNode = currentNode.right;
// 리프 노드에 도달하면 문자를 추가하고 다시 루트로 돌아감
if (currentNode.char !== null) {
decodedStr += currentNode.char;
currentNode = root;
}
}
return decodedStr;
}
encode 과정에서는 코드테이블을 사용해서 이진 데이터로 표현된 문자를 원분 문자열의 순서에 맞춰서 이진 문자열을 생성합니다. 이 후 decode를 수행할 경우에는 앞서 코드 테이블을 사용할때의 규칙에 맞춰 문자가 0 인 경우 왼쪽 노드로 이동을 하고 1인 경우에는 오른쪽 노드로 이동을 수행합니다. 현재 노드의 값이 null이 아닌 경우 해당 문자를 찾은것이기 때문에 원본 문자열에 추가하여 복원 시킬 수 있습니다.
원본 문자열: A_DEAD_DAD_CEDED_A_BAD_BABE_A_BEADED_ABACA_BED
[허프만 코드 테이블]
{ _: '00', D: '01', A: '10', E: '110', C: '1110', B: '1111' }
압축된 이진 데이터: 1000011101001000110010011101100111001001000111110010011111011111100010001111110100111001001011111011101000111111001
복원된 문자열: A_DEAD_DAD_CEDED_A_BAD_BABE_A_BEADED_ABACA_BED
원본 크기: 368 bits
압축 크기: 115 bits
압축률: 68.75%
하프만 코딩이 데이터 압축에 유리한 이유가 무엇일까요? 일반적인 텍스트 인코딩(예: ASCII)은 문자의 등장 빈도와 상관없이 모든 문자에 동일한 길이(보통 8비트)를 할당합니다. 자주 쓰이는 'A'나 드물게 쓰이는 'Z'가 똑같은 용량을 차지합니다.
그래서 압축을 대상으로 하는 문자열의 빈도수를 계산한 후 가장 많이 등장하는 문자에 가장 짧은 코드(예: 0 또는 10 등 1~2비트)를 부여하고, 적게 등장하는 문자에 긴 코드를 부여합니다. 결과적으로 전체 데이터에서 절대다수를 차지하는 빈출 문자들의 비트 길이가 크게 줄어들기 때문에, 희귀 문자의 비트 길이가 길어지더라도 전체 데이터의 총 용량(비트 수)은 감소하게 됩니다.
포화 이진 트리
모든 내부 노드가 2개의 자식을 가지고 있고, 모든 리프 노드의 깊이가 동일한 완벽한 피라미드 형태의 트리입니다. 노드의 개수는 정확히 2의 거듭제곱에서 1을 뺀 값 이 됩니다. 우리가 포화 이진 트리를 사용할 수 있는 경우는 특정 구간의 합이나 최솟값을 빠르게 구하는 세그먼트 트리(Segment Tree)를 배열로 구현할 때 주로 사용하게 됩니다.
class SegmentTree {
constructor(arr) {
this.n = arr.length;
// tree 의 크기의 경우 node 를 기반으로 트리를 만들면서 만들기 위해서 넉넉하게 큰 크기로 만드는 것이 필요하다.
this.tree = new Array(this.n * 4).fill(0);
this.build(arr, 1, 0, N - 1);
}
}
세그먼트 트리를 구현할때 메모리 충돌(Out of Bounds)을 막기 위해 넉넉한 배열 크기를 잡아야 합니다. 이때 데이터의 개수가 N개라면, N을 수용할 수 있는 가장 가까운 포화 이진 트리의 전체 노드 수(대략 4N 크기)를 계산하여 안전하게 메모리를 할당하는 기준점 역할을 합니다.
function build(node, start, end) {
if (start === end) {
tree[node] = arr[start];
return tree[node];
}
const mid = math.floor((start + end) / 2);
const leftsum = build(node * 2, start, mid);
const rightsum = build(node * 2 + 1, mid + 1, end);
tree[node] = leftsum + rightsum;
return tree[node];
}
build 함수는 세그먼트 트리를 처음 한 번 구성하는 과정입니다. 현재 노드가 표현하는 구간이 원본 배열의 원소 하나만을 가리키는 경우(start === end), 더 이상 쪼갤 수 없으므로 해당 값을 그대로 저장합니다. 이 노드는 세그먼트 트리에서 리프 노드가 됩니다.
반대로 하나 이상의 원소를 포함하는 구간이라면, 현재 구간을 가운데 기준으로 두 부분으로 나누고 왼쪽 자식과 오른쪽 자식을 재귀적으로 생성합니다. 이후 두 자식이 저장한 값을 합쳐 현재 노드에 저장합니다. 즉, 각 노드는 자신이 담당하는 구간의 합을 가지게 됩니다.
이 과정을 루트부터 시작하면 전체 배열에 대한 구간 합 정보가 트리 전체에 채워지게 됩니다. 중요한 점은 build는 탐색을 빠르게 만들기 위한 사전 계산(preprocessing) 단계라는 것입니다. 전체 배열의 모든 원소를 한 번씩 반영하여 트리를 구성하므로 시간 복잡도는 O(N) 입니다.
function update(node, start, end, index, val) {
if (start > index || index > end) {
return;
}
if (start === end) {
tree[node] = val;
return;
}
const mid = Math.floor((start + end) / 2);
update(node * 2, start, mid, index, val);
update(node * 2 + 1, mid + 1, end, index, val);
tree[node] = tree[node * 2] + tree[node * 2 + 1];
}
update 함수는 원본 배열의 특정 인덱스 값이 변경되었을 때, 그 영향을 받는 노드들만 다시 계산하는 역할을 합니다. 세그먼트 트리의 핵심은 전체를 다시 계산하지 않고, 변경된 인덱스를 포함하는 경로만 따라 내려간다는 점입니다.
먼저 현재 노드가 담당하는 구간이 수정하려는 인덱스를 포함하지 않는다면 바로 종료합니다. 이 경우 해당 구간의 합은 전혀 변하지 않기 때문입니다. 반대로 현재 구간이 단 하나의 원소만 표현하는 리프 노드라면, 그 노드의 값을 새로운 값으로 교체합니다.
이후 재귀 호출이 끝나면, 부모 노드는 변경된 자식들의 값을 다시 합산하여 자신의 값을 갱신합니다. 즉, 값 하나를 수정하더라도 실제로 다시 계산되는 것은 루트에서 해당 리프까지 이어지는 경로뿐입니다. 그래서 갱신 연산의 시간 복잡도는 O(log N) 이 됩니다.
function query(node, start, end, left, right) {
if (start > left || right > end) {
return 0;
}
if (start <= left && right <= end) {
return tree[node];
}
const mid = Math.floor((start + end) / 2);
const leftSum = query(node * 2, start, mid, left, right);
const rightSum = query(node * 2 + 1, mid + 1, end, left, right);
return leftSum + rightSum;
}
query 함수는 원하는 구간 [left, right]의 합을 빠르게 구하는 연산입니다. 이 함수는 현재 노드가 담당하는 구간 [start, end]와 우리가 구하려는 구간 [left, right]의 관계를 기준으로 동작합니다.
첫 번째 경우는 전혀 겹치지 않는 경우입니다. 예를 들어 현재 구간이 [0, 3]인데 우리가 구하려는 범위가[5, 7]이라면, 이 구간은 결과에 아무런 영향을 주지 않습니다. 합 연산에서는 이런 경우 0을 반환하면 됩니다.
두 번째 경우는 현재 구간이 질의 범위에 완전히 포함되는 경우입니다. 이때는 더 아래로 내려갈 필요가 없습니다. 이미 tree[node]에 해당 구간의 합이 저장되어 있으므로 그 값을 그대로 반환하면 됩니다. 이것이 세그먼트 트리가 빠른 이유입니다.
세 번째 경우는 일부만 겹치는 경우입니다. 이때는 왼쪽 자식과 오른쪽 자식으로 내려가 각각의 결과를 구한 뒤, 두 값을 합쳐 최종 결과를 만듭니다. 결과적으로 필요한 구간만 선택적으로 탐색하게 되므로, 매번 배열을 처음부터 끝까지 순회하는 O(N) 방식보다 훨씬 효율적으로 구간 합을 구할 수 있고, 질의의 시간 복잡도는 O(log N) 입니다.
이진트리 vs 이진 탐색트리
이진 트리(Binary Tree) 와 이진 탐색 트리(Binary Search Tree, BST) 는 이름이 비슷해서 헷갈리기 쉽지만, 둘의 차이는 꽤 분명합니다.
이진 트리는 단순히 각 노드가 최대 두 개의 자식을 가질 수 있는 트리를 의미합니다. 즉, 중요한 것은 구조적인 조건뿐입니다. 왼쪽 자식과 오른쪽 자식이 있다는 점만 만족하면 되며, 노드의 값들이 어떤 순서로 배치되어 있는지는 중요하지 않습니다.
반면, 이진 탐색 트리는 이진 트리의 형태를 가지면서도 값의 크기에 대한 정렬 규칙이 추가된 트리입니다. 모든 노드들은 n에 대해서 모든 왼쪽 자식들 <= n < 모든 오른쪽 자식들 이라는 조건에 대해서 반드시 참이어야 합니다. 즉, 이진 탐색 트리는 “정렬 규칙이 있는 이진 트리” 라고 이해할 수 있습니다.
위의 왼쪽 그림은 유효한 이진 탐색 트리입니다. 루트 노드 8을 기준으로 왼쪽 서브트리에는 8보다 작은 값들만 있고, 오른쪽 서브트리에는 8보다 큰 값들만 있기 때문입니다. 반대로 오른쪽 그림은 루트 노드 8보다 큰 값인 12가 왼쪽 자식 쪽에 위치하고 있으므로, 이진 트리일 수는 있어도 이진 탐색 트리라고 할 수는 없습니다.
이 차이는 탐색 성능에서 큰 차이를 만듭니다. 일반적인 이진 트리는 값의 대소 관계에 대한 규칙이 없기 때문에, 특정 값을 찾으려면 최악의 경우 모든 노드를 확인해야 합니다. 즉, 탐색 시간 복잡도는 O(N) 입니다.
하지만 이진 탐색 트리는 현재 노드의 값과 비교해서 왼쪽으로 갈지 오른쪽으로 갈지를 결정할 수 있습니다.
예를 들어 17을 찾고 있는데 현재 노드가 10이라면, 17은 10보다 크므로 왼쪽 서브트리는 볼 필요 없이 곧바로 오른쪽으로 내려가면 됩니다. 이런 식으로 탐색 범위를 절반씩 줄여 나갈 수 있기 때문에, 트리가 균형 있게 유지된다는 가정 아래 탐색, 삽입, 삭제를 O(log N) 에 처리할 수 있습니다.
다만 여기서 중요한 점이 하나 있습니다. 많은 경우 이진 탐색 트리는 무조건 빠르다고 생각하기 쉽지만, 항상 O(log N) 이 되는 것은 아닙니다. 트리가 한쪽으로 치우치면 높이가 N에 가까워질 수 있고, 이 경우 탐색 성능도 결국 O(N) 까지 나빠질 수 있습니다.
1
\
2
\
3
\
4
\
5
예를 들어 정렬된 값 1, 2, 3, 4, 5를 차례대로 삽입하면 트리는 아래처럼 한쪽으로만 길게 늘어질 수 있습니다. 이 경우는 사실상 연결 리스트와 다를 바 없기 때문에, 이진 탐색 트리의 장점이 거의 사라집니다. 이러한 문제를 해결하기 위해 실제로는 AVL 트리, Red-Black Tree 같은 균형 이진 탐색 트리(Self-Balancing BST) 를 사용하여 트리의 높이를 적절히 유지합니다.
const result = [];
const stack = new Stack();
let current = 'A';
while (current !== '.' || !stack2.isEmpty()) {
while (current !== '.') {
stack.push(current);
current = adj[current][0];
}
current = stack.pop();
result.push(current);
current = adj[current][1];
}
또한 이진 탐색 트리의 중요한 특징 중 하나는 중위 순회(In-order Traversal) 를 수행하면 값들이 오름차순으로 정렬된 결과를 얻을 수 있다는 점입니다. 왼쪽 서브트리 → 현재 노드 → 오른쪽 서브트리 순서로 순회하면, BST의 정렬 규칙 덕분에 자연스럽게 정렬된 순서로 값을 방문하게 됩니다. 정리하면 다음과 같습니다.
- 이진 트리: 자식이 최대 두 개인 트리
- 이진 탐색 트리: 이진 트리에 값의 정렬 규칙이 추가된 트리
- 이진 트리의 탐색: 보통 O(N)
- 이진 탐색 트리의 탐색: 균형이 유지되면 O(log N), 치우치면 O(N)
즉, 두 자료구조의 가장 큰 차이는 구조만 가지는 트리인가, 아니면 탐색을 빠르게 하기 위한 정렬 규칙까지 가지는 트리인가 에 있습니다. 이진 탐색 트리는 단순히 “이진 트리의 한 종류”를 넘어, 정렬된 데이터를 효율적으로 저장하고 탐색하기 위해 고안된 구조라고 이해하는 것이 가장 중요합니다.