1 T 行きがけ順： A B D F I J C G H 通りがけ順： D B I F J A G C H

Presentation on theme: "1 T 行きがけ順： A B D F I J C G H 通りがけ順： D B I F J A G C H"— Presentation transcript:

1 1 T 行きがけ順： A B D F I J C G H 通りがけ順： D B I F J A G C H
通りがけ順： D B I F J A G C H 帰りがけ順： D I J F B G H C A

2 1 T 行きがけ順： A B D F I J C G H 通りがけ順： D B I F J A G C H
通りがけ順： D B I F J A G C H 帰りがけ順： D I J F B G H C A

3 1 T 行きがけ順： A B D F I J C G H 通りがけ順： D B I F J A G C H
通りがけ順： D B I F J A G C H 帰りがけ順： D I J F B G H C A

4 1 T 行きがけ順： A B D F I J C G H 通りがけ順： D B I F J A G C H
通りがけ順： D B I F J A G C H 帰りがけ順： D I J F B G H C A

5 1 T 行きがけ順： A B D F I J C G H 通りがけ順： D B I F J A G C H
通りがけ順： D B I F J A G C H 帰りがけ順： D I J F B G H C A

6 1 T 行きがけ順： A B D F I J C G H 通りがけ順： D B I F J A G C H
通りがけ順： D B I F J A G C H 帰りがけ順： D I J F B G H C A

7 1 T 行きがけ順： A B D F I J C G H 通りがけ順： D B I F J A G C H
通りがけ順： D B I F J A G C H 帰りがけ順： D I J F B G H C A

8 1 T 行きがけ順： A B D F I J C G H 通りがけ順： D B I F J A G C H
通りがけ順： D B I F J A G C H 帰りがけ順： D I J F B G H C A

9 1 T 行きがけ順： A B D F I J C G H 通りがけ順： D B I F J A G C H
通りがけ順： D B I F J A G C H 帰りがけ順： D I J F B G H C A

10 1 T 行きがけ順： A B D F I J C G H 通りがけ順： D B I F J A G C H
通りがけ順： D B I F J A G C H 帰りがけ順： D I J F B G H C A

11 1 T 行きがけ順： A B D F I J C G H 通りがけ順： D B I F J A G C H
通りがけ順： D B I F J A G C H 帰りがけ順： D I J F B G H C A

12 1 T 行きがけ順： A B D F I J C G H 通りがけ順： D B I F J A G C H
通りがけ順： D B I F J A G C H 帰りがけ順： D I J F B G H C A

13 1 T 行きがけ順： A B D F I J C G H 通りがけ順： D B I F J A G C H
通りがけ順： D B I F J A G C H 帰りがけ順： D I J F B G H C A

14 1 T 行きがけ順： A B D F I J C G H 通りがけ順： D B I F J A G C H
通りがけ順： D B I F J A G C H 帰りがけ順： D I J F B G H C A

15 1 T 行きがけ順： A B D F I J C G H 通りがけ順： D B I F J A G C H
通りがけ順： D B I F J A G C H 帰りがけ順： D I J F B G H C A

16 1 T 行きがけ順： A B D F I J C G H 通りがけ順： D B I F J A G C H
通りがけ順： D B I F J A G C H 帰りがけ順： D I J F B G H C A

17 1 T 行きがけ順： A B D F I J C G H 通りがけ順： D B I F J A G C H
通りがけ順： D B I F J A G C H 帰りがけ順： D I J F B G H C A

18 2 (1/3) 60 40 50 80 60 40 60 30 20 50

19 2 (2/3) 20 30 50 70 90 100 60 40 80 20 30 50 70 90 100

20 2 (3/3) 60 20 40 80 5 10 30 50 70 90 100 60 80 10 15 30 50 70 90 100

21 3 (1/8) 20 60 10 30 50 70 5 15 25 35 45 55 65 75

22 3 (2/8) 25 60 10 30 50 70 5 15 20 35 45 55 65 75

23 3 (3/8) 25 60 10 30 50 70 5 15 35 45 55 65 75

24 3 (4/8) 25 60 10 35 50 70 5 15 30 45 55 65 75

25 3 (5/8) 35 60 10 25 50 70 5 15 30 45 55 65 75 35 60 10 25 50 70 15 30 45 55 65 75

26 3 (6/8) 35 60 25 50 70 10 15 30 45 55 65 75 60 70 10 15 30 45 55 65 75

27 3 (7/8) 60 70 10 15 45 55 65 75 60 70 10 25 45 55 65 75

28 3 (8/8) 60 70 25 45 55 65 75 60 35 50 70 15 25 45 55 65 75

29 4 01: RB-INSERT(T,x) 02: TREE-INSERT(T,x) 03: color [x ] ← RED
04: while x ≠ root [T ] and color [p [x ]] = RED 05: do if p [x ] = left [p [p [x ]]] 06: then y ← right [p [p [x ]]] 07: if color [y ] = RED 08: then <Case 1> 09: else 10: if x = right [p [x ]] 11: then <Case 2> 12: <Case 3> 13: else <“then” clause with “left ” and “right ” swapped> 14: color [root [T ]] ← BLACK

30 4.1 x 10 22 7 26 05: 06-08: 09-12: 挿入したノードの親ノードが祖父ノードの左ノードの時以下の処理をする。
01: RB-INSERT(T,x) 02: TREE-INSERT(T,x) 03: color [x ] ← RED 04: while x ≠ root [T ] and color [p [x ]] = RED 05: do if p [x ] = left [p [p [x ]]] 06: then y ← right [p [p [x ]]] 07: if color [y ] = RED 08: then <Case 1> 09: else 10: if x = right [p [x ]] 11: then <Case 2> 12: <Case 3> 13: else <“then” clause with “left ” and “right ” swapped> 14: color [root [T ]] ← BLACK 10 22 7 x 26 05: 06-08: 09-12: 挿入したノードの親ノードが祖父ノードの左ノードの時以下の処理をする。 親ノードの兄弟ノードが赤ノードならば Case 1 の処理をする。 親ノードの兄弟ノードが黒ノードで挿入したノードが親ノードの右ノードならばCase 2 の処理の後 Case 3 の処理をする。挿入したノードが親ノードの左ノードならば Case 3 の処理をする。

31 4.2 (1/3) <Case 1> recolor 22 22 7 35 7 35 10 26 36 10 26 36 30

32 4.2 (2/3) <Case 2> left-rotate 40 40 22 42 35 42 7 35 22 36 10
26 36 7 26 30 10 30

33 4.2 (3/3) <Case 3> right-rotate 40 35 35 42 22 40 22 36 7 26 36
10 30 10 30

34 5 G(V, E) A B E F G C D

35 5.1 G(V, E) A B E F G C D

36 5.1 G(V, E) A B E F G C D

37 5.2 G(V, E) A B E F G C D

38 5.3 A C B F G E D G(V, E)

39 6 11: Algorithm DFS(G, v) 01: Algorithm DFS(G)
Red-Black Trees 19/1/12 3時7分 6 01: Algorithm DFS(G) 02: Input graph G 03: Output labeling of the edges of G 04: as discovery edges and back edges 05: for all u ∈ G.vertices() 06: setLabel(u, UNEXPLORED) 07: for all e ∈ G.edges() 08: setLabel(e, UNEXPLORED) 09: for all v ∈ G.vertices() 10: if getLabel(v) = UNEXPLORED 11: DFS(G, v) 11: Algorithm DFS(G, v) 12: Input graph G and a start vertex v of G 13: Output labeling of the edges of G 14: in the connected component of v 15: as discovery edges and back edges 16: setLabel(v, VISITED) 17: for all e ∈ G.incidentEdges(v) 18: if getLabel(e) = UNEXPLORED 19: w ← opposite(v,e) 20: if getLabel(w) = UNEXPLORED 21: setLabel(e, DISCOVERY) 22: DFS(G, w) 23: else 24: setLabel(e, BACK)

40 6 17: 18: 19-22: 23-24: 挿入したノードの親ノードが祖父ノードの左ノードの時以下の処理をする。
Red-Black Trees 19/1/12 3時7分 6 01: Algorithm DFS(G) 02: Input graph G 03: Output labeling of the edges of G 04: as discovery edges and back edges 05: for all u ∈ G.vertices() 06: setLabel(u, UNEXPLORED) 07: for all e ∈ G.edges() 08: setLabel(e, UNEXPLORED) 09: for all v ∈ G.vertices() 10: if getLabel(v) = UNEXPLORED 11: DFS(G, v) 11: Algorithm DFS(G, v) 12: Input graph G and a start vertex v of G 13: Output labeling of the edges of G 14: in the connected component of v 15: as discovery edges and back edges 16: setLabel(v, VISITED) 17: for all e ∈ G.incidentEdges(v) 18: if getLabel(e) = UNEXPLORED 19: w ← opposite(v,e) 20: if getLabel(w) = UNEXPLORED 21: setLabel(e, DISCOVERY) 22: DFS(G, w) 23: else 24: setLabel(e, BACK) 17: 18: 19-22: 23-24: 挿入したノードの親ノードが祖父ノードの左ノードの時以下の処理をする。 親ノードの兄弟ノードが赤ノードならば Case 1 の処理をする。 親ノードの兄弟ノードが黒ノードで挿入したノードが親ノードの右ノードならばCase 2 の処理の後 Case 3 の処理をする。挿入したノードが親ノードの左ノードならば Case 3 の処理をする。