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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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/3) 60 40 80 50 70 30 90 20 100 0 10 5 15 40 60 80 60 40 50 80 60 40 60 30 40 50 70 80 90 30 20 50 70 80 90

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

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

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

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

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

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

3 (5/8) 20 5 30 10 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

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

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

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

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

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 の処理をする。

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

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

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

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

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

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

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

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

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)

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 の処理をする。