JavaScript 이진 탐색 트리(BST)에서 최빈값 찾는 방법

최빈값(Mode)이란?

최빈값은 데이터 집합에서 가장 많이 등장하는 숫자를 의미합니다. 예를 들어, 데이터셋 [2, 3, 1, 3, 4, 2, 3, 1]에서 3은 세 번 등장하여 다른 어떤 수보다 많이 나타나므로 이 데이터셋의 최빈값은 3입니다.

이진 탐색 트리(Binary Search Tree)

트리 자료구조가 다음 조건을 모두 충족하면 유효한 이진 탐색 트리라고 할 수 있습니다.

노드의 왼쪽 서브트리에는 해당 노드의 키보다 작거나 같은 키를 가진 노드만 존재합니다.
노드의 오른쪽 서브트리에는 해당 노드의 키보다 크거나 같은 키를 가진 노드만 존재합니다.
왼쪽과 오른쪽 서브트리 역시 각각 이진 탐색 트리여야 합니다.

문제 정의

이진 탐색 트리(BST)의 루트 노드를 유일한 인수로 받는 JavaScript 함수를 작성해야 합니다. 이 BST에는 중복된 값이 포함될 수 있으며, 실제로 대부분의 경우 중복 값이 존재합니다. 따라서 목표는 트리에 저장된 데이터 중 가장 자주 등장하는 값, 즉 최빈값을 찾아 반환하는 것입니다.

구현 예제

문제를 해결하는 전체 코드는 다음과 같습니다.

class Node{
    constructor(data) {
        this.data = data;
        this.left = null;
        this.right = null;
    };
};
class BinarySearchTree{
    constructor(){
        // root of a binary search tree
        this.root = null;
    }
    insert(data){
        var newNode = new Node(data);
        if(this.root === null){
            this.root = newNode;
        }else{
            this.insertNode(this.root, newNode);
        };
    };
    insertNode(node, newNode){
        if(newNode.data < node.data){
            if(node.left === null){
                node.left = newNode;
            }else{
                this.insertNode(node.left, newNode);
            };
        } else {
            if(node.right === null){
                node.right = newNode;
            }else{
                this.insertNode(node.right,newNode);
            };
        };
    };
};
const BST = new BinarySearchTree();
BST.insert(1);
BST.insert(3);
BST.insert(3);
BST.insert(2);
BST.insert(3);
BST.insert(2);
const findMode = function(root) {
    let max = 1;
    const hash = {};
    const result = [];
    const traverse = node => {
        if (hash[node.data]) {
            hash[node.data] += 1;
            max = Math.max(max, hash[node.data]);
        } else {
            hash[node.data] = 1;
        };
        node.left && traverse(node.left);
        node.right && traverse(node.right);
    };
    if(root){
        traverse(root);
    };
    for(const key in hash) {
        hash[key] === max && result.push(key);
    };
    return +result[0];
};
console.log(findMode(BST.root));

알고리즘 동작 원리

위 코드의 핵심 로직은 다음과 같이 요약할 수 있습니다.

트리 순회: 재귀 함수 traverse를 사용해 트리의 모든 노드를 방문합니다.
빈도 집계: 해시 객체(hash)에 각 값의 등장 횟수를 기록합니다.
최대 빈도 추적: max 변수에 지금까지 나타난 최대 등장 횟수를 계속 갱신하며 저장합니다.
결과 도출: 순회가 끝나면 빈도가 max와 일치하는 값을 골라 반환합니다.

이 방식은 트리를 단 한 번만 순회하면 되기 때문에 시간 복잡도는 O(n)이며, 해시 맵에 사용되는 추가 공간 복잡도 역시 O(n)입니다.

실행 결과

위 코드를 실행하면 콘솔에 다음과 같이 출력됩니다.