자바스크립트로 구현하는 이진 탐색 트리(Binary Search Tree) 클래스 완벽 가이드

이진 탐색 트리(Binary Search Tree, BST)는 각 노드가 최대 두 개의 자식을 가지며, 왼쪽 자식은 부모보다 작은 값, 오른쪽 자식은 부모보다 큰 값을 저장하는 자료구조입니다. 이러한 규칙 덕분에 데이터 검색, 삽입, 삭제를 평균적으로 O(log n)의 시간 복잡도로 처리할 수 있어 정렬된 데이터를 다룰 때 매우 유용합니다.

이번 글에서는 자바스크립트로 이진 탐색 트리 클래스를 직접 구현해 보겠습니다. 반복문 기반 방식과 재귀 기반 방식을 모두 다루며, 삽입·검색·최솟값/최댓값 조회·노드 삭제·순회(traversal)까지 전체 기능을 포함한 완전한 코드를 소개합니다.

BinarySearchTree 클래스 전체 구현

아래는 이진 탐색 트리의 모든 핵심 기능을 담은 완전한 구현 코드입니다.

class BinarySearchTree {
    constructor() {
        // 루트 노드를 null로 초기화합니다.
        this.root = null;
    }
    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;
                }
            }
        }
    }
    insertRec(data) {
        let node = new this.Node(data);

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

        while (currNode !== null) {
            if (currNode.data === data) {
                // 요소를 찾았습니다!
                return true;
            } else if (data < currNode.data) {
                // 데이터가 부모보다 작으므로 왼쪽으로 이동
                currNode = currNode.left;
            } else {
                // 데이터가 부모보다 크므로 오른쪽으로 이동
                currNode = currNode.right;
            }
        }
        return false;
    }
    searchRec(data) {
        return searchRecHelper(data, this.root);
    }
    getMinVal() {
        if (this.root === null) {
            throw "Empty tree!";
        }
        let currNode = this.root;

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

        while (currNode.right !== null) {
            currNode = currNode.right;
        }
        return currNode.data;
    }
    deleteNode(key) {
        return !(deleteNodeHelper(this.root, key) === false);
    }
    inOrder() {
        inOrderHelper(this.root);
    }
    preOrder() {
        preOrderHelper(this.root);
    }
    postOrder() {
        postOrderHelper(this.root);
    }
}

BinarySearchTree.prototype.Node = class {
    constructor(data, left = null, right = null) {
        this.data = data;
        this.left = left;
        this.right = right;
    }
};

헬퍼(Helper) 메서드 구현

클래스 내부에서 호출되는 순회 함수와 재귀 헬퍼 함수들은 아래와 같이 프로토타입 외부에 일반 함수로 정의합니다.

순회(Traversal) 메서드

트리 순회에는 세 가지 방식이 있습니다. 전위 순회(pre-order)는 루트 → 왼쪽 → 오른쪽 순서로, 중위 순회(in-order)는 왼쪽 → 루트 → 오른쪽 순서로, 후위 순회(post-order)는 왼쪽 → 오른쪽 → 루트 순서로 노드를 방문합니다. 특히 중위 순회는 BST에서 오름차순으로 정렬된 결과를 얻을 수 있다는 점이 특징입니다.

// 헬퍼 메서드
function preOrderHelper(root) {
    if (root !== null) {
        console.log(root.data);
        preOrderHelper(root.left);
        preOrderHelper(root.right);
    }
}
function inOrderHelper(root) {
    if (root !== null) {
        inOrderHelper(root.left);
        console.log(root.data);
        inOrderHelper(root.right);
    }
}

function postOrderHelper(root) {
    if (root !== null) {
        postOrderHelper(root.left);
        postOrderHelper(root.right);
        console.log(root.data);
    }
}

재귀 삽입 및 재귀 검색

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

function searchRecHelper(data, root) {
    if (root === null) {
        // 리프에 도달했지만 찾지 못했습니다.
        return false;
    }
    if (data < root.data) {
        return searchRecHelper(data, root.left);
    } else if (data > root.data) {
        return searchRecHelper(data, root.right);
    }
    // 요소를 찾은 경우
    return true;
}

노드 삭제 로직 상세 설명

노드 삭제는 BST 구현에서 가장 까다로운 부분입니다. 삭제하려는 노드의 위치와 자식 수에 따라 세 가지 경우로 나눌 수 있습니다.

경우 1: 리프 노드(자식 없음)

예를 들어 F를 삭제하는 경우를 살펴보겠습니다.

A
/ \
B C
/ / \
D E F

F는 리프 노드이므로 단순히 부모 노드와의 연결만 끊어주면 됩니다.

A
/ \
B C
/ /
D E

경우 2: 자식이 하나인 중간 노드

예를 들어 B를 삭제하는 경우입니다.

A
/ \
B C
/ / \
D E F

B의 자식 D가 B의 위치를 대체하도록 연결만 변경해 주면 됩니다.

A
/ \
D C
/ \
E F

경우 3: 자식이 둘인 노드 (가장 복잡한 경우)

예를 들어 C를 삭제하는 경우입니다.

A
/ \
B C
/ / \
D E F
/ / \
G H I

이 경우에는 해당 노드의 후속자(successor) 또는 선행자(predecessor)를 찾아 그 값으로 대체해야 합니다. 후속자를 사용한다면, 후속자는 해당 노드보다 바로 큰 값, 즉 오른쪽 서브트리에서 가장 작은 값이 됩니다. C를 삭제한 후 트리는 다음과 같이 됩니다.

A
/ \
B H
/ / \
D E F
/ \
G I

후속자를 제거하려면 후속자의 부모를 찾아 연결을 끊고, 후속자의 왼쪽·오른쪽 참조를 현재 노드의 것으로 연결해야 합니다. 더 간단한 방법은 삭제할 노드의 데이터를 후속자의 값으로 교체한 뒤, 후속자 노드만 삭제하는 것입니다.

deleteNodeHelper 구현

/**
* 루트와 키를 받아 재귀적으로 키를 검색합니다.
* 키를 찾으면 다음 3가지 경우가 발생할 수 있습니다:
*
* 1. 해당 노드가 리프 노드인 경우 → 부모와의 연결을 제거
* 2. 자식이 하나인 경우 → 자식 노드가 부모의 위치를 대체
* 3. 자식이 둘인 경우 → 후속자(오른쪽 서브트리의 최솟값)로 대체 후 후속자 삭제
*/
function deleteNodeHelper(root, key) {
    if (root === null) {
        // 빈 트리
        return false;
    }

    if (key < root.data) {
        root.left = deleteNodeHelper(root.left, key);
        return root;
    } else if (key > root.data) {
        root.right = deleteNodeHelper(root.right, key);
        return root;
    } else {
        // 자식이 없는 경우
        // 케이스 1 - 리프 노드
        if (root.left === null && root.right === null) {
            root = null;
            return root;
        }

        // 자식이 하나인 경우들
        if (root.left === null) return root.right;
        if (root.right === null) return root.left;

        // 자식이 둘이므로 후속자를 찾아야 함
        let currNode = root.right;

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

        // 오른쪽 서브트리에서 해당 값을 삭제
        root.right = deleteNodeHelper(root.right, currNode.data);
        return root;
    }
}

마무리

이렇게 자바스크립트로 이진 탐색 트리의 핵심 연산인 삽입(insert), 검색(search), 최솟값/최댓값 조회(getMinVal/getMaxVal), 삭제(deleteNode), 그리고 세 가지 순회 방식까지 모두 구현해 보았습니다. 반복(iterative) 방식은 스택 오버플로 걱정 없이 동작하고, 재귀(recursive) 방식은 코드가 간결하다는 장점이 있으니 상황에 맞게 선택하여 사용하시기 바랍니다. 이 구현을 바탕으로 AVL 트리나 레드-블랙 트리 같은 자가 균형 트리로 확장해 보는 것도 좋은 학습 과제가 될 것입니다.