第9回 優先度つき待ち行列,ヒープ,二分探索木

Slides:



Advertisements
Similar presentations
区間グラフにおける区間表現からMPQ-treeを効率よく構成するアルゴリズム
Advertisements

基本情報技術概論 I 演習(第5回) 埼玉大学 理工学研究科 堀山 貴史
ヒープソートの演習 第13回.
第12回 ソート(3): シェルソート、クイックソート
2 分探索木 Binary Search Tree 実行可能な操作 計算量 木の高さは,最悪 O(n) n = |A| : 要素の個数
アルゴリズムとデータ構造 第8回 ソート(3).
第10回 整列 ~ バブルソート,挿入ソート,選択ソート~
2分探索.
第11回 整列 ~ シェルソート,クイックソート ~
アルゴリズムとデータ構造 2013年6月18日
アルゴリズムとデータ構造1 2005年7月8日
アルゴリズムとデータ構造 2010年7月5日
第11回 整列 ~ バケットソート,基数ソート,ヒープソート~
情報工学概論 (アルゴリズムとデータ構造)
アルゴリズムとデータ構造 補足資料13-4 「2分探索木の追加・削除(ダイジェスト)」
アルゴリズムとデータ構造 2012年6月14日
情報工学概論 (アルゴリズムとデータ構造)
データ構造とアルゴリズム 第7回 木 ~ データ構造(3)~.
情報工学概論 (アルゴリズムとデータ構造)
2009/11/20 探索アルゴリズム(2) 第8講: 平成21年11月20日 (金) 4限 E252教室 コンピュータアルゴリズム.
データ構造とアルゴリズム 第6回の2 木 ~ データ構造(3)~.
エージェントを管理するボスの苦悩 問題 n人のエージェントを部下に持つボスがいる. エージェントは出張・帰還を頻繁に繰り返す.
ヒープソートの復習.
データ構造と アルゴリズム 第八回 知能情報学部 新田直也.
大岩 元 慶応大学環境情報学部 二分木 データ構造とプログラミング(10) 大岩 元 慶応大学環境情報学部
アルゴリズムとデータ構造 2011年6月14日
集合、辞書とハッシュ法 第8回 集合と辞書 ~ データ構造(4)~.
データ構造と アルゴリズム 第十一回 理工学部 情報システム工学科 新田直也.
アルゴリズムとデータ構造 第7回探索のためのデータ構造(1) 2015/11/18 アルゴリズムとデータ構造 2015.
第11回 整列 ~ シェルソート,クイックソート ~
二分探索木によるサーチ.
7-3.高度な木 (平衡木) AVL木 平衡2分木。回転操作に基づくバランス回復機構により平衡を保つ。 B木
2009/10/16 いろいろなデータ構造 第3講: 平成21年10月16日 (金) 4限 E252教室 コンピュータアルゴリズム.
算法数理工学 第3回 定兼 邦彦.
データ構造とアルゴリズム 第4回 リスト ~ データ構造(1)~.
“Purely Functional Data Structures” セミナー
アルゴリズムとデータ構造1 2006年7月4日
情報工学概論 (アルゴリズムとデータ構造)
アルゴリズムとデータ構造1 2005年7月15日
アルゴリズムとデータ構造勉強会 第6回 スレッド木
アルゴリズムとデータ構造 第3章 ヒープ 6月10日分
第9回 優先度つき待ち行列,ヒープ,二分探索木
データ構造と アルゴリズム 第七回 知能情報学部 新田直也.
データ構造と アルゴリズム 第六回 知能情報学部 新田直也.
基本情報技術概論(第6回) 埼玉大学 理工学研究科 堀山 貴史
Cプログラミング演習 第10回 二分探索木.
データ構造とアルゴリズム論 第9章 木構造 平成29年12月20日 森田 彦.
プログラミング 4 木構造とヒープ.
15.cons と種々のデータ構造.
アルゴリズムとデータ構造 第3章 ヒープ 5月31日分
情報知能学科「アルゴリズムとデータ構造」
アルゴリズムとデータ構造 第3章 ヒープ 5月31日分の復習
情報数理Ⅱ 第11章 データ構造 平成29年1月18日.
データ構造とアルゴリズム (第5回) 静岡大学工学部 安藤和敏
AVL木.
アルゴリズムとデータ構造 2011年6月16日
算法数理工学 第4回 定兼 邦彦.
基本情報技術概論(第6回) 埼玉大学 理工学研究科 堀山 貴史
ヒープソートの復習 第12回.
情報工学概論 (アルゴリズムとデータ構造)
アルゴリズムとデータ構造1 2009年7月2日
第11回放送授業.
平面走査法を使った 一般線分の 交点列挙アルゴリズム
ヒープソート.
アルゴリズムとデータ構造 2013年6月20日
参考:大きい要素の処理.
新人研修発表 平成13年5月14日(月) 探索アルゴリズム ハッシュ法について 株式会社 エーアイネット・テクノロジ          須田 哲生.
データ構造と アルゴリズムI 第三回 知能情報学部 新田直也.
7.木構造 7-1.データ構造としての木 7-2.2分探索木 7-3.高度な木.
Ibaraki Univ. Dept of Electrical & Electronic Eng.
Presentation transcript:

第9回 優先度つき待ち行列,ヒープ,二分探索木 データ構造とアルゴリズム 第9回 優先度つき待ち行列,ヒープ,二分探索木

(問1)解答 (チェイン法) 23 mod 5 = 3 48 mod 5 = 3 35 mod 5 = 0 4 mod 5 = 4 ポインタの配列 連結リスト 10 35 table[0] table[1] NULLの ところは斜線 バケット数 5の ハッシュ表 table[2] 48 23 table[3] table[4] 4

(問1)なぜ先頭に挿入するの? f c a g b c a f g b 挿入位置の計算O(1) 先頭への挿入なら一定時間でできる table [0] c a [1] 先頭への挿入なら一定時間でできる g b [2] 挿入位置の計算O(n) 末尾はどこ? table [0] c a f [1] g b [2]

(問2)解答オープンアドレス法 ハッシュ関数 h(x)= x mod 5 再ハッシュ hi (x)= (h(x)+i) mod 5 図示に必要な 配列の長さは5! Table[0]~table[5]まで 描いた人が結構いた!! ハッシュ関数 h(x)= x mod 5 再ハッシュ hi (x)= (h(x)+i) mod 5 h(23) = 23 mod 5 = 3 h(48) = 48 mod 5 = 3 再 h1(48)=(h(48)+1) mod 5 = 4 mod 5 = 4 h(35) = 35 mod 5 = 0 h( 4) = 4 mod 5 = 4 再 h1(4)= (h(4)+1) mod 5 = 5 mod 5 = 0 再 h2(4)= (h(4)+2) mod 5 = 6 mod 5 = 1 h(10) = 10 mod 5 = 0 再 h1(10)= (h(10)+1) mod 5 = 1 mod 5 = 1 再 h2(10)= (h(10)+2) mod 5 = 2 mod 5 = 2 バケット数 5の ハッシュ表 配列 35 table[0] 4 table[1] 10 table[2] 23 table[3] 48 table[4]

本日の内容 優先度つき待ち行列 半順序木,ヒープ 二分探索木

集合 A4 A1 A2 A3 集合 Ai A : 集合の要素 要素の重複は無い ×{1, 4, 1} 探索の「キー」は,必ず 重複しない(ユニークなID) ⇒ 集合の要素 要素の重複は無い     ×{1, 4, 1} 要素を並べる順序は不問 ○{1, 4} {4, 1}

順序つき集合 Pr4 Pr1 Pr2 Pr3 順序つき集合 Pri Pr : のある要素 集合Aの要素間に全順序が定義されているもの 以後の説明では、同じ要素を複数個もつことを許す多重集合を考えるものとする Pr4 Pr1 Pr2 Pr3 順序つき集合 Pri Pr :            のある要素

順序つき集合の操作 集合の基本的操作の他に以下の操作がよく行われる MIN(A):A≠φならば、≦に関し最小の要素を返す 順序つき集合の操作   集合の基本的操作の他に以下の操作がよく行われる MIN(A):A≠φならば、≦に関し最小の要素を返す DELETEMIN(A): A≠φのとき最小の要素(複数個ある場合はその1つ)をAから取り除く 順序つき集合のデータ構造 優先度つき待ち行列: 2分探索木:

優先度つき待ち行列の例 その1 病院の待ち合い室 重症 優先 患者の集合

優先度つき待ち行列の例 その2 プロセスの集合 タイムシェアリングシステム中でサービスを待っているプロセス 時間 t プロセスA プロセスB 優先度つき待ち行列の例 その2 タイムシェアリングシステム中でサービスを待っているプロセス 時間 t プロセスA プロセスB プロセスC 経過時間の短いプロセスを優先して処理する プロセスの集合

DeleteMinの手順 1.根にあった3を削除  3 5 9 6 8 9 10 10 18 9

DeleteMin, Insertの計算量 3 例 8≦n≦15の場合は 木の高さ:3 半順序の回復に かかる ( ステップ) 根の削除(DeleteMin) O (1),要素の追加(Insert) O (1)   半順序の回復 O ( log2 n ) 3 例 8≦n≦15の場合は 木の高さ:3  半順序の回復に                       かかる (      ステップ)

疑問 最小だけでなく最大も見つけるのに便利な方法はないだろうか? 木を使って,その他の要素も効率よく探索するにはどうしたらよいだろう?

2分探索木の例 5 7 14 18 15 12 10 1 3 2 4

2分探索木の実現 5 7 14 18 10 15 12 10 5 14 7 12 18 15 left_child right_child 構造は2分木のときと同じ left_child right_child element 5 7 14 18 10 15 12 root 10 5 14 7 12 18 15 NODE型のセル

Member 10 5 14 7 12 18 15 xはAの要素か? Aが空の木 → false x = Aの根 → true  → xは 要素か? 5 14 7 12 18 15

Insert 10 5 14 7 12 18 15 xをAに挿入する Aが空の木 → Aの根をxとする x=Aの根 → 挿入する必要なし Aが空の木 → Aの根をxとする x=Aの根 → 挿入する必要なし または2重登録として エラーとする  → xを に挿入 5 14 7 12 18 15

Delete 10 5 14 7 12 18 15 xをAから削除 xのある節点は葉 → にする xのある節点は子が一人 → → にする xのある節点は子が一人 → xのある節点は子が二人 →xを根とする部分木において, 根を削除 を根に入れる 5 14 7 12 18 15

左部分木の最大値と右部分木の最小値 Lmax < x < Rmin x L R

ランダムな順番でデータを挿入し木を作ったと仮定すると 2分探索木操作の時間解析 探索の計算量は木の形状によって変化する 2 1 3 4 5 6 7 昇順にデータが挿入された場合 7 2 3 6 4 5 1 最良のパターン(完全2分木) 最悪のパターン ランダムな順番でデータを挿入し木を作ったと仮定すると 平均の計算量 O (log n )

半順序木は優先度つき待ち行列の実現に適している. 半順序木との効率比較 半順序木 2分探索木 Insert DeleteMin (平均,最悪とも) (最悪でO ( n )) Delete - Member 半順序木は優先度つき待ち行列の実現に適している. その他の操作の効率はよくない

本日の課題 (問1) 以下の数列は,半順序のついた2分木をヒープで表現したものである.この数列が表している木を描け.また,この木からDeleteMinを行った結果の木を描け. 数列 2, 7, 4, 9, 7, 4, 12, 10, 13, 11 数列が表わす木 DeleteMinの結果の木 (問2) 下図 (a) (b) は3要素{1, 2, 3}から成る5種類の2分探索木のうちの2種である.残りの3種を描け.また,それぞれ,行きがけ順,通りがけ順,帰りがけ順で走査した結果を示せ. ( c ) ( d ) ( e )