자바스크립트로 이진 탐색 트리(BST)에 키 삽입하기: 반복문과 재귀 구현법

새로 생성된 이진 탐색 트리(Binary Search Tree)에 처음으로 값을 삽입하면 해당 노드가 루트(root)에 위치하게 됩니다. 이후의 삽입 연산은 이진 탐색 트리의 기본 성질에 따라 수행됩니다. 즉, 왼쪽 자식 노드는 부모보다 작은 값, 오른쪽 자식 노드는 부모보다 큰 값을 가지도록 배치됩니다.

이번 글에서는 이 알고리즘을 코드로 어떻게 구현할 수 있는지 살펴보겠습니다.

반복문을 사용한 삽입 구현

insertIter(data) {
    let node = new this.Node(data);

    // 트리가 비어 있는지 확인
    if (this.root === null) {
        // 첫 번째 요소로 삽입
        this.root = node; return;
    }

    let currNode = this.root;
    while (true) {
        if (data < currNode.data) {
            // 리프 노드에 도달했으므로 여기에 값 설정
            if (currNode.left === null) {
                currNode.left = node;
                break;
            } else {
                currNode = currNode.left;
            }
        } else {
            // 리프 노드에 도달했으므로 여기에 값 설정
            if (currNode.right === null) {
                currNode.right = node;
                break;
            } else {
                currNode = currNode.right;
            }
        }
    }
}

동작 원리

이 함수의 동작 과정을 단계별로 이해해 보겠습니다.

먼저 루트가 null인지 확인합니다. 루트가 null이라면 트리가 비어 있다는 의미이므로, 새 노드를 루트로 지정하고 종료합니다.

트리가 비어 있지 않다면 currNode 변수를 만들어 루트를 가리키도록 합니다. 그다음 삽입하려는 데이터가 현재 노드의 값보다 작은지 비교합니다.

데이터가 더 작다면 왼쪽 자식을 확인하고, 왼쪽 자식이 null이면 그 자리에 데이터를 저장한 후 반복을 종료합니다.
null이 아니라면 왼쪽 자식으로 이동하여 다시 비교를 반복합니다.
데이터가 같거나 크다면 오른쪽 자식에 대해 동일한 과정을 수행합니다.

이렇게 리프 노드(자식이 없는 노드)에 도달할 때까지 탐색을 반복한 뒤, 마침내 해당 위치에 새 데이터를 삽입하게 됩니다.

반복문 버전 테스트하기

아래와 같이 함수를 직접 호출하여 테스트할 수 있습니다.

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);

재귀를 사용한 삽입 구현

같은 기능을 재귀(recursion) 방식으로도 구현할 수 있습니다. 트리는 본질적으로 재귀적인 구조이기 때문에, 각 노드의 서브트리(subtree) 역시 하나의 트리로 취급할 수 있다는 점을 활용하면 재귀적 구현이 매우 자연스럽습니다.

재귀 버전의 insert 메서드는 다음과 같습니다.

insertRec(data) {
    let node = new this.Node(data);

    // 트리가 비어 있는지 확인
    if (this.root === null) {
        // 첫 번째 요소로 삽입
        this.root = node;
    } else {
        insertRecHelper(this.root, node);
    }
}

여기서는 실제 재귀 호출을 담당하는 헬퍼(helper) 함수가 필요합니다. 다만 이 헬퍼 함수가 클래스의 속성으로 외부에 노출되는 것은 바람직하지 않으므로, 클래스 정의 밖에 일반 함수로 선언하는 것이 좋습니다.

function insertRecHelper(root, node) {
    if (node.data < root.data) {
        // 리프 노드에 도달했으므로 여기에 값 설정
        if (root.left === null) {
            root.left = node;
        } else {
            // 왼쪽 서브트리를 대상으로 재귀 호출
            insertRecHelper(root.left, node);
        }
    } else {
        // 리프 노드에 도달했으므로 여기에 값 설정
        if (root.right === null) {
            root.right = node;
        } else {
            // 오른쪽 서브트리를 대상으로 재귀 호출
            insertRecHelper(root.right, node);
        }
    }
}

재귀 버전 테스트하기

재귀 방식으로 구현된 삽입 함수도 아래와 같이 동일하게 테스트할 수 있습니다.

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);

정리

두 방식 모두 시간 복잡도 측면에서 평균적으로 O(log n)의 성능을 보입니다. 반복문 방식은 스택 오버플로우 위험이 없어 깊은 트리에서 안정적이며, 재귀 방식은 코드가 간결하고 트리의 재귀적 특성을 잘 드러낸다는 장점이 있습니다. 상황에 맞게 적절한 방식을 선택하여 사용하시기 바랍니다.