20130610 赤黒木.pptx

赤黒木 Red-‐Black tree
平衡木 (Balanced tree)
•  木構造において探索を行う場合、木の平衡状態によって探索にかかる時間が著
しくばらつく。 1
8
2
4
2
1
6
3
3
12
5
10
7
9
O(log n)
11
4
5
14
13
6
7
15
O(n)
•  木の深さによって探索にかかるコストが決定される。 •  バランスがとれている木が最も効率よく探索可能。 •  バランスがとれている木のことを平衡木(Balanced tree)と呼ぶ。
AVL木
AVL木
AVL木
2-‐3-‐4木
•  ASEARCHIN
– 
– 
– 
– 
2分木に柔軟性をもたせる
ノードが3つの値をもつ場合は4つの子ノードを持つ
ノードが2つの値をもつ場合は3つの子ノードを持つ
ノードが1つの値をもつ場合は2つの子ノードを持つ
ER
AAC
HIN
S
•  ノードを追加する
–  差し込みたい値に位置するノードが1つの値しか持たない場合は、そのまま2つの
値を持つノードにする
–  差し込みたい値に位置するノードが2つの値を持つ場合も同様に、そのまま3つの
値を持つノードにする
–  差し込みたい値に位置するノードが3つの値を持つ場合、3つの値を持つ節を2つ
に分割し、真ん中のキーを親に渡す。その上で差し込みたいノードを差し込む
–  例: Gを追加
ER
AAC
GHIN
EIR
S
AAC
GH
N
S
2-‐3-‐4木 (Cont.)
•  3つの値を持つノードに更に値を加える場合、親のノードを操作する必要がある。 –  親のノードを操作すると、親が3つの値を既にもつ場合に問題が発生する。 •  探索する時に3つの値を持つノードを発見したら、予め分割しておく。 •  実験研究的には分割の発生回数はごく少数回である。 •  また、木の操作において多くの特別なケースが存在するので大半のプログラミン
グ言語において比較的実装が難しい。
演習①
•  Eを追加してみよう
EIR
AAC
GH
N
S
演習①
I
•  Eを追加してみよう
EIR
AAC
GH
R
E
N
S
AAC
GH
N
S
演習①
I
•  Eを追加してみよう
EIR
AAC
GH
R
E
N
S
AAC
GH
N
S
I
R
E
AAC
EGH
N
S
赤黒木 (Red-‐Black tree)
•  2-‐3-‐4木は、少なくとも一種類以上の赤黒木に変換可能である。 –  3つの要素を持つノードの場合は真ん中の値を要素にもつ黒ノードを作成し、それ以外
の要素を作成したノードの子ノードとして生成し色を赤とする。 –  2つの要素を持つノードの場合は、どちらかの要素を持つノードを作成し色を黒とし、もう
片方の要素はそのノードの子ノードとし色を赤とする。 –  最後に葉以外の全てのノードが子どもを2つ持つように黒の葉を付与することで赤黒木
を作成できる。
演習②
•  次の2-‐3-‐4木を赤黒木に変換してみよう
I
AEG
A
AC
NR
EE
H
LM
P
SX
演習②
•  次の2-‐3-‐4木を赤黒木に変換してみよう
I
AEG
A
NR
AC
EE
H
LM
P
SX
I
E
A
A
R
G
C
A
N
E
E
H
M
L
P
X
S
演習③
•  赤黒木を2-‐3-‐4木に変換してみよう。
演習③
•  赤黒木を2-‐3-‐4木に変換してみよう。
8,13,17
1,6
11
15
22,25,27
赤黒木 (Red-‐Black tree)
•  探索 –  単なる二分木と同じ •  挿入 –  一般的にはコストは低い。 –  回転を伴うような場合がある。
演習②’
•  次の2-‐3-‐4木を赤黒木に変換してみよう I
I
E
AEG
A
AC
NR
EE
H
LM
P
A
SX
A
G
C
A
•  回転させてみよう
R
N
E
E
H
M
L
P
R
S
演習②’
•  次の2-‐3-‐4木を赤黒木に変換してみよう I
I
E
AEG
A
AC
NR
EE
H
LM
P
A
SX
N
R
G
C
N
E
A
H
M
E
P
X
S
L
•  回転させてみよう
I
E
A
N
R
G
C
A
N
E
E
H
M
L
P
X
S
演習②’
•  次の2-‐3-‐4木を赤黒木に変換してみよう I
I
E
AEG
A
AC
NR
EE
H
LM
P
A
SX
N
R
G
C
N
E
A
H
M
E
P
X
S
L
•  回転させてみよう
I
EIR
E
AAC
EGH
MNP
A
SX
N
A
E
L
R
G
C
A
N
E
E
H
M
L
P
X
S

Download Report