酒居敬一(sakai.keiichi@kochi-tech.ac.jp) アルゴリズムとデータ構造 2013年6月20日 酒居敬一(sakai.keiichi@kochi-tech.ac.jp) http://www.info.kochi-tech.ac.jp/k1sakai/Lecture/ALG/2013/index.html.

Slides:



Advertisements
Similar presentations
A Simple Constant Time Enumeration Algorithm for Free Trees 中野 眞一 宇野 毅明 群馬大学 情報学研究所 2003 年 9 月 19 日 アルゴリズム研究会.
Advertisements

データ構造とプログラミング技 法 (第3回) ー木構造ー. 木構造 (1) 根( root )と呼ばれる節 R が、 1 つだけ含まれ る。 R … TmTm T1T1 木構造: 1 個以上の節の有限集合 T であり、 次の二つの条件を満足するもの (2) 根以外の節は、 m (≧ 0 )個の互いに素な部.
区間グラフにおける区間表現からMPQ-treeを効率よく構成するアルゴリズム
基本情報技術概論 I 演習(第5回) 埼玉大学 理工学研究科 堀山 貴史
離散システム特論 整列(sorting)アルゴリズム 2.
ヒープソートの演習 第13回.
アルゴリズムとデータ構造1 2008年7月22日
2 分探索木 Binary Search Tree 実行可能な操作 計算量 木の高さは,最悪 O(n) n = |A| : 要素の個数
アルゴリズムとデータ構造 第8回 ソート(3).
2分探索.
アルゴリズムとデータ構造 2013年6月18日
アルゴリズムとデータ構造1 2005年7月8日
アルゴリズムとデータ構造 2010年7月5日
2分探索と2分木 ・ 2分探索 ・ ヒープ ・ 2分木.
On the Enumeration of Colored Trees
Problem G : Entangled Tree
アルゴリズムとデータ構造 補足資料13-4 「2分探索木の追加・削除(ダイジェスト)」
アルゴリズムとデータ構造 2012年6月14日
データ構造とアルゴリズム 第7回 木 ~ データ構造(3)~.
2009/11/20 探索アルゴリズム(2) 第8講: 平成21年11月20日 (金) 4限 E252教室 コンピュータアルゴリズム.
探索アルゴリズム (1) 第7講: 平成21年11月13日 (金) 4限 E252教室.
第7章 データベース管理システム 7.1 データベース管理システムの概要 7.2 データベースの格納方式 7.3 問合せ処理.
データ構造とアルゴリズム 第6回の2 木 ~ データ構造(3)~.
アルゴリズムとデータ構造 2011年6月14日
アルゴリズムとデータ構造 第7回探索のためのデータ構造(1) 2015/11/18 アルゴリズムとデータ構造 2015.
二分探索木によるサーチ.
7-3.高度な木 (平衡木) AVL木 平衡2分木。回転操作に基づくバランス回復機構により平衡を保つ。 B木
Cプログラミング演習 中間まとめ2.
アルゴリズムとデータ構造 2012年6月28日
アルゴリズムとデータ構造 2011年6月27日
“Purely Functional Data Structures” セミナー
アルゴリズムとデータ構造1 2005年7月26日
アルゴリズムとデータ構造1 2006年7月4日
アルゴリズムとデータ構造1 2006年6月16日
アルゴリズムとデータ構造1 2005年7月15日
二分木のメソッド(続き).
データ構造とアルゴリズム (第3回) ー木構造ー.
アルゴリズムとデータ構造 第3章 ヒープ 6月10日分
第9回 優先度つき待ち行列,ヒープ,二分探索木
データ構造と アルゴリズム 第七回 知能情報学部 新田直也.
データ構造と アルゴリズム 第六回 知能情報学部 新田直也.
A Simple Algorithm for Generating Unordered Rooted Trees
基本情報技術概論(第6回) 埼玉大学 理工学研究科 堀山 貴史
Cプログラミング演習 第10回 二分探索木.
アルゴリズムとデータ構造1 2009年7月9日
アルゴリズムとデータ構造 2010年7月26日
プログラミング 4 木構造とヒープ.
15.cons と種々のデータ構造.
アルゴリズムとデータ構造 第3章 ヒープ 5月31日分
アルゴリズムとデータ構造 第3章 ヒープ 5月31日分の復習
情報数理Ⅱ 第11章 データ構造 平成29年1月18日.
データ構造とアルゴリズム (第5回) 静岡大学工学部 安藤和敏
AVL木.
第9回 優先度つき待ち行列,ヒープ,二分探索木
アルゴリズムとデータ構造 2012年7月2日
アルゴリズムとデータ構造1 2008年7月24日
アルゴリズムとデータ構造 2011年6月28日
アルゴリズムとデータ構造 2011年6月16日
アルゴリズムとデータ構造 2013年7月1日
基本情報技術概論(第6回) 埼玉大学 理工学研究科 堀山 貴史
情報工学概論 (アルゴリズムとデータ構造)
アルゴリズムとデータ構造1 2009年7月2日
アルゴリズムとデータ構造 2013年7月2日
平面走査法を使った 一般線分の 交点列挙アルゴリズム
ヒープソート.
ヒープソート.
アルゴリズムとデータ構造1 2007年7月6日
7.木構造 7-1.データ構造としての木 7-2.2分探索木 7-3.高度な木.
Ibaraki Univ. Dept of Electrical & Electronic Eng.
Ibaraki Univ. Dept of Electrical & Electronic Eng.
Presentation transcript:

酒居敬一(sakai.keiichi@kochi-tech.ac.jp) アルゴリズムとデータ構造 2013年6月20日 酒居敬一(sakai.keiichi@kochi-tech.ac.jp) http://www.info.kochi-tech.ac.jp/k1sakai/Lecture/ALG/2013/index.html

平衡木 木を作り変えて性能のよい形に保つ 作り変えるための計算量が多すぎてもダメ AVL木 B木 ほどほどにバランスをとる 2分探索木の一種 多分木 (maybe treeではなく、multiway tree)

AVL木 どの頂点においても、 その左部分木と右部分木の高さの差が +1, 0, -1 のいずれかである2分探索木

この漸化式はFibonacci数列として有名 Fibonacchi数列 頂点数最少のAVL木の頂点数 この漸化式はFibonacci数列として有名 h=2

バランスが崩れて、AVL木でなくなった。 ( のノードの左部分木と右部分木) 17 9 21 5 13 19 23 3 7 11 15 1 を挿入すると… 17 9 21 5 13 19 23 3 7 11 15 バランスが崩れて、AVL木でなくなった。 ( のノードの左部分木と右部分木) 1 17

17 9 21 5 13 19 23 3 7 11 15 1 と を入れ替える(回転する)。 17 9 9 5 17 3 7 13 21 1 11 15 19 23

バランスが崩れて、 AVL木でなくなった。 91ページc) 17 9 21 5 13 19 23 3 7 11 15 17 9 21 23 13 11 5 7 3 19 10 を挿入すると… バランスが崩れて、 AVL木でなくなった。 15

バランスが崩れて、 AVL木でなくなった。 17 9 21 23 13 11 5 7 3 19 10 を挿入すると… バランスが崩れて、 AVL木でなくなった。 15 17 9 21 23 13 11 5 7 3 19 10 1回転してもダメ 15 17 9 21 23 13 11 5 7 3 19 10 15 を根に置くことにして、 2回転します。

削除した結果の木が、 AVL木の条件を満たさない場合 削除の場合 通常の2分探索木として頂点を削除 削除した結果の木が、 AVL木の条件を満たさない場合 木の形が90ページa)では一重回転 木の形が91ページc)では二重回転 教科書98ページにも、そう書いてある。 挿入にせよ削除にせよ、結果の木の形で 再構成の要・不要を判断する。ということ。

B木(B-tree) 二分木ではないが、探索用のm分木 いわゆる平衡木 順序木である B木を構成するためのルール 根から葉までの深さはどの葉についても同じである 各頂点(葉以外)の子の数は最大mである 各頂点(葉以外)の子の数は最小 である  は切り上げを意味する記号である 根は例外で、最小2である

頂点の構造 頂点にはデータは置かない 探索キーだけをおく キーは枝をたどるときの境目

B木の探索 途中の頂点にはデータは入ってない 根から部分木を選択しながら下降する 葉に達したら探索は終了 入ってる値は部分枝の選択のためのキー値 データは葉の部分におかれている そうしない実装もある 根から部分木を選択しながら下降する 部分木の選択にはO(log m)必要 葉に達したら探索は終了 葉の値と一致すれば成功、そうでなければ失敗

B木の頂点に置く境界値 頂点に置かれる値は部分木選択に使われる 境界値の条件は次の2つを満たす 条件を満たす値は複数あるがどれでもいい 左に位置する部分木の最大値以上 右に位置する部分木の最小値以下 条件を満たす値は複数あるがどれでもいい 境界値 境界値の左部分木 境界値の右部分木

44を探索 3を探索 29を探索 7 31 7未満の数 7以上31未満の数 31以上の数 3 6 22 29 - 49 3 6 7 22 29 31 49 探索失敗 未満, less than, より小さい 以上, greater than or equal to 以下, less than or equal to

新しいデータ(子)を追加するとき 追加すべき位置(親の頂点)を決定します 親の頂点に空きがあるか調べます 空きがない場合は親の頂点を分割します 親の親の頂点から新たに枝を増やします 親が根である場合は、新たな根を親の親として増やします 子を頂点に追加します

データ(子)を削除するとき 削除すべきデータを探索し、削除します 親からの枝の本数が最少数を満たすかどうか調べます 最少数に満たない場合は隣の頂点と子を按分します 按分した結果最少数を満たせない場合は隣の頂点と併合します 親が根である場合に最少数2を割ったら、根を削除します

計算量の考察 キー値の比較を1回行うと候補は半減する ちょうど半分ずつ絞りこめばO(log N) 候補が半減する場合がもっとも効率が良い 半減するようにデータを保持する 例:平衡木を使う ちょうど半分ずつ絞りこめばO(log N) キーの比較という手法を使う限りはこれ以上探索の効率はよくならない。

アルゴリズムとデータ構造 演習 学生番号: 名前: 8ページ下の図から を削除します。 アルゴリズムとデータ構造 演習 学生番号:                    名前:                 13 8ページ下の図から を削除します。 15 9 17 5 11 21 3 7 10 19 23 AVL木としてバランスが取れなくなりました。どのノードの 左部分木と右部分木の高さが規定外なのでしょうか? 回転操作により木をAVL木として再構成してください。