자바스크립트 이진 탐색 트리에서 최솟값과 최댓값 찾기

이진 탐색 트리(Binary Search Tree, BST)는 왼쪽 자식 노드가 항상 부모 노드보다 작다는 핵심 성질을 가지고 있습니다. 이 성질을 활용하면 루트에서 출발해 왼쪽 자식을 따라 계속 이동하고, 더 이상 왼쪽 자식이 없는 노드에 도달했을 때 그 노드의 값이 곧 트리 전체에서 가장 작은 값임을 알 수 있습니다.

이제 이 로직을 실제 코드로 구현해 보겠습니다. 앞으로 진행되는 예제에서는 함수를 반복(iterative) 방식 또는 재귀(recursive) 방식 중 한 가지로만 구현합니다. 여기서는 반복문을 사용하는 방식으로 작성해 보겠습니다.

getMinVal() 구현 예제

getMinVal() {
    if (this.root === null) {
        throw "Empty tree!";
    }
    let currNode = this.root;

    while (currNode.left !== null) {
        currNode = currNode.left;
    }
    return currNode.data;
}

먼저 트리가 비어 있는 경우 예외를 발생시켜 잘못된 접근을 방지하고, 이후 루트 노드부터 시작해 왼쪽 자식이 존재하지 않을 때까지 계속 왼쪽으로 이동한 뒤 해당 노드의 데이터를 반환하는 구조입니다.

작성한 함수는 다음과 같이 테스트할 수 있습니다.

테스트 코드

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.getMinVal());

출력 결과

위 코드를 실행하면 다음과 같은 결과가 출력됩니다.

3

삽입된 값 중 가장 작은 값인 3이 정상적으로 반환된 것을 확인할 수 있습니다.

같은 원리를 반대로 적용하면 최댓값도 손쉽게 구할 수 있습니다. BST에서는 오른쪽 자식 노드가 항상 부모 노드보다 크므로, 오른쪽 자식을 따라 끝까지 이동하면 그 노드가 트리에서 가장 큰 값이 됩니다. 이를 활용한 getMaxVal() 함수의 구현 코드는 다음과 같습니다.

getMaxVal() 구현 예제

getMaxVal() {
    if (this.root === null) {
        throw "Empty tree!";
    }
    let currNode = this.root;

    while (currNode.right !== null) {
        currNode = currNode.right;
    }
    return currNode.data;
}

두 함수 모두 트리의 높이(h)에 비례하는 시간 복잡도 O(h)로 동작합니다. 트리의 균형이 잘 잡혀 있다면 O(log n)에 가깝게 빠르게 동작하지만, 편향된 트리의 경우 최악에는 O(n)까지 느려질 수 있다는 점을 참고하시기 바랍니다.