2 分探索木 Binary Search Tree 実行可能な操作 計算量 木の高さは，最悪 O(n) n = |A| ： 要素の個数

Presentation on theme: "2 分探索木 Binary Search Tree 実行可能な操作 計算量 木の高さは，最悪 O(n) n = |A| ： 要素の個数"— Presentation transcript:

1 2 分探索木 Binary Search Tree 実行可能な操作 計算量 木の高さは，最悪 O(n) n = |A| ： 要素の個数
2 分木構造を利用したデータ構造 key に線形順序がある要素の集合 A を蓄えている A の要素を，対象順（symmetric order）に点に保存 実行可能な操作 Member( x, A ), Insert( x, A ), Delete( x, A ) Max( A ), Min( A ) Successor( x, A, y ), Predecessor( x, A, y ) Join( A1, x, A2, A ), Split( x, A, A1, A2 ) 計算量 Join 以外 ：　O( 木の高さ ) Join ：　 O(1) 木の高さは，最悪 O(n) n = |A|　：　要素の個数

2 平衡 2 分木 Balanced Binary Tree 平衡 2 分木を用いた 2 分探索木（データ構造） h≤ log 2 n
点の個数が n のとき，高さ h が O(log n) の 2 分木 完全 2 分木（Full Binary Tree） n = 2h+1 - 1 整列 2 分木（Complete Binary Tree） 2h  n < 2h+1 平衡 2 分木を用いた 2 分探索木（データ構造） AVL 木 （Adelson, Velskii, Landis） 各点において，左右の子の高さの差が高々 1 2 色木， （splay 木） h≤ log 2 n

3 AVL 木 ではない木 6 2 8 7 1 3 4 3 1 2 1 -1 -1 AVL 木 2 分木 T 子が無いとき， -1 の高さとする
1 2 8 7 1 1 3 -1 -1 4 子が無いとき， -1 の高さとする 左右の子の高さの差が高々 1

4 平衡 2 分木 Balanced Binary Tree 平衡 2 分木を用いた 2 分探索木（データ構造） h≤ log 2 n
点の個数が n のとき，高さ h が O(log n) の 2 分木 完全 2 分木（Full Binary Tree） n = 2h+1 - 1 整列 2 分木（Complete Binary Tree） 2h  n < 2h+1 平衡 2 分木を用いた 2 分探索木（データ構造） AVL 木 （Adelson, Velskii, Landis） 各点において，左右の子の高さの差が高々 1 2 色木， （splay 木）　 h≤ log 2 n

5 2 色木（Red-Black Tree) 各点に黒あるいは赤の色を付けた 2 分探索木 下記 3 条件を満たす． 1： 根および外点は黒
1：　根および外点は黒 2：　赤点の親は黒 3：　根から外点への経路上の黒点の個数はどれも同じ

6 内点，外点 2 分木 T 内点 ： n 7 2 9 1 3 8 6 外点 ： n+1

7 内点，外点 n 個の内点を持つ 2 分木は， n+1 個の外点を持つ n = 1 のとき n = n’ のとき
根は子を 1 個持つ wlg，左の子と仮定 根は左右の子を持つ ・・・ n'-1 n'

8 内点，外点 k + n'-k+1 = n'+1 n 個の内点 ⇒ n+1 個の外点 n = n’ のとき 根は左右の子を持つ ・・・ k-1
wlg，以下を仮定できる 左の子を根とする部分木は，k-1 個の点を持ち， 右の子を根とする部分木は，n-k 個の点を持つ ・・・ k-1 n'-k k + n'-k+1 = n'+1 k n'-k+1

9 2 色木（Red-Black Tree) 各点に黒あるいは赤の色を付けた 2 分探索木 下記 3 条件を満たす．
1：　根および外点は黒 2：　赤点の親は黒 3：　根から外点への経路上の黒点の個数はどれも同じ 平衡 2 分木になっている．

10 2 色木（Red-Black Tree) 7 2 2 9 1 3 8 8 6 6 2 分木 T 1. 根，外点は黒 2. 赤点の親は黒
3. 根から外点への経路上の黒点の個数は同じ

11 2 色木にできない 2 分木 2 1 9 9 7 7 10 3 3 8 6 6 2 分木 T 経路上の点数 ： ３ ： ６ 黒は 1 個
赤が続く 1 9 9 7 7 10 経路上の点数 　　　：　３ 3 3 8 6 6 　　　：　６ 経路長の比は倍まで

12 2 色木（Red-Black Tree) 2 色木は平衡 2 分木 n  20 + 21 +･･･ + 2d-1 = 2d －1
log2(n+1)  d 経路上の黒点の個数は高々 d+1 経路上の赤点の個数は高々 d 経路上の点の個数は高々 2d+1 木の高さは高々 2d Full d 1 2 d d+1 ･･･  2 log2(n+1)

13 2 色木（Red-Black Tree) 各点に黒あるいは赤の色を付けた 2 分探索木 下記 3 条件を満たす．
1：　根および外点は黒 2：　赤点の親は黒 3：　根から外点への経路上の黒点の個数はどれも同じ 平衡 2 分木になっている． Member などの探索操作は，2 分探索木と同じ． Insert，Delete は，3 条件を満たすように要変更． Join, Split は扱えない．

14 2 色木 （空) 2 色木 T 1, 2, 3, 5, 4 をこの順に Insert

15 1 を Insert 1 １ 1 Insert を行うと，外点が内点に変わる． その内点は，とりあえず赤点にする．
 経路上の黒点の個数は変化しない 根は黒点なので，色を黒に変える．  経路上の黒点の個数が 1 増加

16 2 を Insert 1 2 2 z の親が黒点なら， 2 色木になっている z Insert を行うと，外点が内点に変わる．
経路上の黒点の 個数は変化して いないから z 2 2 Insert を行うと，外点が内点に変わる． その内点は，とりあえず赤点にする． 新たに赤点になった点を z とする

17 3 を Insert 1 2 3 3 w w で単回転 y z の親 x が x 赤のとき， 要修正 z 赤点に なった点 z
　赤のとき， 　要修正 x 2 z 赤点に なった点 z 3 3 Case B1 : 　x の兄弟 y が黒 　x と z が同じ側 経路上の黒点数は同じ

18 3 を Insert．単回転 2 色木 T 1 w y 2 3 x z

19 3 を Insert．単回転 2 1 3 x z w y 2 色木 T z の子へ ： 黒点の個数が 1 減少

20 3 を Insert．単回転 2 色木 T w 1 y x 2 z 3

21 3 を Insert．単回転後 2 2 1 1 3 x x と w の 色変換 z w y 経路上の黒点の個数が同じになる 2 色木 T
1 増加 y へ　：　黒点の個数に変化無し 経路上の黒点の個数が同じになる

22 5 を Insert 2 1 3 5 5 色交換 w x y z 赤になった 点 z Case A : z の親 x x の兄弟 y が赤

23 5 を Insert，色交換 2 2 1 1 3 3 5 色交換 w x y z Case A : x の兄弟 y が赤 根が赤なので，
経路上の 黒点の個数 に変化無し z 5 Case A : 　x の兄弟 y が赤 根が赤なので，

24 5 を Insert．色交換後 2 色木 T 根の色を黒に戻す 2 1 3 5 根から外点への経路上の 黒点の個数が １ 増加

25 4 を Insert 2 1 3 5 4 4 双回転 赤になった w 点 z z の親 x w で単回転 y x Case B2 : z
　x の兄弟 y が黒 　x と z が反対側 z 4 4 x で単回転後

26 4 を Insert，双回転 2 色木 T 双回転 2 w y 3 1 5 x z 4

27 4 を Insert．双回転後 2 1 4 4 3 3 5 w y x z z 経路上の 黒点の 個数が 同じになる z と w の 色変換
黒点の個数に変化無し x の子へ　： 黒点の個数が 1 減少 1 増加

28 2 色木のデータ構造 親は探索時に 覚えておく ポインタが NULL なら外点を指す Color element LeftSon
RightSon 親は探索時に 覚えておく Color element LeftSon RightSon Color element LeftSon RightSon ポインタが NULL なら外点を指す

29 5 を Insert 2 1 8 6 9 3 7 5 5 経路上の黒点数 ： 3 w x y Case A : x の兄弟 y が赤 z
色交換

30 5 を Insert．色交換後 2 1 8 6 6 9 3 3 7 7 5 w 双回転 x y z Case B2 : x の兄弟 y が黒
　x と z が反対側 5

31 5 を Insert，双回転 2 色木 T w 2 x y 1 8 z 6 9 3 7 5

32 双回転後 6 6 2 2 8 1 3 7 9 5 経路上の黒点の個数が同じに z と w の z 色変換 x w y 2 色木 T
黒点の個数に変化無し x の子へ　： 黒点の個数が 1 減少 1 増加

33 Insert の操作 w x y z z の親 x が黒． x が赤で，x の兄弟 y が黒 x が赤で，x の兄弟 y が赤 w x y
何もしない　 x が赤で，x の兄弟 y が黒 Case B1：　x と z が同じ側 w で単回転 → 色の変換 Case B2：　x と z が反対側 双回転 → 色の変換 x が赤で，x の兄弟 y が赤 Case A： 色交換 w x y z w x y z （繰り返し） → Case B1 or B2 　 根に到達

34 Insert の操作 z の親 x が黒． x が赤で，x の兄弟 y が黒 x が赤で，x の兄弟 y が赤
Case B1：　x と z が同じ側 Case B2：　x と z が反対側 x が赤で，x の兄弟 y が赤 Case A：

35 Delete の操作 2 色木 T （6 を Delete） 6 2 8 or 1 3 7 9 5

36 Delete の操作 （5 を移動） 5 2 8 1 3 7 9 2 色木 T 実際に除去される 左の子の子孫中 点の子は高々 1 個
最大の要素 実際に除去される 点の子は高々 1 個

37 実際に除去される点 左右の子のどちらも外点 問題 or 内点の子と外点の子 a a 除去される点は黒． 内点の子は赤で， 　その子は共に外点．

38 黒の内点が外点に 2 色木 T 7 2 8 z 1 3 9 除去 5 黒の内点 z が 外点に変わる z ： 黒点数が 1 減少

39 Case B-1-a 7 2 8 8 1 3 9 9 5 v z w 2 色木 T w ： z の兄弟 w の子が共に黒なら v が赤なら
　完了 v を黒に 　z への黒点数 1 増加 w へも！

40 Delete の操作 v w z Case A： w が赤 x y Case B： w が黒 B-1 ： w の子が共に黒
B-1-a ：　v が赤　：　色の変換で完了 B-1-b ：　v が黒 B-2： w の z から遠い方の子 x が赤 B-3： w の z から近い方の子 y だけが赤 x y

41 Delete の操作 v w z Case A： w が赤 x y Case B： w が黒 B-1 ： w の子が共に黒
B-1-a ：　v が赤　：　色の変換で完了 B-1-b ：　v が黒 B-2： w の z から遠い方の子 x が赤 B-3： w の z から近い方の子 y だけが赤 x y

42 Case B-2 b d d b b d A C E E A C v w v z w x x y z y E ： 黒点数 1 増
　完了 1 増 v b d v w z A C E x y d b z w z ： 黒点数 1 少ない b d x y E A C v で単回転

43 Delete の操作 v w z Case A： w が赤 x y Case B： w が黒 B-1 ： w の子が共に黒
B-1-a ：　v が赤　：　色の変換で完了 B-1-b ：　v が黒 B-2： w の z から遠い方の子 x が赤 v で単回転 → 色の変換で完了 B-3： w の z から近い方の子 y だけが赤 x y

44 Delete の操作 v w z Case A： w が赤 x y Case B： w が黒 B-1 ： w の子が共に黒
B-1-a ：　v が赤　：　色の変換で完了 B-1-b ：　v が黒 B-2： w の z から遠い方の子 x が赤 v で単回転 → 色の変換で完了 B-3： w の z から近い方の子 y だけが赤 x y

45 Case B-3 f b d f d b f d A C G E G A C E y v z v w w y x z x y を v の色に
　完了 f v w z b d A C G x y E v f d z w z ： 黒点数 1 少ない b f y x G d A C E 双回転

46 Delete の操作 v w z Case A： w が赤 x y Case B： w が黒 B-1 ： w の子が共に黒
B-1-a ：　v が赤　：　色の変換で完了 B-1-b ：　v が黒 B-2： w の z から遠い方の子 x が赤 v で単回転 → 色の変換で完了 B-3： w の z から近い方の子 y だけが赤 双回転 → 色の変換で完了 x y

47 Delete の操作 v w z Case A： w が赤 x y Case B： w が黒 B-1 ： w の子が共に黒
B-1-a ：　v が赤　：　色の変換で完了 B-1-b ：　v が黒 B-2： w の z から遠い方の子 x が赤 v で単回転 → 色の変換で完了 B-3： w の z から近い方の子 y だけが赤 双回転 → 色の変換で完了 x y v の子孫全てで， 経路上の黒点数 1 減 ： w を赤に v が新 z → Case A or B

48 Delete の操作 v w z x y Case A： w が赤 Case B： w が黒 B-1 ： w の子が共に黒
B-1-a ：　v が赤　：　色の変換で完了 B-1-b ：　v が黒　：　w を赤，v を新 z → Case A or B B-2： w の z から遠い方の子 x が赤 v で単回転 → 色の変換で完了 B-3： w の z から近い方の子 y だけが赤 双回転 → 色の変換で完了

49 Case A : w が赤 b d d b b d A C E E A C v w z w v z w を黒， v を赤に
→ Case B へ v は赤 Case B-1-b 以外 v b d v z A C E w d b z w z ： 黒点数 1 少ない b E d A C v で単回転

50 Delete の操作 Case A： w が赤 Case B： w が黒 B-1 ： w の子が共に黒
v で単回転 → 色の変換 → Case B （B-1-b 以外）　 Case B： w が黒 B-1 ： w の子が共に黒 B-1-a ：　v が赤　：　色の変換で完了 B-1-b ：　v が黒　：　w を赤，v を新 z → Case A or B B-2： w の z から遠い方の子 x が赤 v で単回転 → 色の変換で完了 B-3： w の z から近い方の子 y だけが赤 双回転 → 色の変換で完了

51 Delete の操作 Case A： w が赤 Case B： w が黒 B-1 ： w の子が共に黒
高々 3 回の単回転 Case A：　w が赤 v で単回転 → 色の変換 → Case B （B-1-b 以外）　 Case B： w が黒 B-1 ： w の子が共に黒 B-1-a ：　v が赤　：　色の変換で完了 B-1-b ：　v が黒　：　w を赤，v を新 z → Case A or B B-2： w の z から遠い方の子 x が赤 v で単回転 → 色の変換で完了 B-3： w の z から近い方の子 y だけが赤 双回転 → 色の変換で完了 必ず完了