2色木

2015.03.11卒業研究発表
2色木
(Red-Black Tree)
関屋 隼人
原田 尚実
研究の動機
• 2014年度前期のゼミで原田が担当となった項
目だった.
アルゴリズムイントロダクション1巻13章
• プログラミングで実現している人が少ない.
• GUIに興味を持った.
研究の目標
• 2色木のプログラム作成
• 2色木の可視化
• 2色木と二分探索木の比較
役割
• 関屋
GUIの描画プログラム作成
利用データ(Exel)の読み込みプログラムの作成
その他プログラム不備の修正
• 原田
2色木、二分探索木のプログラム作成
発表スライドの作成、利用データのピックアップ
2色木の実用例
目次
• 2色木の特徴
-2色木とは?
• 2色木の利用
-2色木の利用例は?
• 2色木の実現
-2色木をGUIで描画
2色木の特徴
‐2色木とは?
0 2色木の歴史
•
2色木は、ルドルフ・ベイヤーが自身が考案したB木に基
づいて「対称2分木」として1972年に発明.
•
のちにレオニダス・ギッバスとロバート・セジウィックが
研究し、「赤黒木」として論文で取り扱う.
•
2008年、2色木に条件を付け加え、操作が簡単になっ
た「Left-leaning Red-Black Tree」をベイヤーが考案.
(http://www.cs.princeton.edu/~rs/talks/LLRB/LLRB.pdf)
Ⅰ 二分探索木の親戚
二分探索木条件
親に対して、左の子の値は小さく、右の子の値は大きい
5
・・・根(root)
7
2
子
親
高さ
・・・節点(node)
・・・葉(leaf)
4
1
小<2<大
小
< 5 <
9
7<大
大
Ⅱ 2色条件
二分探索木条件に加え、以下の2色条件を満たしたものを2色木という.
2色条件
① 各節点は赤 ( R E D ) または黒 ( B L A C K )
② 根(root)は黒 ( B L A C K )
③ すべての葉はN I L L (色は黒 ( B L A C K ) )(表示を省略)
④ 赤 ( R E D ) の節点の子は黒 ( B L A C K )
⑤ 各節点について、その節点と子孫の
任意の葉を結ぶ単純道は同数の黒 ( B L A C K ) 節点を含
む
〈例〉
根は黒
赤の子は黒
葉はnillかつ黒
どの道も、黒の数は等しい
Ⅱ 2色条件
• 2分探索木では
木の高さで各操作の実行時間が決まる.→O(h)
木が高い場合、連結リストよりも悪い可能性も
• 2色木では
• 2色条件により、根と葉を結ぶ任意の単純道上の節点の配色を
制約することで、ある道の長さがある道の長さの2倍を超えること
がないことを保証できる.
→木はおおよそ平衡している(balanced)という(平衡二分木)
→n個の要素数に対して木の高さは高々2log(n+1)
→各操作に対して最悪実行時間を保証→O(logn)
Ⅲ 2色木の性質
• 木の各節点は属性color,key,left,right,p を持つ.
• 親や子が存在しなければポインタ属性はNILを持つ.
(根の親はNIL)
• SERCH,MINIMUM,MAXIMUM,SUCCESSOR,PREDECESSORは二分
探索木と同様に行える.
• INSERT,DELETEは二分探索木と同様に行うことができない.
そのため、ROTATEを行う必要がある.
Ⅳ ROTATE(回転)
• 左回転(LEFT-ROTATE)と右回転(RIGHT-ROTATE)が存在する.
〈例〉左回転
Ⅳ ROTATE(回転)
• 擬似コード
Ⅴ 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-INSERTFIXUP(T,z)を呼び出す.
• Z を赤に彩色した時点で2色木が
保たれる(zの親が黒)であれば、
そこで終了。
Ⅴ INSERT(挿入)
• 場合1: zの叔父yはRED
zの親z.pとその兄弟y(zの叔父)が赤の場合
を指す
ポインタzは木を2レベル登る
Ⅴ INSERT(挿入)
• 場合2: zの叔父yは黒 かつ z は右の子
• 場合3: zの叔父yは黒 かつ zは左の子
z.p.p(おじいちゃん)は変わらない。
z.pが黒となったので、whileは終了。
Ⅴ INSERT(挿入)
場合1、2、3を組み合わせると、
節点zの挿入後2色条件の満た
されていなかった木が2色木と
なり、次の操作ができるように
なる
①
②
③
④
⑤
各節点は赤 ( r e d ) または黒 ( b l a c k )
根(root)は黒 ( b l a c k )
すべての葉はN I L L (黒( b l a c k ) )
赤 ( r e d ) の節点の子は黒 ( b l a c k )
各節点について、その節点と子孫の
任意の葉を結ぶ単純道は同数の黒
( b l a c k ) 節点を含む
Ⅵ DELETE(削除)
• 2色木Tを通常の二分探索木とみなし、節点zを木Tから削除.
• 次節点yの色によって2色条件を満たさない場合がある
(yの左の子はNIL)
• 節点yがあった場所に移動してくる節点xにも気をつける必要が
ある
• 補助手続きRB-TRANSPLANT,RB-DERETE-FIXUPを呼び出し節点
の再彩色と回転を行う必要がある
Ⅵ DELETE(削除)
u→入れ替えられる対称(削除されるもの).
v→uに入るもの.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が左右どちらにも子を持っている場合
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
Ⅵ DELETE(削除)
• 場合2:wがBLACKでwの両方の子もBLACK
Ⅵ DELETE(削除)
• 場合3:wはBLACK,wの右の子だけがBLACK
Ⅵ DELETE(削除)
• 場合4:wがBLACK,wの右の子だけがRED
2色木の利用
‐2色木の実用例は?
プログラミング言語における連想配列の実現
• 配列
キー
0
1
2
値
リンゴ
ミカン
ブドウ
←数値
• 連想配列(連想リスト、ハッシュ、マップとも)
キー
Apple
Orange
Grape
値
リンゴ
ミカン
ブドウ
←文字
実現方法として主に平衡二分木(2色木、AVL木)、ハッシュテーブルが用いられる
二分探索木
1
Grape
ブドウ
2
Apple
リンゴ
3
Lemon
レモン
4
Melon
メロン
1
2
Grape:ブドウ
3
Lemon:レモン
Apple:リンゴ
7
4
Carrot:ニンジン
Orange:オレンジ
5
Orange
Melon:メロン
5
オレンジ
Pumpkin:カボチャ
6
Pumpkin
カボチャ
7
Carrot
ニンジン
ここでは、アルファベット順で早いものが小さ
い、後ろのものが大きいとしている.
6
2色(赤黒)木
1
Grape
ブドウ
2
Apple
リンゴ
3
Lemon
レモン
4
Melon
メロン
1
Grape:ブドウ
2
3
4
Lemon:レモン
Apple:リンゴ
7
3
4
5
Melon:メロン
Carrot:ニンジン
Orange:オレンジ
Pumpkin:カボチャ
5
Orange
オレンジ
6
Pumpkin
カボチャ
7
Carrot
ニンジン
5
6
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色木が二分探索木より優秀であることを確かめる.
• 利用データ
中部地方の各市(約174市)の人口
(引用:総務省「平成25年3月31日住民基本台帳人口・世帯数、平成24年度人口動態
(都道府県別)(総計)」 より)
描画にあたっての経過
12月
1月
2月・3月
上旬に研究内容を決定。
原田→ 2色木のプログラムを作成
関屋→ GUIの描写プログラムのベースを作成
2色木のプログラムと、GUIのプログラムを結合
GUIの描写に必要で2色木のプログラムでは
不足していた部分を追加・改善
2色木の実用例について調べる
3月の研究発表に向けて準備
スライドの作成、利用データのピックアップ
Excelデータの読み込み部分の作成
比較用二分探索木のプログラムの作成
結果
• わかったこと
・実際に2色木の方が二分探索木よりも木の高さが低くなる
・探索時間も2色木の方が短い
ことが確認できた
• 問題点
GUIでの描画の際に動作が遅くなってしまう.
今回、2280のデータを準備したが、
400ほどのデータ数であっても時間がかかった.
展望
• 高さが高い木の描画を工夫する
• その他の平衡二分木(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/