卒業研究発表 2色木 (Red-Black Tree)

Slides:



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

基本情報技術概論 I 演習(第5回) 埼玉大学 理工学研究科 堀山 貴史
離散システム特論 整列(sorting)アルゴリズム 2.
2 分探索木 Binary Search Tree 実行可能な操作 計算量 木の高さは,最悪 O(n) n = |A| : 要素の個数
2分探索.
第11回 整列 ~ シェルソート,クイックソート ~
アルゴリズムとデータ構造 2013年6月18日
アルゴリズムとデータ構造1 2005年7月8日
アルゴリズムとデータ構造 2010年7月5日
On the Enumeration of Colored Trees
情報工学概論 (アルゴリズムとデータ構造)
アルゴリズムとデータ構造 補足資料13-4 「2分探索木の追加・削除(ダイジェスト)」
第10回 ソート(1):単純なソートアルゴリズム
アルゴリズムとデータ構造 2012年6月14日
データ構造とアルゴリズム 第7回 木 ~ データ構造(3)~.
情報工学概論 (アルゴリズムとデータ構造)
第7章 データベース管理システム 7.1 データベース管理システムの概要 7.2 データベースの格納方式 7.3 問合せ処理.
データ構造とアルゴリズム 第6回の2 木 ~ データ構造(3)~.
第11講: 平成18年12月 8日 (金) 4限 E352教室 グラフ (1).
アルゴリズムとデータ構造 2011年6月14日
データ構造と アルゴリズム 第十一回 理工学部 情報システム工学科 新田直也.
アルゴリズムとデータ構造 第7回探索のためのデータ構造(1) 2015/11/18 アルゴリズムとデータ構造 2015.
二分探索木によるサーチ.
7-3.高度な木 (平衡木) AVL木 平衡2分木。回転操作に基づくバランス回復機構により平衡を保つ。 B木
アルゴリズムとデータ構造 2012年6月28日
アルゴリズムとデータ構造 2011年6月27日
“Purely Functional Data Structures” セミナー
アルゴリズムとデータ構造1 2005年7月26日
アルゴリズムとデータ構造1 2006年7月4日
1 T 行きがけ順: A B D F I J C G H 通りがけ順: D B I F J A G C H
アルゴリズムとデータ構造1 2006年6月16日
二分木のメソッド(続き).
アルゴリズムとプログラミング (Algorithms and Programming)
アルゴリズムとデータ構造勉強会 B+tree.
アルゴリズムとデータ構造勉強会 第6回 スレッド木
アルゴリズムとデータ構造 第3章 ヒープ 6月10日分
第9回 優先度つき待ち行列,ヒープ,二分探索木
データ構造と アルゴリズム 第七回 知能情報学部 新田直也.
データ構造と アルゴリズム 第六回 知能情報学部 新田直也.
基本情報技術概論(第6回) 埼玉大学 理工学研究科 堀山 貴史
Cプログラミング演習 第10回 二分探索木.
アルゴリズムとデータ構造 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日
算法数理工学 第4回 定兼 邦彦.
アルゴリズムとデータ構造 2013年7月1日
基本情報技術概論(第6回) 埼玉大学 理工学研究科 堀山 貴史
情報工学概論 (アルゴリズムとデータ構造)
Advanced Data Structure 第3回
アルゴリズムとデータ構造1 2009年7月2日
アルゴリズムとデータ構造 2013年7月2日
平面走査法を使った 一般線分の 交点列挙アルゴリズム
4.プッシュダウンオートマトンと 文脈自由文法の等価性
ヒープソート.
アルゴリズムとデータ構造 2013年6月20日
参考:大きい要素の処理.
7.木構造 7-1.データ構造としての木 7-2.2分探索木 7-3.高度な木.
Ibaraki Univ. Dept of Electrical & Electronic Eng.
Ibaraki Univ. Dept of Electrical & Electronic Eng.
プログラミング論 バイナリーサーチ 1.
Presentation transcript:

2015.03.11卒業研究発表 2色木 (Red-Black Tree) 関屋 隼人   原田 尚実

研究の動機 2014年度前期のゼミで原田が担当となった項目だった. プログラミングで実現している人が少ない. GUIに興味を持った.         アルゴリズムイントロダクション1巻13章 プログラミングで実現している人が少ない. GUIに興味を持った. なぜ、2色木を卒業研究の対象にしたのか。 前期のゼミで進めていた、「アルゴリズムイントロダクション」の2色木の項目を私(原田)が扱ったことがきっかけ。 また、ゼミの時点で調べた際、実際にプログラムを書いている人は少なかったので、研究対象としました。 さらに、関屋君がGUI(グラフィカルユーザインターフェイス)に興味を持ったことがきっかけで、2色木の可視化を実現しようと思いました。

研究の目標 2色木のプログラム作成 2色木の可視化 2色木と二分探索木の比較 なぜ、2色木を卒業研究の対象にしたのか。 前期のゼミで進めていた、「アルゴリズムイントロダクション」の2色木の項目を私(原田)が扱ったことがきっかけ。 また、ゼミの時点で調べた際、実際にプログラムを書いている人は少なかったので、研究対象としました。 さらに、関屋君がGUI(グラフィカルユーザインターフェイス)に興味を持ったことがきっかけで、2色木の可視化を実現しようと思いました。

役割 関屋 GUIの描画プログラム作成 原田 2色木、二分探索木のプログラム作成 利用データ(Exel)の読み込みプログラムの作成  その他プログラム不備の修正 原田  2色木、二分探索木のプログラム作成  発表スライドの作成、利用データのピックアップ  2色木の実用例

目次 2色木の特徴          -2色木とは? 2色木の利用          -2色木の利用例は? 2色木の実現          -2色木をGUIで描画

2色木の特徴 ‐2色木とは?

0 2色木の歴史 2色木は、ルドルフ・ベイヤーが自身が考案したB木に基づいて「対称2分木」として1972年に発明. 0 2色木の歴史 2色木は、ルドルフ・ベイヤーが自身が考案したB木に基づいて「対称2分木」として1972年に発明. のちにレオニダス・ギッバスとロバート・セジウィックが研究し、「赤黒木」として論文で取り扱う. 2008年、2色木に条件を付け加え、操作が簡単になった「Left-leaning Red-Black Tree」をベイヤーが考案.      (http://www.cs.princeton.edu/~rs/talks/LLRB/LLRB.pdf) B木→ハードディスクドライブなどに応用されている。 1978年に「赤黒木」と名前がつく。 2色木にさらに条件を加えた(赤ノードは常に左の子であるという条件)、 Left-leaning RBTreeというものをベイヤー自身が発表している。

Ⅰ 二分探索木の親戚 二分探索木条件 親に対して、左の子の値は小さく、右の子の値は大きい 5 7 2 4 9 1 ・・・根(root) 親 Ⅰ 二分探索木の親戚 二分探索木条件 親に対して、左の子の値は小さく、右の子の値は大きい 5 ・・・根(root) 7 2 親 子 ・・・節点(node) 高さ 親の値に対して、左の子の値は小さく、右の子の値は大きい。(逆でもよい) このルールのもと、データを保存することで、データを探索しやすくなるだけでなく、データの増減も簡単にできる。というのが2分探索木のメリットである。 しかし、2分 ・・・葉(leaf) 4 9 1    小<2<大       7<大    小  < 5 <   大

Ⅱ 2色条件 2色条件 ① 各節点は赤(RED)または黒(BLACK) ② 根(root)は黒(BLACK) Ⅱ 2色条件 二分探索木条件に加え、以下の2色条件を満たしたものを2色木という. 2色条件    ① 各節点は赤(RED)または黒(BLACK)    ② 根(root)は黒(BLACK)    ③ すべての葉はNILL(色は黒(BLACK))(表示を省略)    ④ 赤(RED)の節点の子は黒(BLACK)    ⑤ 各節点について、その節点と子孫の       任意の葉を結ぶ単純道は同数の黒(BLACK)節点を含む  

〈例〉 根は黒 赤の子は黒 葉はnillかつ黒 どの道も、黒の数は等しい 葉のNILLは表示しない方が見やすいため、表示しないことが多い。 根は黒  26 17 41 赤の子は黒 14 21 30 47 nil nil 10 16 19 23 28 38 nil nil nil nil nil nil 7 12 15 20 35 39 葉のNILLは表示しない方が見やすいため、表示しないことが多い。 nil nil nil nil nil nil nil nil nil nil nil 3 葉はnillかつ黒 どの道も、黒の数は等しい nil nil

Ⅱ 2色条件 2分探索木では 木の高さで各操作の実行時間が決まる.→O(h) 木が高い場合、連結リストよりも悪い可能性も 2色木では Ⅱ 2色条件 2分探索木では   木の高さで各操作の実行時間が決まる.→O(h)   木が高い場合、連結リストよりも悪い可能性も    2色木では 2色条件により、根と葉を結ぶ任意の単純道上の節点の配色を制約することで、ある道の長さがある道の長さの2倍を超えることがないことを保証できる.   →木はおおよそ平衡している(balanced)という(平衡二分木)   →n個の要素数に対して木の高さは高々2log(n+1)   →各操作に対して最悪実行時間を保証→O(logn) 平衡二分木

Ⅲ 2色木の性質 木の各節点は属性color,key,left,right,p を持つ. 親や子が存在しなければポインタ属性はNILを持つ. Ⅲ 2色木の性質 木の各節点は属性color,key,left,right,p を持つ. 親や子が存在しなければポインタ属性はNILを持つ.   (根の親はNIL) SERCH,MINIMUM,MAXIMUM,SUCCESSOR,PREDECESSORは二分探索木と同様に行える. INSERT,DELETEは二分探索木と同様に行うことができない.   そのため、ROTATEを行う必要がある. 木の各節点は属性color(色),key(キー),left(左の子),right(右の子),p(親) を持つ. 二分探索木にcolorの属性を加えた形。 SERCHは探索、MINIMUMは最小値、MAXIMUMは最大値、 SUCCESSORは次接点(次に大きいもの)、PREDECESSORは前接点(前に小さいもの)が何か。 INSERT(挿入)、DELETE(削除)を二分探索木同様に行うと、2色条件がくずれるため、 ROTATE(回転)を行う必要がある

Ⅳ ROTATE(回転)   左回転(LEFT-ROTATE)と右回転(RIGHT-ROTATE)が存在する. 〈例〉左回転

Ⅳ ROTATE(回転)    擬似コード 2行目→ 14、12、17をまるごと Xの右部分木として持ってくる。(yの左部分木だから、xよりも全部大きいことは分かっている) 3行目→ yの左部分木がNILでない場合 (空であれば、xとxの左部分木をそのままyの左の子として持ってくる)           4行目→ yの左部分木の親をxとする           5行目→ xとyの親が一致(xとyが兄弟となる)           6行目→ xの親が番兵(=xは根だった)ならば                 7行目→ 根はyになる           8行目→ xは根ではなく、xがxの親の左の子ならば                 9行目 →xの親の左の子をyとする(xの立場をyが奪う)           10行目→ xがxの親の右の子であれば、 それをyとする 11行目→ yの左の子にxが来る 12行目→ xの親はyとなって 左回転終了 ポインタのみを変更するだけ。

Ⅴ INSERT(挿入) 2色木Tを通常の二分探索木とみなし、節点zを木Tに挿入. ただし、zは必ず赤(RED)に彩色する. しかし、必ずしも2色木条件が満たされる状態にならない. 補助手続きRB-INSERT-FIXUPを呼び出し節点の再彩色と回転を行う必要がある.

Ⅴ INSERT(挿入) 14~15行でのT.nilをz.leftとz.rightに代入. 16行でzをREDに彩色. 17行で補助手続きRB-INSERT-FIXUP(T,z)を呼び出す. Z を赤に彩色した時点で2色木が保たれる(zの親が黒)であれば、そこで終了。

Ⅴ INSERT(挿入)   場合1: zの叔父yはRED  zの親z.pとその兄弟y(zの叔父)が赤の場合を指す    ポインタzは木を2レベル登る

Ⅴ INSERT(挿入) z.p.p(おじいちゃん)は変わらない。 場合2: zの叔父yは黒 かつ z は右の子   z.pが黒となったので、whileは終了。

Ⅴ INSERT(挿入)    場合1、2、3を組み合わせると、節点zの挿入後2色条件の満たされていなかった木が2色木となり、次の操作ができるようになる ① 各節点は赤(red)または黒(black) ② 根(root)は黒(black) ③ すべての葉はNILL(黒(black)) ④ 赤(red)の節点の子は黒(black) ⑤ 各節点について、その節点と子孫の   任意の葉を結ぶ単純道は同数の黒(black)節点を含む 

Ⅵ DELETE(削除) 2色木Tを通常の二分探索木とみなし、節点zを木Tから削除. 次節点yの色によって2色条件を満たさない場合がある   (yの左の子はNIL) 節点yがあった場所に移動してくる節点xにも気をつける必要がある 補助手続きRB-TRANSPLANT,RB-DERETE-FIXUPを呼び出し節点の再彩色と回転を行う必要がある 次接点yは削除したzの位置に入るもの。 次節点yは削除した接点zより、大きい値の中で一番小さい値 (zの右部分木の中で一番小さいもの) →zより大きくyより小さいものはないので、左の子は持たない。 yが黒だと発生する可能性がある問題は3つ 1, yがもともと根であり、yの赤の子が新しい根になった場合   →条件2に反する 2, xとx.pが共に赤となってしまった場合              →条件4に反する 3, yが移動したために単純道の黒節点の数が1減ってしまった場合   →条件5に反する 特に3は、もともとyがいた場所にいるxが“特黒”を持っていると考えて解消する。 黒節点yを削除または移動するときは、xに黒を「プッシュ」し、xは赤でも黒でもない状態にする。 xは「赤黒」or「黒黒」 P270 yがもともと根であり、yの赤の子が新しい根になった場合→条件2に反する xとx.pが共に赤となってしまった場合            →条件4に反する yが移動したために単純道の黒節点の数が1減ってしまった場合→条件5に反する もともとyがいた場所にいるxが“特別な黒”を持っているとして、xを含む単純道の黒節点を数える場合は1増やすこととしておく。 赤黒→1 黒黒→2 で数える  xのcolor属性は赤黒→RED 黒黒→BRACK

Ⅵ DELETE(削除) u→入れ替えられる対称(削除されるもの). v→uに入るもの.uの次接点. 1~2行目 uの親がT.nil(uが根)→根にvを持ってくる 3~4行目 uが左の子 → vをもとのuのあったところにもってくる 5行目 uが右の子 →       // 6行目 vの親にuの親がなる 1~2行目 uの親がT.nil(uが根)→根にvを持ってくる 3~4行目 uが左の子 → vをもとのuのあったところにもってくる 5行目 uが右の子 →       // 6行目 vの親にuの親がなる

Ⅵ DELETE(削除)   1. zの子がない または右か左に1つもつ場合  y=zの位置にx(zのどちらかの子)がくる

Ⅵ DELETE(削除) 2. zが左右どちらにも子を持っている場合 このとき、yには左の子は存在しないので、xをyの右の子とする  zの右部分木の中で一番小さい節点をyとして、yの色を記憶しておく  このとき、yには左の子は存在しないので、xをyの右の子とする yの親がzであれば、zの位置にyが入り、yの位置にxがくる(xの親はyのまま変わらない) yの親がzでないなら、x=y.rightがyの位置に入り、xがyがもといた位置にくる   yはz の色を引き継ぐ ※yの色がもともと黒の場合、2色木条件が満たされない →RB-DERETE-FIXUP(T,x)で再彩色と回転を行う

Ⅵ DELETE(削除) 場合1:xの兄弟wがRED While文の目的 1,xが赤黒節点 2,xが根を指す  3,適切な回転と再彩色を行ってループを停止 この文の中では常にxは根ではない黒黒節点を指している 2行目はxが親のどちらの子になるのかを決定する Xの兄弟Wに注目していく。 節点xが黒黒より、w=T.nilであると、xの方の単純道の黒節点数より、wの方の単純道の黒節点数が小さくなってしまい、 初めから2色木が成り立っていない状態になってしまう。 よって、W≠T.nil  p272 場合1 yの子xの兄弟wが赤ならば、 wとxとwの親の色を入れ替え、(wを黒、x.pを赤)  x.pで左回転を行う →xは変わらず、新しいwができる。これは、赤だったwの子なので、黒 →この後行う場合2、3、4 に当てはまる形になる

Ⅵ DELETE(削除) 場合2:wがBLACKでwの両方の子もBLACK 2、WがBLACKで、wの子が左右とも黒である場合 Xを黒に、wを赤に再彩色し、 Xの親x.pに特黒を付加する。→新しいx 新しいxは赤、または黒のカラー属性をもっている。 もし、赤であれば、xが赤黒となり、ループは停止。23行目でxを黒に再彩色する もし、黒であれば、xは黒黒で再び兄弟の色を見ていく。

Ⅵ DELETE(削除) 場合3:wはBLACK,wの右の子だけがBLACK 場合3:wはBLACK,wの右の子だけがBLACK 今度はxの兄弟wの右の子が黒、左の子は赤の場合 このとき、wとその左の子の色を交換する W=赤、w.left=黒 そのうえで右回転を行う→2色木条件は違反は発生しない Xの新しい兄弟wは黒であり、その右の子が赤になったので、場合4に変換された

Ⅵ DELETE(削除) 場合4:wがBLACK,wの右の子だけがRED p273 場合4 Xの兄弟Wが黒、右の子が赤の場合(左=赤、右=赤 と 左=黒、右=赤の2パターンある) Wはxとwの親の色を受け継ぐ(赤または、黒) Xとwの親を黒に、wの右の子を黒に再彩色してx.pで左回転を行うことで、 2色条件を満たすことができる。 Xを根としたら、ループは停止する

2色木の利用 ‐2色木の実用例は? 2色木が実際に利用されている例を紹介します。

プログラミング言語における連想配列の実現 連想配列(連想リスト、ハッシュ、マップとも)  実現方法として主に平衡二分木(2色木、AVL木)、ハッシュテーブルが用いられる キー 1 2 リンゴ ミカン ブドウ ←数値 値 連想配列(アソシエイティブ アライ) 配列:キーは数値  連想配列:キーは文字でも可能 この連想配列をプログラミング言語で簡単に表示できるのは、裏で平衡二分木やハッシュテーブルが用いられているから キー Apple Orange Grape リンゴ ミカン ブドウ ←文字 値

二分探索木 1 2 3 7 4 5 6 Grape:ブドウ Lemon:レモン Apple:リンゴ Melon:メロン Orange オレンジ 6 Pumpkin カボチャ 7 Carrot ニンジン 1 Grape:ブドウ 2 3 Lemon:レモン Apple:リンゴ 7 4 Melon:メロン Carrot:ニンジン 5 Orange:オレンジ 二分探索木はある接点(ノード)に対して右は大きく、左は小さいものをとる ここでは、アルファベット順で早いものが小さいと考える。 6 Pumpkin:カボチャ ここでは、アルファベット順で早いものが小さい、後ろのものが大きいとしている.

2色(赤黒)木 1 2 2 3 4 4 3 7 3 3 4 5 5 5 6 Grape:ブドウ Lemon:レモン Apple:リンゴ Melon メロン 5 Orange オレンジ 6 Pumpkin カボチャ 7 Carrot ニンジン 1 Grape:ブドウ 2 2 3 4 4 3 Lemon:レモン Apple:リンゴ Melon:メロン 7 3 3 4 5 5 Carrot:ニンジン 5 6 Orange:オレンジ Pumpkin:カボチャ

2色木 二分探索木 高さ 3 高さ 4 二分探索木に比べ、2色木は木の高さを低く保つ性質がある.(2log(n+1) ) Orange→オレンジ、Pumpkin→カボチャを探索する場合、二分探索木より2色木の方が早く見つかる. ⇒プログラミング言語で連想配列を実現するにあたって適している.

連想配列を標準で提供する言語 C++ Java Map 、HashMap、TreeMapなど JavaScript 文字列が添え字の連想配列として扱われる PL/SQL  PHP (配列と連想配列の区別がない) Perl   など

2色木の実現 ‐2色木をGUIで描画

2色木と二分探索木をGUIで描画 目的 利用データ 2色木と二分探索木を可視化して比較するため. 数少ないデータだとあまり差がつかない.    2色木と二分探索木を可視化して比較するため.    数少ないデータだとあまり差がつかない.    より多くのデータで量で比較することで、    本当に2色木が二分探索木より優秀であることを確かめる. 利用データ    中部地方の各市(約174市)の人口       (引用:総務省「平成25年3月31日住民基本台帳人口・世帯数、平成24年度人口動態 (都道府県別)(総計)」  より)

描画にあたっての経過 12月 上旬に研究内容を決定。 原田→ 2色木のプログラムを作成 関屋→ GUIの描写プログラムのベースを作成 1月 2色木のプログラムと、GUIのプログラムを結合 GUIの描写に必要で2色木のプログラムでは 不足していた部分を追加・改善 2色木の実用例について調べる 2月・3月 3月の研究発表に向けて準備 スライドの作成、利用データのピックアップ Excelデータの読み込み部分の作成 比較用二分探索木のプログラムの作成 研究経過 の紹介 ↓プログラムの実行

結果 わかったこと 問題点 ・実際に2色木の方が二分探索木よりも木の高さが低くなる ・探索時間も2色木の方が短い ことが確認できた   ・実際に2色木の方が二分探索木よりも木の高さが低くなる   ・探索時間も2色木の方が短い    ことが確認できた 問題点    GUIでの描画の際に動作が遅くなってしまう.    今回、2280のデータを準備したが、    400ほどのデータ数であっても時間がかかった. 2000近くのデータ=日本全国の市区町村の人口データ

展望 高さが高い木の描画を工夫する その他の平衡二分木(AVL木、2-3-4木)との関連性を学習する Left-leaning Red-Black Treeの見聞を深める 参考:「アルゴリズムイントロダクション」第1巻     Wikipedia       「Red-Black Tree by Java—これで分かった赤黒木」     http://www.moon.sannet.ne.jp/okahisa/rb-tree/