ハッシュ法
ここまでの授業では、配列(データ検索は、登録順保存ならO(N)、２分探索ならO(log N)となる、2分探索ができるのは配列がランダムアクセスができるからこそ)、単純リスト(データ検索(シーケンシャルアクセスしかできない […]
データベースとB木
2分探索木の考え方を拡張したものでB木があり、データベースシステムではB木を基本としたデータ構造が活用されている。 B木の構造 2分木では、データの増減で木の組換えの発生頻度が高い。そこで、1つのノード内に複数のデータを […]
木構造の探索・深さ優先探索・幅優先探索
深さ優先探索(前順) 以前紹介した2分木の表示では、再帰呼び出しで木の処理を記述していた。 しかし、スタックを使って未処理のノードを保存しながらノードに対する処理を行えば、ループ処理で「すべての木のノード」に対する処理を […]
2分木による構文木
逆ポーランド記法とスタックマシン 逆ポーランド記法(RPN)は、(1+2)*3 であれば “1 2 + 3 *” のように表すことができ、この書き方は「1と2を加える、(それに)3を掛ける」という […]
2分木の応用(意思決定木と演算子)
データをO(log N)で検索するための2分探索木以外の2分木のデータ構造について解説を行う。 意思決定木 意思決定木の説明ということで、yes/noクイズの例を示しながら、2分木になっていることを 説明しプログラムを紹 […]
2分ヒープとレポート課題
2分ヒープ(binary heap) 2分探索木では、１つのノードにつき2つのポインタを持ち、データ1件あたりのメモリの使用量が多い。通常の「配列の先頭から昇順にデータを並べる2分探索法」では、途中にデータを挿入する場合 […]
2分探索木への追加とAVL
2分探索木にデータを追加 前回の2分探索木では、基本的な説明ということで、木の生成では直接木構造を生成していた。しかし、本来であれば、扱うデータに応じて木を生成することが求められる。 Javaの場合 以下の Javaのプ […]
2分探索木
配列やリスト構造のデータの中から、目的となるデータを探す場合、配列であれば2分探索法が用いられる。これにより、配列の中からデータを探す処理は、O(log N)となる。(ただし事前にデータが昇順に並んでいる必要あり) // […]
双方向リストとdeque
deque(両端キュー) 双方向循環リストを使うと、(1)先頭にデータを挿入(addFirst/unshift)、(2)先頭のデータを取り出す(removeFirst/shift)、(3)末尾にデータを追加(addLas […]
双方向リスト
単純リストから双方向リストへ ここまで説明してきた単純リストは、次のデータへのポインタを持つ。ここで、１つ後ろのデータ(N番目からN+1番目)をアクセスするのは簡単だけど、１つ前のデータ(N-1番目)を参照しようと思った […]