JavaScript

深さ優先探索（DFS：Depth-First Search）は、兄弟ノード（同一階層の頂点）よりも先に子ノードを訪問するグラフ探索アルゴリズムです。つまり、探索範囲の「幅」を広げる前に、まず特定のパスの「深さ」を最後までたどるのが特徴です。DFSを実装する際には、スタック（再帰を利用する場合はプログラムのコールスタック）が一般的に使われます。DFSの動作手順隣接する未訪問の頂点を訪問し、訪問済みとしてマークします。表示したうえで、スタックにプッシュします。隣接する未訪問の頂点が見つからない場合は、スタックから頂点をポップします（隣接する未訪問頂点を持たない頂点がすべてポップされていきます）。ス

トポロジカルソートとはトポロジカルソート（トポロジカル順序付け）とは、有向グラフのすべての頂点を線形に並べる手法です。頂点 u から頂点 v へ向かう有向辺 UV が存在する場合、必ず u が v より先に現れるように並べます。この概念が意味を持つのは、有向グラフの場合のみです。トポロジカルソートは、実際のさまざまな場面で活用されています。例えば料理のレシピでは、次の工程に進む前に必ず完了しておくべきステップがある一方で、並行して行える作業も存在します。また、大学の履修登録でも同じ考え方が使えます。発展的な科目を受講するには前提科目が必要であり、その前提科目自体がさらに別の科目の前提となってい

グラフ理論における最短経路問題とは、グラフ上の2つの頂点（ノード）をつなぐ経路の中から、構成するエッジ（辺）の重みの合計が最小となるものを見つける問題です。このアルゴリズムを実装するためには、既存のaddEdgeメソッドとaddDirectedEdgeメソッドを修正し、エッジに重みを設定できるように拡張する必要があります。 重み付きエッジを追加する実装例 それでは、実際にどのように重みを扱えるようにするのか、コードを見ていきましょう。 /** * 同じ重みを持つ双方向のエッジを追加します * * weight * node1 <===============

ダイクストラ法（Dijkstras algorithm）は、重み付きグラフにおけるノード間の最短経路を求めるための代表的なアルゴリズムです。グラフを作成する際に addEdge や addDirectedEdge のメソッドを使えば、エッジに重みを設定できます。ここでは、このアルゴリズムがどのように動作するのかを順番に見ていきましょう。ダイクストラ法の基本的な流れ距離を格納するコレクションを作成し、始点ノード以外のすべての頂点の距離を無限大（Infinity）に設定します。始点ノードの距離は 0 なので、優先度 0 として最小優先度キュー（min-priority queue）にエンキューしま

全点対最短経路問題とはダイクストラ法（Dijkstras algorithm）は、ある1つのノードから他のすべてのノードへの最短距離・経路を求めるためのアルゴリズムです。しかし、実務では「すべてのノードから、それ以外のすべてのノードへの最短経路」をまとめて求めたいケースがあります。こうした問題に活躍するのが全点対最短経路（All Pairs Shortest Path）アルゴリズムであり、その中で最も広く利用されているのがワーシャル・フロイド法（Floyd-Warshall algorithm）です。ワーシャル・フロイド法の仕組みワーシャル・フロイド法は、以下の手順で動作します。N × N の

木構造の走査（ツリートラバーサル）とは木構造の走査（ツリートラバーサル）とは、ツリー（木）データ構造に含まれる各ノードを、正確に一度ずつ訪問する処理のことを指します。ツリーは階層的なデータ構造であるため、配列のような線形構造とは異なり、どの順序でノードを辿るかが重要な設計要素となります。この走査順序によって、トラバーサルはいくつかの種類に分類されます。主な走査方法の種類木構造の走査は、大きく「深さ優先探索（DFS）」と「幅優先探索（BFS）」の2つに分けられます。深さ優先探索（DFS）深さ優先探索は、あるノードから出発して子孫方向へできる限り深く進み、行き止まりに達したら戻りながら次の経路を探

通りがけ順走査（In-order Traversal）とは通りがけ順走査は、木構造の走査方法のひとつで、左部分木 → 根（ルート） → 右部分木 の順にノードを訪問します。ここで重要なのは、すべてのノードがそれ自体ひとつの部分木とみなせるという点です。つまり、各ノードに対して同じルールを再帰的に適用していくことになります。二分探索木（BST）を通りがけ順で走査すると、キーの値が昇順にソートされた状態で出力されるという特徴があります。これは二分探索木の非常に便利な性質のひとつです。走査の流れまず A から出発し、通りがけ順のルールに従って左部分木の B へ移動します。B に対しても同様に通りがけ

先行順走査（Pre-order Traversal）は、二分木を巡回する代表的な手法のひとつです。この走査方法では、まずルートノードを訪問し、次に左部分木、最後に右部分木の順で処理を行います。先行順走査の流れ具体的な動きを見てみましょう。まず A から開始し、先行順走査に従って最初に A 自身を訪問します。その後、左部分木である B へ移動します。B も同様に先行順で走査され、この処理はすべてのノードを訪問するまで繰り返されます。この木に対する先行順走査の結果は以下のようになります。A → B → D → E → C → F → Gアルゴリズムの手順実装するアルゴリズムは非常にシンプルで、以下

後順走査（ポストオーダー走査）は、木構造（ツリー）を巡回する方法のひとつで、「根ノードを最後に訪問する」ことからこの名前が付いています。まず左側の部分木をたどり、次に右側の部分木をたどり、最後に根ノードを処理するのが特徴です。 後順走査の流れ ここでは、ノード A を起点として考えてみましょう。後順走査では、最初に左部分木である B を訪問します。B の部分木も同じく後順でたどられるため、すべてのノードを訪問し終えるまで処理が再帰的に続きます。この木に対して後順走査を行った場合の出力結果は以下の通りです。 D → E → B → F → G → C → A 後順走査のアルゴリズム 今回実装する

木構造（ツリー）からノードを削除する処理は、一見すると複雑に感じられます。ノードの削除では、次の3つの場合分けを考慮する必要があります。これらは後述する関数のコメントにも記載しています。これまでの実装と同様に、クラス本体にメソッドを作成し、再帰的に呼び出すためのヘルパー関数を用意する形で実装していきます。 クラスメソッド deleteNode(key) { // ノードが正常に削除されると、参照が返されます。 return !(deleteNodeHelper(this.root, key) === false); } ヘルパーメソッド 削除対象のノードの状態によって、以下の3

二分探索木（Binary Search Tree：BST）は、各ノードが最大2つの子ノードを持つ木構造のデータ構造です。「左側の子孫は親より小さい値、右側の子孫は親より大きい値」という規則を保つことで、データの挿入・検索・削除を効率的に行えます。 この記事では、JavaScriptによる二分探索木クラスの完全な実装を紹介し、挿入・探索・削除などの主要な操作について詳しく解説します。すべての操作について、反復処理版と再帰処理版の両方を用意しています。 BinarySearchTreeクラスの完全な実装 以下が二分探索木クラスの完全な実装コードです。 class BinarySearchTree

AVL木とはAVL木（発明者であるAdelson-VelskyとLandisの名前にちなんで命名されました）は、自己平衡二分探索木の一種です。自己平衡木とは、部分木の内部で「回転（ローテーション）」と呼ばれる操作を行うことで、木の左右のバランスを自動的に保つデータ構造のことです。なぜ木のバランスが重要なのか二分探索木にデータを挿入し続けると、値の並び方によっては木が片側に偏ってしまうことがあります。このようなケースでAVL木は特に有効です。バランスの取れた木では、探索・挿入・削除の時間計算量がO(log n)に保たれます。一方、完全に偏った木（実質的に連結リストと同じ状態）では、計算量がO(n

AVL木（AVLツリー）は、左部分木と右部分木の高さを比較し、その差が1を超えないことを保証する自己平衡型二分探索木です。この高さの差のことをバランス係数（Balance Factor）と呼びます。バランス係数とは例として、次のような木を考えてみましょう。1つ目の木はバランスが取れていますが、2つ目と3つ目の木はバランスが崩れています。2つ目の木では、ノードCの左部分木の高さが2、右部分木の高さが0であるため、差は2になります。また、3つ目の木では、ノードAの右部分木の高さが2である一方、左部分木が存在しないため高さは0となり、ここでも差は2です。AVL木では、この差（バランス係数）は1以下で

AVL木は、ノードの挿入や削除によってバランスが崩れた際に、自己平衡性を保つために以下の4種類の回転（ローテーション）操作を実行します。 左回転（Left Rotation）右回転（Right Rotation）左右回転（Left-Right Rotation）右左回転（Right-Left Rotation） 最初の2つは「単回転」、後の2つは「二重回転」に分類されます。木が不平衡となるためには、少なくとも高さ2の木が必要です。ここではシンプルな木を例に、それぞれの回転操作を順番に解説していきます。 左回転（Left Rotation） あるノードの「右部分木のさらに右部分木」にノードを挿

AVL木へのノード挿入の基本 AVL木へのノード挿入は、通常の二分探索木（BST）とほぼ同じ手順で行います。ただし、AVL木では挿入処理の中で木を下っていくたびに、「バランス調整（balance）」という追加のステップを実行する必要があります。 バランス調整にはバランスファクター（平衡係数）の計算が必要です。これは以前の記事で解説した通り、左部分木と右部分木の高さの差から求められます。計算結果に応じて、適切な回転操作（LL回転・LR回転・RR回転・RL回転）を呼び出すことで、木の平衡状態を保ちます。どの回転を選択すべきかは、条件分岐の構成を見れば直感的に理解できるでしょう。 insertメソ

プログラミングをしていると、複数のコンテナを結合関数でまとめ、新しいコンテナとして取得したい場面がよくあります。ここでは、2つのHashTableを受け取り、すべての値を含む新しいHashTableを返す静的メソッドjoinを実装します。シンプルにするため、両方のテーブルに同じキーが存在する場合は、第2引数のHashTableの値が第1引数の値を上書きする仕様とします。実装例 combo.put(k, v)); return combo; }このメソッドは、まず新しい空のHashTableを作成し、forEachを使って2つのテーブルのすべてのキーと値を順番に挿入していきます。同じキー

ハッシュテーブル（Hash Table）は、キーと値のペアを高速に管理できる代表的なデータ構造です。キーをハッシュ関数に通して得られた「ハッシュ値」をインデックスとして使うため、平均O(1)の計算量で要素の追加・検索・削除が行えます。 JavaScriptには標準でMapやObjectが用意されていますが、ここではハッシュテーブルの内部構造を理解するために、HashTableクラスをゼロから実装します。以下の実装では、チェイン法（Separate Chaining）を採用しており、ハッシュ値の衝突（コリジョン）が発生しても、複数の要素を同じバケットに格納できるようになっています。もちろん、より

ツリーデータ構造とは?ツリー(木)構造は、組織図やファイルシステムなど、階層的なデータを表現するための基本的なデータ構造です。JavaScriptにおいても、DOM(ドキュメントオブジェクトモデル)やJSONデータの操作など、さまざまな場面でツリー構造の考え方が活用されています。ツリーの定義より形式的に言うと、ツリーは再帰的(局所的)に定義できます。つまり、ツリーとはルートノード(root node)から始まるノードの集合であり、各ノードは「値」と「子ノード(children)への参照のリスト」から構成されるデータ構造です。この定義には重要な制約があります。それは参照が重複してはならないという

二分木（バイナリツリー）は、データの格納を目的として使用される特殊なデータ構造です。最大の特徴は、各ノードが持てる子ノードの数が2つまでという条件にあります。二分木は、整列済み配列と連結リストの両方の長所を兼ね備えた構造です。検索はソートされた配列と同等の速さで行え、データの挿入や削除も連結リストと同様に高速に実行できます。そのため、大量のデータを効率的に扱いたい場合に非常に有用なデータ構造といえます。以下は、二分木の構造を示したイラストです。図には、このあと解説する重要な用語も含まれています。二分木における重要な用語二分木を理解するうえで押さえておきたい、主要な用語を以下にまとめました。パス

二分探索木とは二分探索木は、通常の木構造とは異なる特別な性質を持つデータ構造です。この性質により、データの検索・挿入・削除を効率的に行うことができます。二分探索木では、各ノードが次のルールに従わなければなりません。ノードの左の子は、必ず親ノードより小さい値を持つノードの右の子は、必ず親ノードより大きい値を持つこの規則が成り立つことで、値を探す際に「目的の値より小さければ左へ、大きければ右へ」と分岐をたどるだけで済み、探索範囲を毎回半分に絞り込めます。そのため、整列された配列に対する二分探索と同様の効率性が得られます。本記事を含む木構造のセクションでは、主にこの二分探索木を中心に解説を進めていき