プログラミング

データ構造における根付きツリー(有根木)と根なしツリー(無根木)は、どちらもノードとエッジで構成される木構造ですが、その性質と用途には重要な違いがあります。本記事では、両者の違いをわかりやすく解説します。まずは、それぞれのツリーの例から見ていきましょう。 根付きツリーの例 根なしツリーの例 根付きツリーと根なしツリーの基本的な違い 根付きツリーでは、子孫ノードを持つ各ノードが、それらの子孫全体にとっての最も近い共通祖先(最近共通祖先)を表します。さらに、ツリーによっては、エッジ(辺)の長さが時間的な経過の推定値として解釈される場合もあります。 一方、根なしツリーには祖先を示す「根」が

ユニバーサルハッシュの背景にある問題 ハッシュ表の設計では、単一のハッシュ関数に頼ること自体に本質的な限界があります。ハッシュ表のサイズ m が、キー全体の集合（ユニバース）U のサイズ u に比べて非常に小さい場合、どんなハッシュ関数 h を選んでも、U の中には必ず同じハッシュ値へ対応づけられる大きな部分集合が存在してしまいます。 つまり、実際に入力されるデータ S がたまたまその「衝突しやすい部分集合」と一致すると、ハッシュ関数の性能は極端に劣化します。しかもこの問題は、事前に悪い入力の内容が分からない限り、回避することができません。 解決策：ハッシュ関数の族（ファミリー）を使う この

チェイン法（連鎖法）によるハッシュとはこのセクションでは、チェイン法（Chaining、連鎖法）と呼ばれるハッシュ手法について解説します。チェイン法は、ハッシュテーブルにおける衝突（コリジョン）を解決するための代表的な手法の一つです。ハッシュテーブルでは、異なるキーが同じハッシュ値にマッピングされる「衝突」を完全に避けることはできません。しかし、衝突の発生をできるだけ抑えたり、同じハッシュ値を持つ複数の要素を適切に格納したりすることは可能です。チェイン法はまさにこの課題に対処するためのアプローチです。基本的な仕組みここでは、0から6までの値を返すハッシュ関数 h(x) を想定してみましょう。こ

オープンアドレス法とはオープンアドレス法(開番地法)は、ハッシュテーブルにおける衝突(コリジョン)を解決するためのもう一つの代表的な手法です。チェイン法(連鎖法)とは異なり、要素を別のデータ構造に格納するのではなく、ハッシュテーブル自体に直接データを挿入する点が大きな特徴です。そのため、すべてのキーを格納できるよう、ハッシュテーブルのサイズはキーの総数よりも大きく設定する必要があります。オープンアドレス法の3つの主要な手法オープンアドレス法には、広く知られている手法として以下の3つがあります。線形探査法(Linear Probing)二次探査法(Quadratic Probing)ダブルハッシ

線形探索法（リニアプロービング）とは 本記事では、ハッシュテーブルの衝突解決手法の一つであるオープンアドレス法における「線形探索法（リニアプロービング）」について詳しく解説します。 まず、通常のハッシュ関数 h′(x)：U → {0, 1, …, m−1} を考えます。ここで U はキーの全体集合、m はハッシュテーブルのサイズです。 h′(x) = x mod m オープンアドレス法では、この通常のハッシュ関数 h′(x) に試行回数 i を組み合わせ、次のような線形式として実際のハッシュ関数 h(x, i) を定義します。 h(x, i) = (h′(x) + i) mod m i は 0

二次プロービング（Quadratic Probing）とは 二次プロービングは、ハッシュ表で衝突が発生した際に対応する手法の一つである「オープンアドレス法（open addressing）」で用いられる衝突解決技術です。 まず、通常のハッシュ関数 h′(x) : U → {0, 1, ..., m − 1} が与えられているものとします。オープンアドレス法では、この基本となるハッシュ関数に別の要素を組み合わせて二次式を構成することで、実際に使用するハッシュ関数 h(x) を作り上げます。 h′(x) = x mod m h(x, i) = (h′(x) + i²) mod m ここで使用する二

ダブルハッシュ法とは ダブルハッシュ（Double Hashing）は、ハッシュテーブルの衝突解決手法である「オープンアドレス法」の一種です。基本となるハッシュ関数 h′(x)：U → {0, 1, …, m−1} に対して、挿入先のセルがすでに使用中だった場合に、もう一つのハッシュ関数を組み合わせて新しい格納位置を求めます。 ダブルハッシュでは、次の2つの補助ハッシュ関数を定義します。 第1ハッシュ関数： h₁(x) = x mod m第2ハッシュ関数： h₂(x) = x mod m′合成ハッシュ関数： h(x, i) = (h₁(x) + i·h₂(x)) mod m ここで i は

ブレント法（Brents Method）とは本記事では、オープンアドレス法（open addressing）によるハッシングに関連する「ブレント法」について解説します。ブレント法はヒューリスティック（発見的手法）の一種であり、ハッシュテーブルにおける成功探索（目的の要素が実際に見つかる探索）の平均所要時間を最小化することを目的とした手法です。この方法はもともとダブルハッシングの技法に対して考案されたものですが、線形探査（linear probing）や二次探査（quadratic probing）をはじめとする、あらゆるオープンアドレス法の技術にも適用できます。要素の「エイジ」という概念オープ

平衡二分探索木とは 本記事では、平衡二分探索木（Balanced Binary Search Tree）について詳しく解説します。二分探索木（BST：Binary Search Tree）は、各ノードに対して「左の子にはより小さい要素、右の子にはより大きい要素」が配置されるという性質を持つ二分木です。 二分探索木の課題：木が偏る問題 二分探索木での要素検索は、平均的にO(log n)の時間計算量で実行できます。ただしこれは、二分探索木の高さに依存します。BSTの性質を保ちながら要素を挿入していくと、挿入順序によっては木が片側に偏ってしまう（スキューした状態になる）ことがあります。 木が極端に

非対称ハッシュ（Asymmetric Hashing）とは非対称ハッシュは、複数選択ハッシング（multiple choice hashing）を発展させたハッシュ技法の一つで、チェーンの長さの偏りを抑え、検索・挿入性能を向上させることを目的としています。ここでは、非対称ハッシュの基本的な仕組みと、理論的に保証される性能について解説します。基本構造：ハッシュテーブルの分割非対称ハッシュでは、まずハッシュテーブル全体を d 個のブロックに分割します。各ブロックの長さは n/d となります。このとき、探査値（probe value）xi（0 ≤ i ≤ d−1）は、以下の範囲から一様ランダムに選択

LCFSハッシングとはこの記事では、LCFSハッシング（Last Come First Serve Hashing：後着優先ハッシング）について詳しく解説します。LCFSはオープンアドレス法（開番地法）の一種であり、従来の衝突解消の戦略を変更した興味深い手法です。従来のオープンアドレス法との違い（FCFS方式）オープンアドレス法によるハッシングのアルゴリズムを確認すると、2つの要素が衝突した場合、先に到着した要素がテーブルに保持され、後から来た要素は次の空き場所へ移動しなければなりません。つまり、通常のオープンアドレス法は「先着順（FCFS：First Come First Serve）」の基

グラフは代表的な非線形データ構造の一つです。このデータ構造では、値（データ）を「ノード（頂点）」に格納し、ノード同士を「エッジ（辺）」で結びつけて表現します。グラフにデータを格納できるように、目的の要素を探して取り出すためには、探索（サーチ）の仕組みが必要になります。グラフの探索には、主に次の2つの手法が用いられます。幅優先探索（Breadth First Search / BFS）深さ優先探索（Depth First Search / DFS）幅優先探索（BFS）とは幅優先探索（BFS）は、与えられたグラフのすべてのノードを巡回するためのアルゴリズムです。まず1つのノードを選択し、その隣接ノ

有向グラフにおける深さ優先探索（DFS）とは無向グラフの場合と同様に、有向グラフ（ダイグラフ）に対しても深さ優先探索（DFS）を適用できます。ただし、有向グラフでは辺に向きが存在するため、探索の過程で現れる辺をいくつかの種類に分類できる点が大きな特徴です。DFSアルゴリズムを実行すると、「DFS木」と呼ばれる木構造が形成されます。このとき、グラフ内の辺は以下の4種類に分類されます。辺の4つの分類木辺（Tree Edge：T） ― DFS木そのものに含まれる辺です。前進辺（Forward Edge：F） ― 一連の木辺の経路と平行になる辺です。具体的には、DFS番号が小さい頂点から大きい頂点へ向

この記事では、グラフ理論における重要な概念であるオイラーグラフとハミルトングラフについて解説します。これらを理解する前に、まずグラフにおける「トレイル(小道)」という基本的な概念を押さえておきましょう。トレイル(小道)とは何かトレイルとは、辺の列 (v1, v2), (v2, v3), …, (vk−1, vk) で構成される道のことです。このとき、頂点 (v1, v2, …, vk) は同じ頂点を複数回通っても構いませんが、すべての辺は互いに異なる(重複しない)必要があります。上図のグラフを例にとると、{(B, A), (A, C), (C, D), (D, A), (A, F)} はトレイ

二項ヒープ（Binomial Heap）は、複数の「二項木（Binomial Tree）」を集めて構成されるデータ構造です。二項木 Bk は再帰的に定義される順序付き木であり、最も単純な二項木 B0 は、たった1つのノードから成ります。 二項木の定義 二項木 Bk は、2つの二項木 Bk-1 を連結することで構成されます。このとき、一方の木の根が、もう一方の木の根の最も左の子となります。この定義により、木の規模は段階的に倍々に増えていくという特徴的な構造を持っています。 いくつかの二項ヒープの例を以下に示します。 二項木の主な性質 二項木 Bk は、ちょうど 2k 個のノードを持ちます。

フィボナッチヒープとはフィボナッチヒープ(Fibonacci Heap)は、二項ヒープ(Binomial Heap)と同様に、複数の木から構成されるデータ構造です。二項ヒープを緩くベースとしていますが、両者には重要な違いがあります。二項ヒープ内部の木が「順序付けられた木(ordered tree)」であるのに対し、フィボナッチヒープ内部の木は根(root)を持ちますが、順序付けられていない点が特徴です。ノードの構造フィボナッチヒープ内の各ノード x は、以下のようなポインタを持っています。p[x]:親ノードを指すポインタchild[x]:自身の子のうち任意の1つを指すポインタノード x の子同

本記事では、二分最大ヒープ（Max Heap）というデータ構造に新しい要素を挿入する方法について詳しく解説します。ヒープは優先度付きキューの実装などで広く使われる重要なデータ構造であり、挿入操作の仕組みを理解することはアルゴリズム学習の基礎となります。まず、以下のような初期状態のヒープ（完全二分木）を想定します。最大ヒープへの挿入アルゴリズム最大ヒープへの挿入は、次の手順で行われます。ヒープに空きがあるか確認し、満杯であれば処理を終了します。新しい要素をヒープの末尾（配列の最後の位置）に仮置きします。親要素と値を比較しながら、親より大きい場合は親と入れ替えて上へ移動させます（この操作を「アップ

ここでは、二分最大ヒープ（Binary Max Heap）というデータ構造から要素を削除する方法について解説します。まず、次のような初期状態の木を想定してください。 最大ヒープからの削除アルゴリズム 最大ヒープに対する削除操作では、通常「根（ルート）にある最大値を取り除く」処理を行います。削除後も親ノードは常に子ノード以上というヒープ条件を維持しなければならないため、単純に要素を取り除くだけでは不十分です。以下の擬似コードのように、末尾の要素を使ってヒープを再構成します。 delete(heap, n) − Begin if heap is empty, then exit

整数キーを扱うハッシュテーブルとはここでは、整数値をキーとして扱うハッシュテーブルについて解説します。キーの値 x は、次のような宇宙（ユニバース）U から取られるものとします。U = {0, 1, …, u − 2, u − 1}そして、ハッシュ関数 h の定義域はこの宇宙 U 全体であり、その値域は {0, 1, …, m − 1} の集合です。ここで、m ≤ u という条件が成り立ちます。つまり、ハッシュ関数 h は、取り得るすべての整数キーを受け取り、それを 0 以上 m − 1 以下の整数に対応付ける役割を果たします。実際に格納するデータ数 m がキー空間のサイズ u より小さいため

除算法によるハッシュとはここでは、除算法（division method）と呼ばれるハッシュ手法について解説します。この手法では、次のようなハッシュ関数を使用します。ℎ(𝑥) = 𝑥 𝑚𝑜𝑑 𝑚つまり、キー x を m で割った余りをハッシュ値として利用する、シンプルながら広く使われている方法です。チェイン法（連鎖法）による実装このハッシュ関数を実際に利用するためには、配列 A[0, …, m − 1] を用意します。配列の各要素は、連結リストの先頭ノードへのポインタを保持しています。連結リスト Li は配列要素 A[i] が指し示しており、h(x) = i を満たすすべての要素