이진 검색 트리란 무엇인가?
이진 검색 트리(Binary Search Tree, BST)는 특별한 규칙을 따르는 트리 자료구조입니다. 모든 노드는 다음 두 가지 조건을 반드시 만족해야 합니다.
- 왼쪽 자식 노드의 값은 항상 부모 노드의 값보다 작아야 합니다.
- 오른쪽 자식 노드의 값은 항상 부모 노드의 값보다 커야 합니다.
이러한 정렬 규칙 덕분에 이진 검색 트리에서는 값 검색, 삽입, 삭제 작업을 평균적으로 O(log n)의 시간 복잡도로 매우 효율적으로 수행할 수 있습니다. 데이터가 정렬된 상태로 유지되기 때문에 배열보다 빠른 탐색 성능을 기대할 수 있는 것이죠.
이번 섹션에서는 트리 자료구조를 다룰 때 주로 이진 검색 트리를 중심으로 설명하겠습니다.
이진 검색 트리의 주요 연산
이진 검색 트리에서 구현하고 사용하는 대표적인 연산은 다음과 같습니다.
1. 키 삽입 (Insert)
트리에 새로운 키(값)를 추가하는 연산입니다. 루트부터 시작해 값의 크기를 비교하며 왼쪽 또는 오른쪽으로 내려가 적절한 위치에 노드를 배치합니다.
2. 중위 순회 (In-order Traversal)
왼쪽 서브트리 → 루트 → 오른쪽 서브트리 순서로 노드를 방문합니다. 이진 검색 트리를 중위 순회하면 오름차순으로 정렬된 결과를 얻을 수 있다는 점이 특징입니다.
3. 전위 순회 (Pre-order Traversal)
루트 → 왼쪽 서브트리 → 오른쪽 서브트리 순서로 방문합니다. 트리 구조를 복사하거나 직렬화할 때 유용하게 활용됩니다.
4. 후위 순회 (Post-order Traversal)
왼쪽 서브트리 → 오른쪽 서브트리 → 루트 순서로 방문합니다. 자식 노드를 먼저 처리해야 하는 상황, 예를 들어 트리 삭제 작업에 적합합니다.
5. 값 검색 (Search)
특정 값을 찾는 연산입니다. 찾으려는 값과 현재 노드의 값을 비교하여 작으면 왼쪽, 크면 오른쪽으로 이동하기 때문에 탐색 범위가 절반씩 줄어듭니다.
6. 최솟값 탐색 (Minimum)
트리에서 가장 작은 값을 찾습니다. BST의 규칙상 항상 가장 왼쪽 끝에 있는 노드가 최솟값입니다.
7. 최댓값 탐색 (Maximum)
트리에서 가장 큰 값을 찾습니다. 마찬가지로 가장 오른쪽 끝에 있는 노드가 최댓값입니다.
8. 리프 노드 삭제 (Remove Leaf Node)
자식 노드가 없는 리프(leaf) 노드를 트리에서 제거하는 연산입니다. 삭제 연산 중 가장 간단한 형태로, 해당 노드와의 연결만 끊어주면 됩니다.
마무리
이진 검색 트리는 정렬 규칙을 활용해 빠른 검색과 정렬된 데이터 관리를 가능하게 하는 강력한 자료구조입니다. 위에서 소개한 삽입, 순회, 검색, 최솟값·최댓값 탐색, 삭제 연산은 자바스크립트로 BST를 구현할 때 반드시 익혀야 할 핵심 개념이니 차근차근 실습해 보시기 바랍니다.