배열과 연결 리스트가 데이터를 일렬로 늘어놓는 선형 구조라면, 트리(Tree)는 나무의 뿌리(Root)에서 가지가 뻗어나가는 형태의 계층적(Hierarchical) 비선형 구조입니다. 특히 이진 탐색 트리(Binary Search Tree, BST)는 부모 노드를 기준으로 "작은 값은 왼쪽, 큰 값은 오른쪽"이라는 엄격한 규칙을 적용하여, 데이터를 탐색할 때마다 탐색 대상을 절반씩 줄여나가는 O(log N)의 기적적인 속도를 자랑합니다.
1. 이진 탐색 트리(BST)의 규칙과 탐색 시뮬레이션
2. 성능 및 특징 요약
연산 (Operation)
평균 시간 복잡도 (균형 트리)
최악의 경우 (편향 트리)
탐색 (Search)
O(log N)
O(N)
삽입 (Insert)
O(log N)
O(N)
삭제 (Delete)
O(log N)
O(N)
💡 실무 지식: 밸런스가 무너진 트리의 위험성 (편향 트리)
만약 트리 모델에 [10, 20, 30, 40, 50] 처럼 이미 정렬된 데이터를 순서대로 삽입하면 어떻게 될까요? 계속 오른쪽 가지로만 뻗어나가며 결국 연결 리스트와 다를 바 없는 일자형(편향) 트리가 되어버립니다. 이 경우 탐색 시간이 O(N)으로 극악의 성능 저하를 일으킵니다.
따라서 실무 시스템(특히 RDBMS의 데이터베이스 인덱스)에서는 노드를 추가/삭제할 때마다 스스로 밸런스를 조정하여 양쪽 깊이를 엇비슷하게 맞추는 AVL 트리, Red-Black 트리, B-Tree 등의 진화된 균형 탐색 트리 구조를 기본 탑재하고 있습니다.
// 📂 BST.js (JavaScript)
// 클래스를 활용하여 노드(Node)와 이진 탐색 트리(BST)를 구현합니다.
class Node {
constructor(value) {
this.value = value;
this.left = null;
this.right = null;
}
}
class BinarySearchTree {
constructor() {
this.root = null;
}
// 데이터 삽입
insert(value) {
const newNode = new Node(value);
if (this.root === null) {
this.root = newNode;
return this;
}
let current = this.root;
while (true) {
if (value === current.value) return undefined; // 중복 허용 안함
if (value < current.value) { // 작으면 왼쪽으로
if (current.left === null) {
current.left = newNode;
return this;
}
current = current.left;
} else { // 크면 오른쪽으로
if (current.right === null) {
current.right = newNode;
return this;
}
current = current.right;
}
}
}
// 데이터 탐색 (O(log N))
find(value) {
if (this.root === null) return false;
let current = this.root;
let found = false;
while (current && !found) {
if (value < current.value) {
current = current.left;
} else if (value > current.value) {
current = current.right;
} else {
found = true; // 찾음!
}
}
return found ? current : false;
}
}
// 실행 예시
const tree = new BinarySearchTree();
tree.insert(10);
tree.insert(5);
tree.insert(15);
tree.insert(2);
console.log("트리에서 15 탐색:", tree.find(15)); // Node { value: 15, left: null, right: null }
console.log("트리에서 99 탐색:", tree.find(99)); // false
