JavaScriptで二分探索木（BST）の最頻値（モード）を求める方法

本記事では、JavaScriptを使って二分探索木（Binary Search Tree、BST）に格納されたデータから「モード（最頻値）」を求める方法を解説します。

モード（最頻値）とは？

モード（最頻値）とは、一連のデータの中で最も多く出現する数値のことです。
例えば、次のデータセットを見てみましょう。

2, 3, 1, 3, 4, 2, 3, 1

この中で「3」は合計3回出現しており、他のどの数値よりも多く登場します。したがって、このデータセットのモードは「3」となります。

二分探索木（BST）とは？

ある木構造のデータ構造が「有効な二分探索木」であると認められるには、以下の条件をすべて満たす必要があります。

• 各ノードの左側の部分木には、そのノードのキー以下の値を持つノードのみが含まれる。
• 各ノードの右側の部分木には、そのノードのキー以上の値を持つノードのみが含まれる。
• 左右それぞれの部分木もまた、二分探索木として成立していなければならない。

課題：BST内の最頻値を見つける

ここで求められているのは、二分探索木のルート（根）ノードを唯一の引数として受け取るJavaScript関数を記述することです。与えられるBSTには重複した値が含まれている可能性があり、実際にはほぼ含まれている前提で考えます。私たちのタスクは、ツリー全体に格納されたデータからモードを特定し、それを返すことです。

コード例

実際のコードは以下の通りです。

class Node {
   constructor(data) {
      this.data = data;
      this.left = null;
      this.right = null;
   };
};
class BinarySearchTree {
   constructor() {
      // 二分探索木のルート
      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));

実行結果

コンソールに出力される結果は次の通りです。

3

コードの解説

このアルゴリズムの流れを簡単に整理してみましょう。

1. 走査（トラバース）： traverse 関数が深さ優先探索（DFS）で全ノードを訪問し、各値の出現回数をハッシュオブジェクト（連想配列）に記録していきます。
2. 最大出現回数の追跡： 値が出現するたびにカウントを更新し、Math.max を使ってこれまでの最大出現回数 max を常に保持します。
3. 結果の抽出： 走査完了後、ハッシュオブジェクトを走査し、出現回数が max と一致するキーだけを結果配列に集めます。
4. 戻り値： 結果の先頭要素を数値化（単項プラス + 演算子）して返します。

今回の例では、挿入した値「3」が3回出現して最も多いため、findMode(BST.root) の結果として 3 が出力されます。なお、複数の値が同じ最大回数で並んだ場合は、最初に検出された値が返される点に注意してください。