Tree(트리)는 노드(Node)와 에지(Edge)로 구성된 계층적 자료구조입니다. 최상위 노드인 루트(Root)에서 시작하여 자식 노드로 뻗어나가는 구조로, 사이클이 없는 연결 그래프입니다. 각 노드는 데이터와 자식 노드에 대한 참조를 가지며, 부모-자식 관계로 계층을 형성합니다. 깊이(Depth), 높이(Height), 레벨(Level) 등의 개념으로 트리의 구조를 표현합니다.
트리의 종류: 이진 트리(Binary Tree)는 각 노드가 최대 2개의 자식을 가지는 기본 형태입니다. 이진 탐색 트리(BST, Binary Search Tree)는 왼쪽 자식 < 부모 < 오른쪽 자식 규칙으로 정렬됩니다. AVL 트리와 Red-Black 트리는 자가 균형(Self-Balancing) 트리로 O(log n) 성능을 보장합니다. B-Tree와 B+ Tree는 디스크 기반 저장소에 최적화되어 데이터베이스 인덱스에 사용됩니다.
시간복잡도: 일반 BST는 평균 O(log n)이지만 편향되면 O(n)까지 저하됩니다. AVL/Red-Black 트리는 항상 O(log n)을 보장합니다. B-Tree는 디스크 I/O를 최소화하여 대용량 데이터에서 효율적입니다. 힙(Heap)은 완전 이진 트리로 삽입/삭제가 O(log n), 최소/최대값 조회는 O(1)입니다.
실무 활용: 웹 브라우저의 DOM(Document Object Model)은 HTML을 트리 구조로 표현합니다. 파일 시스템은 디렉토리-파일 관계를 트리로 관리합니다. 데이터베이스의 B+ Tree 인덱스는 수백만 건의 레코드에서 밀리초 단위 검색을 가능하게 합니다. AI/ML에서는 결정 트리(Decision Tree), 의사결정 프로세스 표현에 널리 사용됩니다.
📊 시간복잡도 비교
트리 종류별 연산 시간복잡도 비교입니다.
트리 종류
검색
삽입
삭제
공간
BST (평균)
O(log n)
O(log n)
O(log n)
O(n)
BST (최악)
O(n)
O(n)
O(n)
O(n)
AVL / Red-Black
O(log n)
O(log n)
O(log n)
O(n)
B-Tree
O(log n)
O(log n)
O(log n)
O(n)
Heap
O(n)
O(log n)
O(log n)
O(n)
선택 기준: 메모리 기반 검색이 주 목적이면 AVL/Red-Black, 디스크 I/O가 많으면 B-Tree, 우선순위 처리가 필요하면 Heap을 사용합니다.
💻 코드 예제
# 이진 탐색 트리 (BST) 구현
class TreeNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
class BST:
def __init__(self):
self.root = None
# 삽입 - O(log n) 평균, O(n) 최악
def insert(self, val):
if not self.root:
self.root = TreeNode(val)
return
def _insert(node, val):
if val < node.val:
if node.left is None:
node.left = TreeNode(val)
else:
_insert(node.left, val)
else:
if node.right is None:
node.right = TreeNode(val)
else:
_insert(node.right, val)
_insert(self.root, val)
# 검색 - O(log n) 평균
def search(self, val):
def _search(node, val):
if node is None or node.val == val:
return node
if val < node.val:
return _search(node.left, val)
return _search(node.right, val)
return _search(self.root, val)
# 트리 순회 (Traversal)
def inorder(self, node, result=None):
"""중위 순회: 왼쪽 → 루트 → 오른쪽 (정렬된 순서)"""
if result is None:
result = []
if node:
self.inorder(node.left, result)
result.append(node.val)
self.inorder(node.right, result)
return result
def preorder(self, node, result=None):
"""전위 순회: 루트 → 왼쪽 → 오른쪽 (복사에 유용)"""
if result is None:
result = []
if node:
result.append(node.val)
self.preorder(node.left, result)
self.preorder(node.right, result)
return result
def postorder(self, node, result=None):
"""후위 순회: 왼쪽 → 오른쪽 → 루트 (삭제에 유용)"""
if result is None:
result = []
if node:
self.postorder(node.left, result)
self.postorder(node.right, result)
result.append(node.val)
return result
# 레벨 순회 (BFS)
def level_order(self):
"""너비 우선 탐색: 레벨별로 순회"""
from collections import deque
if not self.root:
return []
result = []
queue = deque([self.root])
while queue:
node = queue.popleft()
result.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
return result
# 사용 예시
bst = BST()
for val in [50, 30, 70, 20, 40, 60, 80]:
bst.insert(val)
print("중위 순회:", bst.inorder(bst.root)) # [20, 30, 40, 50, 60, 70, 80]
print("전위 순회:", bst.preorder(bst.root)) # [50, 30, 20, 40, 70, 60, 80]
print("레벨 순회:", bst.level_order()) # [50, 30, 70, 20, 40, 60, 80]
# 검색
node = bst.search(40)
print(f"검색 결과: {node.val if node else 'Not found'}") # 40
// 이진 탐색 트리 (BST) 구현
class TreeNode {
constructor(val) {
this.val = val;
this.left = null;
this.right = null;
}
}
class BST {
constructor() {
this.root = null;
}
// 삽입
insert(val) {
const newNode = new TreeNode(val);
if (!this.root) {
this.root = newNode;
return;
}
let current = this.root;
while (true) {
if (val < current.val) {
if (!current.left) {
current.left = newNode;
break;
}
current = current.left;
} else {
if (!current.right) {
current.right = newNode;
break;
}
current = current.right;
}
}
}
// 검색
search(val) {
let current = this.root;
while (current) {
if (val === current.val) return current;
current = val < current.val ? current.left : current.right;
}
return null;
}
// 중위 순회 (정렬된 결과)
inorder(node = this.root, result = []) {
if (node) {
this.inorder(node.left, result);
result.push(node.val);
this.inorder(node.right, result);
}
return result;
}
// 레벨 순회 (BFS)
levelOrder() {
if (!this.root) return [];
const result = [];
const queue = [this.root];
while (queue.length > 0) {
const node = queue.shift();
result.push(node.val);
if (node.left) queue.push(node.left);
if (node.right) queue.push(node.right);
}
return result;
}
// 트리 높이
getHeight(node = this.root) {
if (!node) return -1;
return 1 + Math.max(
this.getHeight(node.left),
this.getHeight(node.right)
);
}
}
// 사용 예시
const bst = new BST();
[50, 30, 70, 20, 40, 60, 80].forEach(val => bst.insert(val));
console.log('중위 순회:', bst.inorder()); // [20, 30, 40, 50, 60, 70, 80]
console.log('레벨 순회:', bst.levelOrder()); // [50, 30, 70, 20, 40, 60, 80]
console.log('트리 높이:', bst.getHeight()); // 2
// DOM 트리 순회 예시 (실무)
function traverseDOM(element, depth = 0) {
console.log(' '.repeat(depth) + element.tagName);
for (const child of element.children) {
traverseDOM(child, depth + 1);
}
}
// traverseDOM(document.body);
import java.util.*;
// 이진 탐색 트리 (BST) 구현
class TreeNode {
int val;
TreeNode left, right;
TreeNode(int val) {
this.val = val;
this.left = null;
this.right = null;
}
}
class BST {
private TreeNode root;
// 삽입
public void insert(int val) {
root = insertRec(root, val);
}
private TreeNode insertRec(TreeNode node, int val) {
if (node == null) {
return new TreeNode(val);
}
if (val < node.val) {
node.left = insertRec(node.left, val);
} else {
node.right = insertRec(node.right, val);
}
return node;
}
// 검색
public TreeNode search(int val) {
return searchRec(root, val);
}
private TreeNode searchRec(TreeNode node, int val) {
if (node == null || node.val == val) {
return node;
}
return val < node.val
? searchRec(node.left, val)
: searchRec(node.right, val);
}
// 중위 순회
public List inorder() {
List result = new ArrayList<>();
inorderRec(root, result);
return result;
}
private void inorderRec(TreeNode node, List result) {
if (node != null) {
inorderRec(node.left, result);
result.add(node.val);
inorderRec(node.right, result);
}
}
// 레벨 순회 (BFS)
public List levelOrder() {
List result = new ArrayList<>();
if (root == null) return result;
Queue queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
TreeNode node = queue.poll();
result.add(node.val);
if (node.left != null) queue.offer(node.left);
if (node.right != null) queue.offer(node.right);
}
return result;
}
public static void main(String[] args) {
BST bst = new BST();
int[] values = {50, 30, 70, 20, 40, 60, 80};
for (int val : values) {
bst.insert(val);
}
System.out.println("중위 순회: " + bst.inorder());
// [20, 30, 40, 50, 60, 70, 80]
System.out.println("레벨 순회: " + bst.levelOrder());
// [50, 30, 70, 20, 40, 60, 80]
TreeNode found = bst.search(40);
System.out.println("검색 결과: " + (found != null ? found.val : "Not found"));
}
}
🗣️ 실무에서 이렇게 말하세요
💬 면접에서 - BST vs Hash Table
"BST와 Hash Table 모두 검색에 사용되지만 특성이 다릅니다. Hash Table은 평균 O(1) 검색이지만 순서 보장이 없고, BST는 O(log n)이지만 정렬된 순서로 순회가 가능합니다. 범위 검색이나 최소/최대값이 자주 필요하면 BST(또는 TreeMap), 단순 키-값 조회가 주 목적이면 Hash Table을 선택합니다."
💬 설계 회의에서 - 트리 구조 선택
"사용자 카테고리 계층을 저장해야 하는데요. 깊이가 5레벨 정도이고 카테고리 이동이 잦습니다. Nested Set은 조회는 빠르지만 이동 시 대량 업데이트가 필요해서, Materialized Path나 Closure Table이 더 적합할 것 같습니다. 카테고리 수가 1만 개 미만이라 Closure Table로 가겠습니다."
💬 코드 리뷰에서
"여기서 정렬된 데이터를 BST에 순차 삽입하면 편향 트리가 되어 O(n) 검색이 됩니다. TreeSet이나 TreeMap을 쓰시면 내부적으로 Red-Black 트리라 자동 균형이 유지돼요. 아니면 삽입 전에 데이터를 셔플하는 것도 방법입니다."
⚠️ 흔한 실수 & 주의사항
❌
균형 유지 무시
정렬된 데이터를 일반 BST에 삽입하면 연결 리스트처럼 편향되어 O(n) 성능. AVL, Red-Black 트리를 사용하거나 데이터를 셔플 후 삽입하세요.
❌
재귀 깊이 초과 (Stack Overflow)
깊은 트리에서 재귀 순회 시 스택 오버플로우 발생 가능. 깊이가 1000 이상이면 반복문 + 명시적 스택을 사용하거나, Python은 sys.setrecursionlimit() 조정이 필요합니다.
❌
메모리 사용량 과소평가
트리 노드는 데이터 외에 포인터(참조)를 저장합니다. n개 노드의 이진 트리는 2n개의 포인터(null 포함)를 사용. 대용량에서는 B-Tree처럼 노드당 여러 키를 저장하는 구조가 효율적입니다.
✅
올바른 접근법
목적에 맞는 트리 선택: 메모리 검색은 AVL/Red-Black, 디스크 기반은 B-Tree, 우선순위는 Heap. 표준 라이브러리(Java TreeMap, C++ std::map, Python sortedcontainers)를 적극 활용하세요.