이진 탐색 트리(Binary Search Tree, BST)는 데이터를 효율적으로 저장하고 검색할 수 있는 자료구조입니다. 이번 글에서는 BinarySearchTree 클래스에 특정 값이 트리 안에 존재하는지 확인하는 contains 메서드를 구현하는 방법을 알아보겠습니다.
구현 원리
BST는 다음과 같은 규칙을 따릅니다.
- 왼쪽 자식 노드는 항상 부모 노드보다 작은 값을 가집니다.
- 오른쪽 자식 노드는 항상 부모 노드보다 큰 값을 가집니다.
이 규칙 덕분에 값을 검색할 때 매 단계마다 탐색 범위가 절반으로 줄어들어, 평균적으로 O(log n)의 시간 복잡도로 빠른 검색이 가능합니다. 검색 로직은 루트 노드부터 시작해 찾고자 하는 값과 현재 노드의 값을 비교하고, 값이 더 작으면 왼쪽으로, 더 크면 오른쪽으로 이동하며 반복합니다. 노드가 더 이상 없으면 해당 값은 트리에 존재하지 않는 것입니다.
예제 코드
아래 코드는 BST의 노드 클래스와 함께 삽입(insert) 및 검색(contains) 기능을 구현한 전체 예제입니다.
// BST의 개별 노드를 위한 클래스
class Node {
constructor(value) {
this.value = value;
this.left = null;
this.right = null;
}
}
// BST 클래스 - 노드 삽입 및 검색 기능 포함
class BinarySearchTree {
constructor() {
this._root = null;
}
// 새로운 값 삽입 (중복 값은 무시)
insert(value) {
let node = this, side = '_root';
while (node[side]) {
node = node[side];
if (value === node.value) {
return; // 중복 값은 삽입하지 않음
}
side = value < node.value ? 'left' : 'right';
}
node[side] = new Node(value);
}
// 특정 값이 트리에 존재하는지 확인
contains(value) {
let current = this._root;
while (current) {
if (value === current.value) {
return true; // 값을 찾음
}
current = value < current.value ? current.left : current.right;
}
return false; // 끝까지 못 찾으면 false 반환
}
}
// 사용 예시
const tree = new BinarySearchTree();
for (let i = 0; i < 10; i++) {
tree.insert(Math.floor(Math.random() * 1000)); // 무작위 값 10개 삽입
}
tree.insert(34);
console.log(tree.contains(34)); // true 출력
console.log(tree.contains(334)); // false 출력실행 결과
위 코드를 실행하면 콘솔에 다음과 같은 결과가 출력됩니다.
true false
동작 설명
tree.insert(34)를 통해 값 34를 트리에 추가했기 때문에 contains(34)는 true를 반환합니다. 반면 값 334는 트리에 삽입된 적이 없으므로 contains(334)는 false를 반환합니다.
마무리
이처럼 contains 메서드는 반복문을 활용해 간단하게 구현할 수 있습니다. 재귀 함수를 사용하는 방식도 가능하지만, 반복문 방식은 호출 스택을 사용하지 않아 깊은 트리에서도 스택 오버플로우 걱정 없이 안전하게 동작한다는 장점이 있습니다. BST의 검색뿐 아니라 삭제, 순회 등 다른 연산도 같은 원리로 확장해볼 수 있으니 직접 구현해 보시길 추천합니다.