ITリテラシ | ページ 3

[データ構造] 三分探索木

三分探索木三分探索木（さんぶんたんさくぎ、英: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色木、レッド・ブラック・ツリーともいう。出...

Python でAVL木を実装します。ノード 2分探索木とあまり変わりません。 height というインスタンス変数を設定し、ノードの高さを保持します。 class Node(object): def __init__(s...

平衡二分探索木平衡二分探索木（へいこうにぶんたんさくぎ、英:self-balancing binary search tree）とは、計算機科学において二分探索木のうち木の高さ（根からの階層の数）を自動的にできるだけ小さく維持しようとするもの（平衡木...