Presentation is loading. Please wait.

Presentation is loading. Please wait.

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

Similar presentations


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 経路上の点数 : 3 : 6 黒は 1 個
赤が続く 1 9 9 7 7 10 経路上の点数    : 3 3 3 8 6 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 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 根から外点への経路上の 黒点の個数が 1 増加

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 だけが赤 双回転 → 色の変換で完了 必ず完了


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

Similar presentations


Ads by Google