データ構造 | YottaGin

[グラフ] 素集合データ構造

以下のスライドがダントツで分かりやすいです。素集合データ構造素集合データ構造（そしゅうごうデータこうぞう、英: disjoint-set data structure）は、データの集合を素集合（互いにオーバーラップしない集合）に分割し...

Python で三分探索木を実装してみます。ノードクラスそれぞれのノードは、その文字を持ち、左右と真ん中に子を持ちます。また、キーとしてその文字列が存在する場合は、値を持ちます。 class Node(object): ...

三分探索木三分探索木（さんぶんたんさくぎ、英:ternary search tree）は、トライ木の各ノードを二分探索木として表現したデータ構造である。出典: フリー百科事典『ウィキペディア（Wikipedia）』三分探索木は、トライ木...

TRIE木トライ木（英:trie）やプレフィックス木（英:prefix tree）とは、順序付き木の一種。あるノードの配下の全ノードは、自身に対応する文字列に共通するプレフィックス（接頭部）があり、ルート（根）には空の文字列が対応している。値は一般に...

Python では、連想配列として辞書型が組み込まれているので、そちらを通常は利用します。 5.5.辞書型 (dictionary) マッピング型 ---dict ここでは辞書は使わず、自分の理解のため簡単な連想配列をスクラッチから実装して...

連想配列連想配列（れんそうはいれつ、英語:associative array）とは、コンピュータプログラミングにおいて、添え字にスカラー数値以外のデータ型(文字列型等)も使用できる配列である。抽象データ型のひとつ。連想リスト、連想コンテナ、辞書（ある...

Python のリストを使い Max Heap を2分ヒープで実装します。初期化配列の最大要素数を定数MAX_NUM_ITEMSとして定めます。また、self.heap_size という定数を用意して、配列の最後の要素にアクセスする際...

ヒープは過去にもまとめています。最初よく混乱しますが、メモリのヒープとデータ構造のヒープは別のものです。 2分ヒープ二分ヒープ（にぶんヒープ,バイナリヒープ,Binary heap）とは、二分木を使って作られるヒープ(データ...

優先度付きキュー優先度付きキュー（ゆうせんどつき -、英:priority queue）は、以下の4つの操作をサポートする抽象データ型である。キューに対して要素を優先度付きで追加する。最も高い優先度を持つ要素をキューから取り除き、それを返す。(オプ...

以前にまとめた赤黒木は以下です。赤黒木 Red Black Tree 赤黒木（あかくろぎ）は、コンピュータ科学のデータ構造である平衡二分木の一種で、主に連想配列の実装に用いられている。2色木、レッド・ブラック・ツリーともいう。出...