Rustの特徴のひとつは、所有権(ownership)・移動(move)・借用(borrow)の概念です。これらがコンパイル時に厳格にチェックされることにより、古くから未定義挙動でプログラマを悩ませてきたダングリングポインタなどの問題がなくなり、メモリ安全性がもたらされます。
しかし一方で、自分で多少複雑なデータ構造を定義しようとする場合にはコンパイルを通すだけでもかなりの知識・力量が要求されます。
この（不定期）連載では、 Rustではじめるデータ構造とアルゴリズム と題し、プログラミングコンテストなどでよく見かける基礎的なデータ構造とアルゴリズムを、できるだけシンプルにRustで実装していきます。 &, &mut, Box, Rc, Cell, RefCell などの使い分けや、なぜそれを使う必要があるかの解説を、実例を通して行います。
第1回は、最もシンプルな木構造である 二分木 を取り扱います。基礎的な木構造なので、再帰・深さ優先探索・幅優先探索のエッセンスを集中的に理解することが期待できます。
各回共通し、以下のような構成を予定しています。
- データ構造の説明と、Rustでの定義
- 関連するアルゴリズムの説明と、（汎用的に実装できる場合は）Rustでの実装
- 定義したデータ構造とアルゴリズムを使って、プログラミングコンテストの問題を解いてみる
連載記事一覧
- 二分木 （この記事）
- 二分探索木
- 平衡二分探索木 （未執筆）
- ヒープ （未執筆）
- 有向グラフ（ポインタ表現） （未執筆）
- 有向グラフ（行列表現） （未執筆）
- 無向グラフ（ポインタ表現） （未執筆）
- 無向グラフ（行列表現） （未執筆）
目次
更新履歴
- 2020/01/01
- 2019/12/31
- 2019/12/29
二分木の説明
二分木は木構造の一種で、1つのノード（節点）が、0~2個の子ノードを持つものを指します。
バランスの良い二分木1
2
3
4
5
6
7
8
| 2
__/ \__
/ \
7 5
/ \ \
2 6 9
/ \ /
5 11 4
|
上の図のように、ルート（根: 親ノードを持たないノード）からリーフ（葉: 子ノードを持たないノード）までの深さがどこをとってもだいたい同じものを平衡二分木と言いますが、下のように深さがバラバラなものも二分木です。
バランスの悪い二分木
この記事では平衡二分木ではなく、一般の二分木について扱います。
Rustで定義する二分木
二分木の定義はどのように行うのが良いでしょうか？
木構造の定義の方法は、大まかに
- 子が親への参照（1つ）を持つ
- 親が子への参照（複数）を持つ
と分けられるかと思います。
前者の「子が親への参照を持つ」は二分木の定義に適していません。
間違った二分木の定義（擬似コード）1
2
3
| struct BinaryTree {
parent: Option<BinaryTree>
}
|
この定義では、「親は子を2つ以下しか持たない」という制約が表現できていません。「子が親を参照するタイミングで、親がこの個数をカウントして、2個までしか認めないようにする」というような実装は可能ですが、あまり自然でもないしランタイムでのチェックが必要になってしまいます。
「親が子への参照を持つ」形式だと、「親は子を2つ以下しか持たない」制約を型レベルで（コンパイルタイムに）強制することができます。
二分木の定義（Optionを使う, 擬似コード）1
2
3
4
| struct BinaryTree {
left: Option<BinaryTree>,
right: Option<BinaryTree>,
}
|
だいぶ良くなってきました。ここで Option は、子の有無を表現するために使用しています。この定義でも十分実用に耐えますが、この有無を組み込みの型で表現するのではなく自前で定義すると、次のように定義できます。
二分木の定義（enumを使う, 擬似コード）1
2
3
4
| enum BinaryTree {
Nil,
Node { left: BinaryTree, right: BinaryTree }
}
|
さて、これで二分木の外形は定義できましたが、各ノードが値を持てるようになっていません。各ノードが任意の型 T の値を持てるようにした完全な定義が下記になります。
二分木の定義1
2
3
4
5
6
7
8
9
| #[derive(Debug, PartialEq, Eq)]
pub enum BinaryTree<T> {
Nil,
Node {
val: T,
left: Box<BinaryTree<T>>,
right: Box<BinaryTree<T>>,
},
}
|
いくつか飛躍があるので説明しておきます。
#[derive(Debug, PartialEq, Eq)]
assert_eq!(BinaryTree { ... }, BinaryTree { ... }) のように比較したいので、いくつかのTraitの実装を使う。
pub
- BinaryTree を定義したモジュールの外でも使いたいので公開する。
Box<BinaryTree<T>> （重要）
left: BinaryTree<T> のように書きたくなるが、これでは再帰的な型定義となってしまい、 BinaryTree 型のサイズが確定できない（「 BinaryTree のサイズは… val のバイト数と、 left の BinaryTree のサイズを足して… ってそれを今計算してるのに😫」）。これを回避するために、”BinaryTree 型へのポインタ型” としてサイズが確定できるよう Box に包む。
これで二分木の型定義ができました。これからこの二分木に対する構築・追加・削除の操作や、深さ優先探索・幅優先探索のアルゴリズムを記述していきます。その後、実応用（？）として、いくつか LeetCode の問題を解いていきます。
データ構造への基本的な操作とアルゴリズム
構築
二分木の構築は、定義したenumを使って素直に初期化をするだけです。
構築1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
|
let root = BinaryTree::<i32>::Node {
val: 5,
left: Box::new(BinaryTree::<i32>::Node {
val: 4,
left: Box::new(BinaryTree::<i32>::Node {
val: 11,
left: Box::new(BinaryTree::Nil),
right: Box::new(BinaryTree::Nil),
}),
right: Box::new(BinaryTree::Nil),
}),
right: Box::new(BinaryTree::<i32>::Node {
val: 8,
left: Box::new(BinaryTree::Nil),
right: Box::new(BinaryTree::Nil),
}),
};
|
このように見た目が煩雑になってしまうので、構築用の new マクロを用意します。マクロ定義の方法は本記事の範疇を超えるので読み飛ばして良いですが、 bin_tree! マクロはこれ以降出てくるので、使い方だけでも把握してください。
構築用のマクロ定義1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
| #[macro_export]
macro_rules! bin_tree {
( val: $val:expr, left: $left:expr, right: $right:expr $(,)? ) => {
BinaryTree::Node {
val: $val,
left: Box::new($left),
right: Box::new($right),
}
};
( val: $val:expr, right: $right:expr $(,)? ) => {
bin_tree! {
val: $val,
left: bin_tree!(),
right: $right,
}
};
( val: $val:expr, left: $left:expr $(,)? ) => {
bin_tree! {
val: $val,
left: $left,
right: bin_tree!(),
}
};
( val: $val:expr $(,)? ) => {
bin_tree!(val: $val, left: bin_tree!(), right: bin_tree!(),)
};
() => {
BinaryTree::Nil
};
}
|
bin_tree! マクロの使い方1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
let root = bin_tree! {
val: 5,
left: bin_tree! {
val: 4,
left: bin_tree! { val: 11 },
},
right: bin_tree! { val: 8 },
};
|
追加（置き換え）
子ノードの追加を考えます。これは、「左または右の子ノードが Nil であるときに、それを Node に置き換える」操作として記述できます。
Node が1つのノードでなくサブツリーのルートであれば、二分木に二分木を追加することになります。
汎用性の高い操作なので、メソッドとして定義しましょう。
追加（置き換え）1
2
3
4
5
6
7
| impl<T> BinaryTree<T> {
pub fn replace(&mut self, to: Self) {
*self = to;
}
}
|
テストしてみます。
replace() のテスト1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
| #[test]
fn test_replace() {
let mut tree1 = bin_tree! {
val: 5,
left: bin_tree! {
val: 4,
left: bin_tree! {
val: 11,
left: bin_tree! { val: 7 },
right: bin_tree! { val: 2 },
},
},
};
let tree2 = bin_tree! {
val: 8,
left: bin_tree! { val: 13 },
right: bin_tree! {
val: 4,
right: bin_tree! { val: 1 },
},
};
let tree3 = bin_tree! {
val: 5,
left: bin_tree! {
val: 4,
left: bin_tree! {
val: 11,
left: bin_tree! { val: 7 },
right: bin_tree! { val: 2 },
},
},
right: bin_tree! {
val: 8,
left: bin_tree! { val: 13 },
right: bin_tree! {
val: 4,
right: bin_tree!{ val: 1 },
},
},
};
if let BinaryTree::Node { right, .. } = &mut tree1 {
(**right).replace(tree2);
}
assert_eq!(&tree1, &tree3);
}
|
削除
先程の replace() 関数を使って素直に実装できますね。
削除1
2
3
4
5
6
| impl<T> BinaryTree<T> {
pub fn remove(&mut self) {
self.replace(BinaryTree::Nil);
}
}
|
深さ優先探索
深さ優先探索は、再帰関数を使うことで簡潔に実装することができます。1回1回の関数呼び出しであるノードを探索し、その中で左右の子ノードについても同じ関数を呼び出して探索します。
以下、二分木の中から 13 という値を探す再帰関数を擬似コードで記載します（コンパイルできるコードは下記の応用編で出てきます）。
13 を深さ優先探索で探す再帰関数（擬似コード）1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
| fn find_13(cur_node: BinaryTree) -> bool {
if cur_node.val == 13 { return true; }
if cur_node.left != Nil {
if find_13(cur_node.left) { return true; }
}
if cur_node.right != Nil {
if find_13(cur_node.right) { return true; }
}
false
}
let root = ...;
assert!(find_13(root));
|
幅優先探索
幅優先探索は、FIFOなキューに左右の子ノードを順にpushしていき、それをpopしていくループによって実現できます。再帰を使った深さ優先探索のほうが直感的に記述できることが多いですが、以下のような場合は幅優先探索の利用を検討してみましょう。
- 二分木の中に答えを持つノードがいくつかあるが、深さが最も小さいノードを選択するのが重要なとき（最短経路問題）。
- 再帰関数を使うとスタック領域を多く使ってしまい、プロセスや言語のランタイムが持つスタック領域の上限を超えてしまう場合。
- この場合は、再帰を使わずに（データ構造としての）スタックとループを使う手もあります。
さて、深さ優先探索で見たのと同じ問題を幅優先探索で解いてみましょう。こちらも擬似コードですが、下記の応用編にコンパイルが通るコードがあります。
13 を幅優先探索で探す関数（擬似コード）1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
| fn find_13(root: BinaryTree) -> bool {
let mut queue = VecDeque::<BinaryTree>::new();
queue.push_back(root);
while let Some(cur_node) = queue.pop_front() {
if cur_node.val == 13 { return true; }
if cur_node.left != Nil { queue.push_back(cur_node.left); }
if cur_node.right != Nil { queue.push_back(cur_node.right); }
}
false
}
let root = ...;
assert!(find_13(root));
|
応用編: LeetCode の問題を解いてみる
説明した操作やアルゴリズムで実際の問題が解決できることを例示するために、 LeetCode から以下の問題を取り上げます。
- 112. Path Sum
- 整数値をノード値に持つ二分木について、ルートからリーフまで値を足し算しながら辿っていき、その和が特定の数になるような辿り方があるかどうかを回答。 構築 と 深さ優先探索 または 幅優先探索 を使う。
- 814. Binary Tree Pruning
- 0 または 1 をノード値に持つ二分木について、すべてのノードが 0 であるようなサブツリーを切り落とす (prune) 操作をする。 構築・削除・深さ優先探索 を使う。
さて、LeetCode の問題のページにアクセスすればわかると思いますが、LeetCode ではRustを使って回答をすることもできます。LeetCode の二分木関連の問題では、二分木として以下の構造を使うことが求められます。
LeetCode で使う二分木1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| #[derive(Debug, PartialEq, Eq)]
pub struct TreeNode {
pub val: i32,
pub left: Option<Rc<RefCell<TreeNode>>>,
pub right: Option<Rc<RefCell<TreeNode>>>,
}
impl TreeNode {
#[inline]
pub fn new(val: i32) -> Self {
TreeNode {
val,
left: None,
right: None
}
}
}
|
Option<Rc<RefCell<TreeNode>>> といういかつい型が出てきました。
一番外側のOptionは、冒頭でも触れたように、子ノードの有無を表します。
（本記事の範疇を超えるので、この段落は読み飛ばしても良いです📝）
Rc<RefCell<...>> は、イディオムのように頻出する型です。Rustにおいて所有権は、通常たった一つの変数（や仮引数など）が持つものですが、Rc (Reference counting の略) を使えば複数の変数が所有権を持つことができるようになります。RefCell は内部可変性を導入するために利用する型です。 mut ではない struct であっても、 RefCell なフィールドだけは可変にできます。Rustにメモリ安全性を導入する「可変参照はたったひとつしか作れない」というコンパイルタイムの原則に対する抜け穴として RefCell があります。これを使うとコンパイルタイムでのメモリ安全性は保証されず、可変参照を2個以上作ったときにランタイムエラーが発生するようになるので、本当にどうしても必要で、かつ制御しきれる程度の仕事しかしない箇所で利用することをお勧めします。
二分木の各ノードを読むだけなら、共有参照で事足りるので、Rc<RefCell> は不要です。二分木をサブツリーに分けて扱い、同じノードに対する可変参照が複数個必要となるケースでは、 Rc<RefCell> が必要になるかもしれません。とはいえ、 Rc<RefCell> を導入する前に制御フローを工夫して、可変参照を1個以内に保てないかをまず検討するべきだと思います。
というわけで、今回は Option<Rc<RefCell<TreeNode>>> は使わず、最初に定義した
二分木の定義1
2
3
4
5
6
7
8
9
| #[derive(Debug, PartialEq, Eq)]
pub enum BinaryTree<T> {
Nil,
Node {
val: T,
left: Box<BinaryTree<T>>,
right: Box<BinaryTree<T>>,
},
}
|
を使います。LeetCodeで求められる型ではないのでSubmitはできませんが、代わりに簡単なテストコードを書いていきます。
112. Path Sum
整数値をノード値に持つ二分木について、ルートからリーフまで値を足し算しながら辿っていき、その和が特定の数になるような辿り方があるかどうかを回答する問題です。
解き方としては、愚直にルートからリーフまで足し算しながら辿っていって、リーフにたどり着いた時点で目指す総和になっていれば true を返せばよいです。
まずは深さ優先探索で回答してみます。テスト実行可能な形式で書いていきます。解説はコード内コメントで。
112. Path Sum - 深さ優先探索1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
| #[test]
fn leetcode_112_path_sum_dfs() {
use BinaryTree::{Nil, Node};
pub fn has_path_sum(root: &BinaryTree<i32>, sum: i32) -> bool {
fn rec(cur_node: &BinaryTree<i32>, cur_sum: i32, sum: i32) -> bool {
match cur_node {
Nil => panic!("cur_node が Nil のときは呼び出さないでください"),
Node { val, left, right } => {
let cur_sum = cur_sum + val;
match (&(**left), &(**right)) {
(Nil, Nil) => cur_sum == sum,
(_, Nil) => rec(&(*left), cur_sum, sum),
(Nil, _) => rec(&(*right), cur_sum, sum),
(_, _) => rec(&(*left), cur_sum, sum) || rec(&(*right), cur_sum, sum),
}
}
}
}
rec(root, 0, sum)
}
let root = bin_tree! {
val: 5,
left: bin_tree! {
val: 4,
left: bin_tree! {
val: 11,
left: bin_tree! { val: 7 },
right: bin_tree! { val: 2 },
},
},
right: bin_tree! {
val: 8,
left: bin_tree! { val: 13 },
right: bin_tree! {
val: 4,
right: bin_tree! { val: 1 },
},
},
};
assert_eq!(has_path_sum(&root, 22), true);
}
|
幅優先探索での回答は以下のように書けます。二分木の構築とassertion部分は省略。
112. Path Sum - 幅優先探索1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
| #[test]
fn leetcode_112_path_sum_bfs() {
use std::collections::VecDeque;
use BinaryTree::{Nil, Node};
pub fn has_path_sum(root: &BinaryTree<i32>, sum: i32) -> bool {
let mut queue = VecDeque::<(&BinaryTree<i32>, i32)>::new();
queue.push_back((root, 0));
while let Some((cur_node, cur_sum)) = queue.pop_front() {
match cur_node {
Nil => {
panic!("Nil を queue に詰めないでください");
}
Node { val, left, right } => {
let cur_sum = cur_sum + val;
match (&(**left), &(**right)) {
(Nil, Nil) => {
if cur_sum == sum {
return true;
}
}
(_, Nil) => queue.push_back((&(*left), cur_sum)),
(Nil, _) => queue.push_back((&(*right), cur_sum)),
(_, _) => {
queue.push_back((&(*left), cur_sum));
queue.push_back((&(*right), cur_sum));
}
}
}
}
}
false
}
}
|
814. Binary Tree Pruning
0 または 1 をノード値に持つ二分木について、すべてのノードが 0 であるようなサブツリーを切り落とす (prune) 操作をする問題です。
素直に思いつくのは、「あるノードをルートとするサブツリーを考え、その全要素を探索し、全て0ならばそのサブツリーを切り落とす」という解法ですが、この方法ではリーフ近くのノードが何回も「0かどうか」チェックされて無駄があります。
“上から下に” ではなく、 “下から上に” 考えてみると、「あるノードがリーフのとき、自分が0ならば、自分自身をNilに置き換える」という解法がとれます。これだと0との比較の回数は、多くても全ノードの数だけになります。
この方針に従って、深さ優先探索で回答します。幅優先探索を使うと “下から上” な処理が書きづらいので、難儀するかと思います。
814. Binary Tree Pruning1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
| #[test]
fn leetcode_814_binary_tree_pruning() {
use BinaryTree::{Nil, Node};
pub fn prune_tree(root: &mut Box<BinaryTree<i32>>) {
match &mut **root {
Nil => {}
Node { val, left, right } => match (&mut **left, &mut **right) {
(Nil, Nil) => {
if *val == 0 {
root.remove();
}
}
(_, Nil) => {
prune_tree(left);
if let Nil = &mut **left {
if *val == 0 {
root.remove();
}
}
}
(Nil, _) => {
prune_tree(right);
if let Nil = &mut **right {
if *val == 0 {
root.remove();
}
}
}
(_, _) => {
prune_tree(left);
prune_tree(right);
if let (Nil, Nil) = (&mut **left, &mut **right) {
if *val == 0 {
root.remove();
}
}
}
},
}
}
let mut tree = Box::new(bin_tree! {
val: 1,
left: bin_tree! {
val: 0,
left: bin_tree! { val: 0 },
right: bin_tree! { val: 0 },
},
right: bin_tree! {
val: 1,
left: bin_tree! { val: 0 },
right: bin_tree! { val: 1 },
},
});
let pruned = bin_tree! {
val: 1,
right: bin_tree! {
val: 1,
right: bin_tree! { val: 1 },
},
};
assert_eq!(
{
prune_tree(&mut tree);
*tree
},
pruned
);
}
|
終わりに
この記事ではRustで二分木をシンプルに定義する方法と、二分木の構築・追加・削除、そして深さ優先探索と幅優先探索を紹介しました。
ただ、実用上ただの二分木はそんなに登場しません😂
しかし二分木は、二分探索木やヒープという、シンプルでありながら適用範囲の広いデータ構造のための基礎です。次回第2回では、二分探索木を紹介していきます。
この記事は FOLIO Advent Calendar 2019 の8日目の記事です。
12/23に8日目、開始は12/16でしょうか？（原稿落とした同僚の代打投稿です）
この遡及穴埋めもあり、どうやらFOLIOは今年もアドベントカレンダーを完走できそうです🎅🎄