プログラミング

セグメントツリーとは セグメントツリー（Segment Tree）は、配列に対する「区間に関する問い合わせ」と「要素の更新」を高速に処理するためのデータ構造です。本記事では、セグメントツリーが必要とされる背景と、その基本的な構成方法について解説します。 解決したい問題 まず、次のような問題を考えてみましょう。長さ n の配列 arr[0 … n-1] が与えられたとき、以下の2つの操作を効率よく行いたいとします。 区間和の取得：インデックス l から r までの要素の合計を求める（0 ≤ l ≤ r ≤ n-1） 要素の更新：指定したインデックス i の値を新しい値 x に変更する（arr

K分木（K-aryツリー）とはこの記事では、データ構造のひとつであるK分木（K-aryツリー）について解説します。K分木とは、根付き木（rooted tree）の一種で、各ノードが持つことのできる子ノードの数が最大でk個に制限された木構造です。この「k」の値によって、木の形状や性質が大きく変わります。二分木・三分木との関係k = 2 の場合、この木は二分木（バイナリツリー）として知られています。同様に、k = 3 の場合は三分木（ターナリーツリー）と呼ばれます。つまり、二分木や三分木はK分木の特殊なケースであり、K分木はこれらを一般化した概念だと言えます。この一般化により、データベースのB木や

非循環有向グラフ（DAG）とは 非循環有向グラフ（Acyclic Digraph）とは、有向サイクル（閉路）を一切含まない有向グラフのことを指します。英語では「Directed Acyclic Graph」と表記され、その頭文字を取ってDAGと略されるのが一般的です。 DAGにおいては、どのノードから出発して辺を辿っていっても、二度と同じノードに戻ることがないという点が最大の特徴です。 DAGの重要な性質 すべての有限のDAGには、出次数（そのノードから出ていく辺の数）が0であるノードが少なくとも1つ存在することが数学的に証明されています。これはDAGの最も基本的な性質の一つです。 また、こ

高さ平衡左偏木（HBLT）とは 本記事では、データ構造の一つである高さ平衡左偏木（Height Balanced Leftist Tree：HBLT）について詳しく解説します。 外部ノードと拡張二分木 まず、空の部分木を外部ノード（external node）と呼ばれる特殊なノードで置き換えた二分木を考えてみましょう。外部ノード以外のすべてのノードは内部ノード（internal node）と呼ばれます。このように、既存の二分木に外部ノードを追加して完成させた木を拡張二分木（extended binary tree）といいます。 この木から葉につながる辺を取り除いて考えると、それが元々の二分

最大HBLTへの挿入とは最大HBLT(Height-Biased Leftist Tree、高さ偏り左傾木)への要素の挿入は、「Meld(マージ)操作」を利用することで実現できます。Meld操作とは、2つの最大HBLTを1つの最大HBLTへと統合するための基本操作です。Meld操作を使った挿入手順例として、要素xを最大HBLTであるHに挿入する場合を考えてみましょう。手順は以下の通りです。挿入したい要素xだけを含む、小さなHBLTを新しく作成します。この新しいHBLTと既存のHに対して、Meld操作を実行します。Meld操作が完了すると、Hには要素xを含むすべての要素が格納された状態になります

最大HBLTの基本構造と最大要素の位置最大HBLT(Max HBLT:Height-Biased Leftist Tree)は、ヒープの性質を満たす二分木の一種です。このデータ構造では、親ノードの値が常にその子ノードの値以上になるように構成されているため、木全体で最も大きい要素は必ず根(ルート)に配置されます。最大要素の削除手順最大HBLTから最大要素を削除する操作は、以下の手順で行われます。根(ルート)の削除:最大値が格納されている根ノードを取り除きます。2つの部分木への分離:根が削除されると、残った左部分木と右部分木が、それぞれ独立した最大HBLTとして分離します。meld(併合)操作によ

HBLT（Height-Biased Leftist Tree、高さ優先左分木）同士の融合（meld）は、再帰を用いることで簡潔かつ効率的に実装できます。ここでは、融合対象となる2つの最大HBLTをAとBとして、その手順を解説します。融合の基本戦略まず、どちらか一方が空である場合は、空でないもう一方をそのまま結果として返すだけで処理は完了します。両方が空でない場合は、それぞれの根（ルート）が保持する要素を比較します。そして、より大きい要素を持つ根が、融合後のHBLTの根となります。Aの根の方が大きいと仮定しましょう。Aの左部分木をLとし、Aの右部分木とBを融合した結果得られる最大HBLTをCと

配列表現におけるメモリの無駄の問題 データ構造における配列による表現は、時間とともに変化するデータを格納する場合、基本的にメモリ領域を無駄にしてしまう傾向があります。あるデータを格納するためには、複数の値を余裕をもって格納できるサイズの配列を事前に確保しておく必要があり、多くの場合、配列の拡張には「配列倍増（アレイ・ダブリング）」という手法が用いられます。 配列倍増の仕組みとその課題 具体的な例で考えてみましょう。現在の配列サイズが8192であり、すでに満杯になっているとします。この場合、配列倍増の手法によってサイズを拡張する必要があり、新しい配列のサイズは16384になります。その後、旧配

最大HBLTにおける任意のノード削除とは最大HBLT（Height-Biased Leftist Tree：高さ偏り左木）や最小HBLTから任意のノードを削除することは、優先度付きキュー（プライオリティキュー）やHBLTにおける標準的な操作ではありません。しかし、特定の要件によっては、指定したノードKをHBLTから取り除く必要が生じる場合があります。その際は、以下のルールに従って削除を行います。削除の基本ルールサブツリーの分離とmeld（併合）による置換： ノードKを根とする部分木を木全体から切り離し、その位置にノードKの左右の部分木をmeldした結果を配置します。s値の更新と部分木の交換：

重みバイアス左翼木（WBLT）とは ここでは、左翼木（Leftist Tree）のもうひとつの変種である重みバイアス左翼木（Weight Biased Leftist Tree：WBLT）について解説します。通常の左翼木では、根から外部ノードまでの最短経路の長さを考慮しますが、WBLTでは代わりに部分木に含まれるノードの数を基準として扱う点が大きな特徴です。 重み w(x) の定義 ノード x の重み w(x) は、「x を根とする部分木内の内部ノードの総数」として定義されます。具体的には以下の通りです。 x が外部ノード（external node）の場合：w(x) = 0 x が内部ノ

Max-WBLTとはWBLT（Weight-Biased Leftist Tree：重み偏左木）は、優先度付きキューの実装に用いられるヒープ構造の一種です。本記事では、Max-WBLTにおける各種操作について詳しく解説します。HBLT（Height-Biased Leftist Tree：高さ偏左木）には、挿入（insert）、削除（delete）、初期化などの操作が存在しますが、これらはWBLTにもほぼ同様の形で適用できます。ただし、両者で大きく異なるのはmeld（併合）操作です。WBLTでは、meld操作をトップダウンの1回の走査で完了できるという大きな特徴があります。1回のパスで実現でき

ロビンフードハッシュ（Robin Hood Hashing）とは ロビンフードハッシュは、オープンアドレス法（開番地法）に分類されるハッシュ手法のひとつです。「富者から奪って貧者に与える」という伝説の英雄ロビンフッドの名前にちなんだこの方式は、要素ごとの探索時間に偏りが生じないよう、より公平な衝突解決戦略を採用している点が最大の特徴です。 従来の線形探査などの手法では、挿入順序やハッシュ値の分布によって、特定の要素だけ探索に長い時間がかかるといった「格差」が発生しがちでした。ロビンフードハッシュは、この格差を積極的に是正することで、最悪ケースの性能を大幅に改善します。 挿入時のルール：「若い

抽象データ型としての辞書抽象データ型である辞書(Dictionary)を実装する場合、各ノードに値を関連付けていくことになります。辞書とは、本質的には「全順序(total ordering)が定義された要素集合から取り出されたキーの集合」です。各キーには追加の情報(値)を関連付けることができますが、これは辞書の概念的理解には本質的には関わりません。二分探索木の不変条件辞書を木構造で実装する場合、各ノードは一意なキーを保持します。木の中の各ノード u に対して、左部分木 u.l 内のすべてのキーは u.k よりも厳密に小さく、右部分木 u.r 内のすべてのキーは u.k よりも厳密に大きい、とい

マージアルゴリズムとは マージ（併合）アルゴリズムは、2つの整列済み（ソート済み）リストを1つの整列済みリストに統合するための基本的なアルゴリズムです。さまざまな場面で利用されており、特にマージソートでは、分割された各部分リストを並べ替えた後、それらを大きなリストへと結合する段階でこのマージ処理が必須となります。 基本的な考え方 アプローチは非常にシンプルです。まず2つのリストを用意し、それぞれの先頭要素を指す2つのポインタを準備します。 次に、両ポインタが指す値を比較し、小さい方の要素を結果となる統合リストへ取り出します。そして、取り出した要素が属していた側のポインタを1つ進めます。この操

本記事では、B木（B-Tree）について詳しく解説します。B木は、m-way探索木を特殊化したデータ構造であり、ディスクアクセスを目的として広く利用されています。B木の基本構造次数（オーダー）が m のB木では、1つのノードが最大で m-1 個のキーと m 個の子を持つことができます。この特性により、1つのノードに大量の要素を格納できるため、木全体の高さが比較的低く抑えられる点が大きな利点です。高さが低いということは、検索時にアクセスするノード数が少なくて済むため、ディスクI/Oのコストが高い環境、たとえばデータベースやファイルシステムにおいて特に有効です。B木の満たすべき性質B木はm-way

本記事では、Rツリー（R-Tree）というデータ構造について詳しく解説します。Rツリーは、空間データのインデックスを効率的に格納するために設計された木構造であり、空間的な検索やデータの保存において非常に有用な仕組みです。Rツリーは現実世界のさまざまな場面で活用されており、主な応用例は以下の通りです。多次元情報のインデックス化ゲームデータの管理地理空間座標（ジオスペーシャルデータ）の保持仮想マップの実装Rツリーの構造例以下に、Rツリーによる空間データの表現例を示します。この空間データに対応するRツリーの構造は次のようになります。Rツリーの主な特性Rツリーには、以下のような重要な特性があります。R

この記事では、自己平衡型二分探索木の一つである赤黒木（Red-Black Tree）について解説します。赤黒木は、各ノードに「赤」または「黒」の色情報を持たせることで、木のバランスを自動的に保つデータ構造です。赤黒木が満たすべき条件赤黒木では、すべてのノードが以下の性質を満たす必要があります。各ノードは必ず「赤」または「黒」のいずれかの色を持つ根（ルート）ノードは常に黒である赤いノードが隣接して連続することはない（赤ノードの子は必ず黒）任意のノードからその子孫のNULLノードまでのすべての経路には、同じ数の黒ノードが含まれる（これを「黒高さ」と呼びます）赤黒木の例以下は、上記の条件を満たす赤黒

算術式を書き表す方法は「記法（ノーテーション）」と呼ばれます。算術式は、式の本質や計算結果を変えることなく、3つの異なる記法で表現できます。その3つが以下の通りです。中置記法（Infix）前置記法（Prefix）後置記法（Postfix）中置記法は、私たちが日常的に数式を書く際に使う標準的な記法です。一方、前置記法と後置記法はこれとは大きく異なる特徴を持っています。前置記法（Prefix Notation）とは前置記法では、演算子を被演算子（オペランド）の前に置くのが特徴です。つまり、演算子がオペランドより先に書かれます。例えば +ab は、中置記法の a + b と同じ意味になります。前置記

本記事では、データ構造の一つであるトーナメントツリーについて、勝者ツリー（Winner Tree）と敗者ツリー（Loser Tree）の違いを交えながら詳しく解説します。 トーナメントツリーとは？ トーナメントツリーとは、n個の外部ノード（葉）と n−1 個の内部ノードから構成される完全二分木です。外部ノードは選手（プレイヤー）を表し、内部ノードは2人の選手が対戦した結果の勝者を表します。スポーツのトーナメント表をイメージすると理解しやすく、この木は「セレクションツリー（選択木）」とも呼ばれます。 トーナメントツリーの主な性質 根付き木である： 親から子へ向かう有向パスが存在し、親を持たない

本記事では、データ構造の一種である根なし二分木（unrooted binary tree）について解説します。根なし二分木は、閉路（サイクル）を持たない連結な無向グラフとして定義される木構造です。根なし二分木の基本概念根なし二分木には「根」となる特定の頂点が存在せず、すべての頂点が対等な立場で扱われる点が大きな特徴です。この木構造における各要素は、以下のように分類されます。葉（リーフ）：隣接する頂点（近傍ノード）を1つだけ持つ頂点内部ノード：葉以外の残りのすべての頂点また、頂点の次数（degree）とは、その頂点に隣接する頂点の数を指します。2つ以上のノードを持つ木において、葉は次数1の頂点と