자바스크립트 이진 탐색 트리(BST)에서 값 검색하기

이진 탐색 트리(Binary Search Tree, BST)는 각 노드를 기준으로 왼쪽 자식에는 더 작은 값, 오른쪽 자식에는 더 큰 값이 위치한다는 핵심 속성을 가지고 있습니다. 이 속성을 활용하면 트리 안에서 원하는 값을 매우 효율적으로 찾을 수 있습니다. 먼저 반복문(iteration)을 사용하는 검색 구현부터 살펴보겠습니다.

반복문을 사용한 검색 구현

searchIter(data) {
    let currNode = this.root;
    while (currNode !== null) {
        if (currNode.data === data) {
            // Found the element!
            return true;
        } else if (data < currNode.data) {
            // Go Left as data is smaller than parent
            currNode = currNode.left;
        } else {
            // Go right as data is greater than parent
            currNode = currNode.right;
        }
    }
    return false;
}

이 함수는 루트 노드를 시작점(currNode)으로 삼아, 찾고자 하는 데이터와 현재 노드의 데이터를 비교합니다. 두 값이 일치하면 true를 반환하고, 일치하지 않으면 비교 결과에 따라 왼쪽 또는 오른쪽 자식 노드로 이동하며 탐색을 계속합니다. 이 과정은 원하는 요소를 찾거나 리프 노드(자식이 없는 노드)에 도달할 때까지 반복되며, 끝까지 찾지 못하면 false를 반환합니다.

다음과 같이 실제 동작을 확인할 수 있습니다.

사용 예제

let BST = new BinarySearchTree();
BST.insertIter(10);
BST.insertIter(15);
BST.insertIter(5);
BST.insertIter(50);
BST.insertIter(3);
BST.insertIter(7);
BST.insertIter(12);

console.log(BST.searchIter(2));
console.log(BST.searchIter(12));
console.log(BST.searchIter(50));
console.log(BST.searchIter(-22));
console.log(BST.searchIter(200));

실행 결과

위 코드를 실행하면 다음과 같은 출력을 얻습니다.

false
true
true
false
false

삽입(insert) 함수와 마찬가지로, 검색 역시 재귀(recursion) 방식으로 구현할 수 있습니다.

searchRec(data) {
    return searchRecHelper(data, this.root);
}

재귀 구현에는 클래스에 포함시키지 않을 별도의 헬퍼(helper) 함수가 필요합니다. 따라서 이 함수는 클래스 정의 외부에 다음과 같이 작성합니다.

재귀 헬퍼 함수 구현

function searchRecHelper(data, root) {
    if (root === null) {
        // Reached leaf but didn't find it.
        return false;
    }
    if (data < root.data) {
        return searchRecHelper(data, root.left);
    } else if (data > root.data) {
        return searchRecHelper(data, root.right);
    }
    // This means element is found
    return true;
}

헬퍼 함수는 현재 노드가 null일 때 false를 반환하여 탐색의 종료 조건을 처리합니다. 찾는 값이 현재 노드의 값보다 작으면 왼쪽 서브트리로, 크면 오른쪽 서브트리로 재귀 호출을 이어가며, 어느 조건에도 해당하지 않으면 요소를 찾은 것이므로 true를 반환합니다.

재귀 버전 역시 다음과 같이 테스트할 수 있습니다.

사용 예제

let BST = new BinarySearchTree();
BST.insertRec(10);
BST.insertRec(15);
BST.insertRec(5);
BST.insertRec(50);
BST.insertRec(3);
BST.insertRec(7);
BST.insertRec(12);

console.log(BST.searchRec(2));
console.log(BST.searchRec(12));
console.log(BST.searchRec(50));
console.log(BST.searchRec(-22));
console.log(BST.searchRec(200));

실행 결과

위 코드를 실행하면 다음과 같은 출력을 얻습니다.

false
true
true
false
false

두 구현 방식 모두 균형 잡힌 BST에서 시간 복잡도는 O(log n)입니다. 매 단계마다 탐색 범위가 절반으로 줄어들기 때문입니다. 다만 트리가 한쪽으로 치우친 편향 트리(skewed tree) 형태라면 최악의 경우 O(n)까지 성능이 저하될 수 있다는 점을 유의해야 합니다.