JavaScript

木構造（ツリー）を構成する個々の要素は「ノード」と呼ばれます。二分木はノードの集合体であるため、二分木を定義する前に、まずノードそのものを定義する必要があります。ここでは、left・right・data という3つのプロパティを持つ、シンプルなノード定義を作成していきましょう。それぞれのプロパティの役割は以下のとおりです。left ― このノードの左の子ノードへの参照を保持します。right ― このノードの右の子ノードへの参照を保持します。data ― このノードに格納したいデータへの参照を保持します。ノード構造のコード例それでは、このような構造をコードで表現してみましょう。class No

この記事では、JavaScriptで二分探索木（Binary Search Tree）を作成し、表現する方法を解説します。まずは BinarySearchTree クラスを作成し、そのクラスに Node プロパティを定義するところから始めましょう。二分探索木とは二分探索木（BST）は、各ノードが最大2つの子ノードを持つデータ構造です。「左の子ノードには親より小さい値、右の子ノードには親より大きい値を格納する」というルールに従うことで、高速な検索・挿入・削除を実現できます。実装例class BinarySearchTree { constructor() { // ルート

二分木への挿入の基本新しく作成した二分木への最初の挿入では、ノードがルートとして配置されます。2回目以降の挿入では、二分探索木（BST）の特性に従ってノードが配置されます。つまり、左の子は親より小さい値、右の子は親より大きい値を持つというルールです。ここでは、このアルゴリズムをコードで実装する方法を、反復（イテレーティブ）と再帰の2つのアプローチで解説します。反復版の挿入メソッドinsertIter(data) {     let node = new this.Node(data);     // ツリーが空か

二分探索木（Binary Search Tree：BST）の最大の特徴は、「左の子は親より小さく、右の子は親より大きい」という値の順序が保たれている点です。この性質を利用すると、要素を非常に効率よく検索できます。まずは、反復処理（ループ）を使った検索の実装から見ていきましょう。反復版の実装searchIter(data) {    let currNode = this.root;    while (currNode !== null) {       if (currNo

二分探索木（Binary Search Tree：BST）には「左の子は必ず親より小さい」という重要な性質があります。この性質に注目すると、左の子が存在しなくなるまで左へ辿り続ければ、BST内の最小値のノードにたどり着くことが分かります。同様に、「右の子は必ず親より大きい」という性質から、右端まで辿れば最大値が見つかることも理解できます。それでは、実際にコードでこの機能を実装してみましょう。ここからは関数を反復処理版または再帰版のどちらか一方のみ実装していきます。今回は反復処理を使った関数を作成します。getMinVal() の実装例getMinVal() {   &nbs

辞書（ディクショナリ）型のデータを扱っていると、ある処理のために「キーだけ」を配列として取り出したい場面があります。JavaScriptでは、Object.keysメソッドを使うことで、オブジェクトが持つプロパティ（キー）を簡単に配列形式で取得できます。ここでは、このメソッドを利用して、独自のコンテナオブジェクトからキーの一覧を返す実装を見ていきましょう。 keys()メソッドの実装例 keys() {     return Object.keys(this.container); } 動作確認 実際に動作を確認してみます。 const myMap =

JavaScriptで辞書（連想配列）の中身を一括で空にしたい場面は多くあります。本記事では、自作のMapクラスにclear()メソッドを実装する方法と、ES6で標準搭載されたMapオブジェクトのclear()メソッドの使い方を、コード例とともにわかりやすく解説します。 カスタムMapクラスにclear()を実装する まずは、コンテナ（内部データ）の内容をすべて消去するclear()関数を実装してみましょう。考え方は非常にシンプルで、データを格納しているコンテナに新しい空のオブジェクトを代入し直すだけです。 実装例 clear() { this.container = {} }

はじめに JavaScriptでは、辞書（キーと値のペアを管理するデータ構造）の中身を順番に処理したい場面がよくあります。ここでは、独自の辞書クラスにforEach関数を実装し、すべてのキーと値のペアに対して呼び出されるコールバック関数を受け取れるようにする方法を紹介します。 自作クラスでのforEach実装例 まずは、クラス内にforEachメソッドを実装してみましょう。for...inループでコンテナ内の各プロパティを走査し、キーと値を引数としてコールバックに渡します。 forEach(callback) { for (let prop in this.container) {

辞書（Dictionary）は、キーと値のペアを格納するための基本的なデータ構造です。JavaScriptには標準でMapオブジェクトが用意されていますが、独自の辞書クラスを実装することで、内部の仕組みを深く理解でき、動作を自由にカスタマイズすることも可能になります。ここでは、プレーンなオブジェクトを内部コンテナとして利用した、MyMapクラスの完全な実装を紹介します。MyMapクラスの完全な実装以下がMyMapクラスの完全な実装コードです。class MyMap { constructor() { this.container = {}; } disp

ハッシュテーブル（Hash Table）は、データを連想形式で格納するデータ構造です。ハッシュテーブルでは、データは配列形式で保持され、それぞれのデータ値に固有のインデックス値が割り当てられます。目的のデータのインデックスさえ分かれば、データへのアクセスは非常に高速に行えます。そのため、ハッシュテーブルはデータサイズの大小にかかわらず、挿入操作も検索操作も非常に高速に実行できるデータ構造となっています。ハッシュテーブルは配列を記憶領域として利用し、要素を挿入または検索すべきインデックスを生成するために「ハッシュ」という技法を用います。ハッシュ化（Hashing）とはハッシュ化とは、キー値の範囲

まず、各種メソッドを定義するためのシンプルなクラスを用意しましょう。ハッシュテーブル本体を格納するコンテナオブジェクトを作成し、テーブルの内容を出力するための display 関数も一緒に実装していきます。なお、キーの衝突(コリジョン)が発生した場合の対処には、「チェイニング」と呼ばれる手法を採用します。チェイニングでは、同じハッシュ値を持つ複数の要素を連結リスト(配列)として同じスロットに格納できるため、衝突が起きてもデータを失うことなく管理できます。クラスの基本構造display 関数は、テーブル内の各エントリ(ハッシュ値)を順番に取り出し、そのスロットに関連付けられているすべてのキーと値

ハッシュテーブルへ要素を追加する際に最も重要なのが「衝突（コリジョン）」の解決です。本記事では、チェイン法（Chaining／連鎖法）と呼ばれる手法を使って衝突を処理する方法を解説します。チェイン法以外にも、オープンアドレス法などさまざまな衝突解決アルゴリズムが存在します。興味のある方は Wikipedia の Hash table ページを参考にしてください。ハッシュテーブルへの要素追加の実装ここでは説明をシンプルにするため、整数のみを対象とするハッシュ関数を作成します。より複雑なハッシュアルゴリズムを採用すれば、任意のオブジェクトをキーとしてハッシュ化することも可能です。以下は、キーと値の

getメソッドの実装実は、要素の検索処理はすでにputメソッドの中である程度実装されています。ここでは、そのロジックを独立したgetメソッドとして切り出し、あらためて詳しく見ていきましょう。サンプルコードget(key) { let hashCode = hash(key); for(let i = 0; i < this.container[hashCode].length; i ++) { // チェーン内から該当する要素を探す if(this.container[hashCode][i].key === key) {

ハッシュテーブルから要素を削除するには、該当するキーを探し出し、配列からその場で要素を取り除ける splice メソッドを呼び出すだけで実現できます。削除処理は以下の手順で行われます。hash 関数を使って、キーからハッシュ値(バケットのインデックス)を計算します。該当するバケット内のチェーン(連結されたエントリのリスト)を順番に走査します。同じキーを持つ要素が見つかったら、splice(i, 1) を呼び出してその位置の要素を1つ削除し、true を返します。見つからなかった場合は、何も削除せずに false を返します。実装例それでは、実際のコードを見てみましょう。remove(key)

ここでは、ハッシュテーブルに格納されているすべてのキーと値のペアを走査し、それぞれの値に対してコールバック関数を実行できる forEach メソッドを作成します。実装の考え方はシンプルです。ハッシュテーブル内部のコンテナには、衝突した要素が「チェーン」と呼ばれるリストで格納されています。そのため、コンテナ内の各チェーンを外側のループでたどり、さらに各チェーン内の要素に対して分割代入で key と value を取り出しながらコールバックを呼び出せばよいのです。forEachメソッドの実装例forEach(callback) { // コンテナ内の各チェーンをループ this.c

clearメソッドの実装は非常にシンプルです。セットの中身を空にしたい場合は、container変数に新しい空のオブジェクトを再代入するだけで対応できます。これにより、それまで格納されていた要素はすべて破棄され、セットが初期状態になります。 実装例 clear() {    this.container = {}; } このメソッドが正しく動作するかどうかは、以下のようなコードで確認できます。まず要素をいくつか追加して表示し、その後にclear()を呼び出して再度表示してみましょう。 テストコード const testSet = new MySet(); testSet.

自作のセット（Set）クラスでは、クラス内に forEach 関数を作成し、各要素に対して呼び出されるコールバック関数を受け取ることができます。ここでは、そのような関数をどのように実装するのかを見ていきましょう。実装例forEach(callback) {     for (let prop in this.container) {         callback(prop);     } }この関数は、以下のようにして動作を確認でき

2つのセットを追加する操作は「和集合（ユニオン）」と呼ばれます。これは、片方のセットに含まれるすべての要素を新しいセットに追加しながら、重複を排除していく処理です。すでに実装済みのメソッドを組み合わせれば、この操作は簡単に実現できます。既存のセットを変更（ミューテート）せず、新しいセットを作成して返す設計とするため、この関数は静的メソッドとして実装します。まず最初に、引数として渡されたオブジェクトが本当にMySetクラスのインスタンスであるかを検証しましょう。実装例static union(s1, s2) { if (!(s1 instanceof MySet) || !(s2 insta

2つのセットの差集合とは、引かれる側のセットから、引く側のセットに含まれるすべての要素を取り除いた結果のことです。この操作を実現するには、2番目のセットを走査しながら、その中に存在する要素を1番目のセットからすべて削除していきます。 カスタムSetクラスでの実装例 static difference(s1, s2) {    if (!s1 instanceof MySet || !s2 instanceof MySet) {       console.log("指定されたオブジェクトはMySet型ではありません");

セット(Set)は、重複しない値のコレクションを扱うための基本的なデータ構造です。JavaScriptには標準で組み込みのSetオブジェクトが用意されていますが、その内部動作を理解するには、独自のMySetクラスをゼロから実装してみるのが効果的です。 以下は、基本操作(追加・削除・検索・クリア)、反復処理、そして和集合と差集合を求める静的メソッドまでを含んだ、MySetクラスの完全な実装例です。 MySetクラスの実装例 class MySet { constructor() { this.container = {}; } display() {