目次：プログラミング学習

プログラミングを学習することを目的に、今回は二分探索木（にぶんたんさくぎ）のノードを実装します。ノードは再帰的構造になるので、いくつか罠があります。

構造

二分探索木はデータ構造の一つです。構造は二分木と同じですが、左の子の値　≤ 親の値 ≤ 右の子の値 という制約があります。

• １つのノードは２つ子を持つ
• ２つの子は 左の子の値　≤ 親の値 ≤ 右の子の値 という制約がある

上図の一番上にある 8 の二つの子は左が 3、 右が 10 となっていて、制約 左の子の値　≤ 親の値 ≤ 右の子の値 を満たします。 3 の二つの子は左が 1、右が 6 となっていて、他のノードを見ても制約を満たすように配置されています。

ノード

Node は値と左、右の子を持ちます。構造を定義する時点では制約を気にする必要はありません。

1
2
3
4
5
struct Node {
    data: i64,
    left: Node,
    right: Node,
}

JavaScript に慣れていると、こんなコードを書きたくなります。これはビルドすることができません。

この構造体は lett, right は Node 型の値を持つと定義しています。rust には null というのがありませんので、left, right は必ず Node 型の値を設定しなければなりません。Node 型はサイズは 0 ではないためデータサイズが無限に発散してします。 そのため、このコードはビルドをすることができません。

1
2
3
4
5
6
7
8
9
10
11
12
error[E0072]: recursive type `Node` has infinite size
  --> src/main.rs:13:1
   |
13 | struct Node {
   | ^^^^^^^^^^^ recursive type has infinite size
14 |     data: i64,
15 |     left: Node,
   |           ---- recursive without indirection
   |
help: insert some indirection (e.g., a `Box`, `Rc`, or `&`) to make `Node` representable
   |
15 |     left: Box<Node>,

コンソールには Box<Node> にすればいいよ、みたいなことが出力されていますが、これもビルドできません。

1
2
3
4
5
struct Node {
    data: i64,
    left: Box<Node>,
    right: Box<Node>,
}

left, right に Box 型の値を必ず設定しなければなりません。Box<Node> 型の初期値を作るために Node 型の値が必要になります。結局、これも無限に続くことになります。

1
2
3
4
5
6
#[derive(Default, Debug)]
struct Node {
    data: i64,
    left: Option<Node>,
    right: Option<Node>,
}

Option 型であれば、None と Some(Node) のどちらかの値を設定すればよく、初期値は None にすれば Node の初期化が必要なさそうです。

1
2
3
4
5
6
7
8
9
10
11
12
13
error[E0072]: recursive type `Node` has infinite size
  --> src/main.rs:13:1
   |
13 | struct Node {
   | ^^^^^^^^^^^ recursive type has infinite size
14 |     data: Data,
15 |     left: Option<Node>,
   |           ------------ recursive without indirection
   |
help: insert some indirection (e.g., a `Box`, `Rc`, or `&`) to make `Node` representable
   |
15 |     left: Box<Option<Node>>,
   |           ^^^^            ^

これもサイズが無限に発散するということでビルドエラーとなります。お勧めされている Box<Option<Node>> は罠です。

Option を使用しても Some(Node) のサイズが分からず、無限に続く可能性があるためビルドエラーとなります。つまり、サイズがわかっていればビルドエラーにはなりません。 Box はサイズがわかっています。

1
2
3
4
5
6
#[derive(Default, Debug)]
struct Node {
    data: i64,
    left: Option<Box<Node>>,
    right: Option<Box<Node>>,
}

これで、Node を初期化するとき left, right の初期値は None を設定すればよく、Box の初期化で Node 型の値が必要という罠から抜け出すことができました。

しかし、Option<Box<Node>> これを あちこちに書くのは面倒です。（個人的な感想です）type を使って別名にしてしまおうと考えました。

1
2
3
4
5
6
7
8
9
type OBNode = Option<Box<Node>>;
type Data = i64;

#[derive(Default, Debug)]
struct Node {
    data: Data,
    left: OBNode,
    right: OBNode,
}

最終的に、Node は上記のようにしました。制約を考慮したメンバー名にするならば

1
2
3
4
5
struct Node {
    data: Data,
    less: OBNode,
    grater: OBNode,
}

less, grater という名前にしてもいいかもしれませんね。私の場合は二分木の構造を図で考えると left, right の方が分かりやすいと思いました。検索しても left, right で書かれてるので、、、

None も含めると下図のようになります。

参考

• 二分探索木 - Wikipedia
• type
  • 型エイリアス
  • 型を変更する際に一箇所の修正で済む。
  • Advanced Types - The Rust Programming Language
• Option
  • None, Some(_) でデータの有無を表す。
  • std::option::Option - Rust
• Box
  • データを操作するためにスタックではなくヒープに割り当てる。
  • std::boxed::Box - Rust
• struct
  • 構造体
  • struct - Rust
• derive
  • Derive - The Rust Reference
• Default
  • 構造体初期化の際に Default 値を設定したい
  • std::default::Default - Rust
• Debug
  • println! マクロなどで データをコンソールに出力したい
  • std::fmt::Debug - Rust