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

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

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

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

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

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

０ 2色木の歴史 2色木は、ルドルフ・ベイヤーが自身が考案したB木に基づいて「対称2分木」として1972年に発明. ０　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色条件 　　　①　各節点は赤(RED)または黒(BLACK) 　　　②　根(root)は黒(BLACK) 　　　③　すべての葉はNILL(色は黒(BLACK))(表示を省略) 　　　④　赤(RED)の節点の子は黒(BLACK) 　　　⑤　各節点について、その節点と子孫の 　　　　　 任意の葉を結ぶ単純道は同数の黒(BLACK)節点を含む　　

〈例〉 根は黒 赤の子は黒 葉はnillかつ黒 どの道も、黒の数は等しい 葉のNILLは表示しない方が見やすいため、表示しないことが多い。 根は黒　 26 17 41 赤の子は黒 14 21 ３０ 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の左部分木の親をｘとする 　　　　　　　　　　5行目→　ｘと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行目→　ｘの親は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(挿入)　　 場合１：　zの叔父yはRED 　zの親z.pとその兄弟y(zの叔父)が赤の場合を指す 　　　ポインタzは木を２レベル登る

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

Ⅴ　INSERT(挿入)　　 　場合１、２、３を組み合わせると、節点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は削除した接点ｚより、大きい値の中で一番小さい値 (ｚの右部分木の中で一番小さいもの) →ｚより大きくｙより小さいものはないので、左の子は持たない。 yが黒だと発生する可能性がある問題は3つ 1,　yがもともと根であり、yの赤の子が新しい根になった場合 　　→条件2に反する 2,　xとx.pが共に赤となってしまった場合　　　　　　　　　　　 　　→条件4に反する 3,　yが移動したために単純道の黒節点の数が1減ってしまった場合 　　→条件5に反する 特に3は、もともとyがいた場所にいるxが“特黒”を持っていると考えて解消する。 黒節点yを削除または移動するときは、xに黒を｢プッシュ｣し、xは赤でも黒でもない状態にする。 xは｢赤黒｣or｢黒黒｣ P２７０ yがもともと根であり、yの赤の子が新しい根になった場合→条件2に反する xとx.pが共に赤となってしまった場合　　　　　　　　　　　　→条件4に反する yが移動したために単純道の黒節点の数が1減ってしまった場合→条件5に反する もともとyがいた場所にいるxが“特別な黒”を持っているとして、xを含む単純道の黒節点を数える場合は1増やすこととしておく。 赤黒→1　黒黒→2　で数える　　ｘのｃｏｌｏｒ属性は赤黒→ＲＥＤ　黒黒→ＢＲＡCK

Ⅵ 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色木が実際に利用されている例を紹介します。

プログラミング言語における連想配列の実現 連想配列(連想リスト、ハッシュ、マップとも) 　実現方法として主に平衡二分木(２色木、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：カボチャ

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

連想配列を標準で提供する言語 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/