目次：プログラミング学習
前回はノードを作成しました。 今回は二分探索木の操作をするためのコードを書いていきます。
構造
1
2
3
4
#[derive(Default, Debug)]
struct BSTree {
root: OBNode,
}
メンバーが一つだけの構造です。
初期化
1
2
3
4
5
6
7
impl BSTree {
fn new() -> BSTree {
BSTree {
..Default::default()
}
}
}
new() は self を引数にとらず関連関数として定義しています。ここで BSTree のインスタンスを作成しています。
BSTree は #[derive(Default)] によって Default トレイとが実装されているので、初期値を簡単に設定することができます。
1
let tree = BSTree::new();
1
2
3
BSTree {
root: None,
}
Option<T> 型の初期値は None ですので、root には None が設定されています。
操作
- 挿入
- 探索
- 削除
これらの操作は関連関数ではなくメソッドとして BSTree 定義します。
挿入
二分探索木の構造の制約 左の子の値 ≤ 親の値 ≤ 右の子の値 を実装します。
この制約を 左の子の値 < 親の値 ≤ 右の子の値 として挿入する値が親の値と同じ場合は右の子に挿入するようにします。
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
use std::cmp::Ordering::*;
impl BSTree {
pub fn insert(&mut self, data: Data) {
// self.root から値を取り tmp に代入、self.root には None を設定
// tmp の所有権が move している
let mut tmp = self.root.take();
// &mut tmp のところに、&mut self.root にするとビルドエラーになる
// self._insert() が先に self を使用しているので、
// self.root とする self が使用中であるためビルドエラーになる
self._insert(&mut tmp, data);
// self._insert メソッド内で tmp が更新されている
// self.root に tmp を戻す(move)
self.root = tmp;
}
fn _insert(&mut self, node: &mut OBNode, data: Data) {
// node.take() によって node には None が設定される
// match 式の返り値を node に戻している
// match 式の中で値の挿入操作を行う
*node = match node.take() {
Some(mut boxed_node) => {
// node に値が設定されている場合は、その値と比較し左右どちらかに値を挿入する
match data.cmp(&boxed_node.data) {
Less => {
// 挿入しようとしている値が、node の値よりも小さい
// 左ノードに値を挿入する
self._insert(&mut boxed_node.left, data);
// node に値を戻す
Some(boxed_node)
}
Equal | Greater => {
// 挿入しようとしている値が、node の値と等しい、もしくは大きい
// 右ノードに値を挿入する
self._insert(&mut boxed_node.right, data);
// node に値を戻す
Some(boxed_node)
}
}
}
// node の値が None の場合は新しく Node インスタンスを作成して返す
None => BSTree::new_node(data),
}
}
}
match 式の返り値は Option<Box<Node>>型にしたいので、Box<Node> 型の boxed_node を Option<Box<Node>> になるように Some(boxed_node) としています。
1
2
3
4
5
fn main() {
let mut tree = bstree::BSTree::new();
tree.insert(8);
println!("{:#?}", tree);
}
1
2
3
4
5
6
7
8
9
10
$ cargo run
BSTree {
root: Some(
Node {
data: 8,
left: None,
right: None,
},
),
}
ページのトップにあるツリー画像のように値を挿入していきます。
let list = [8, 3, 10, 1, 6, 14, 4, 7, 13]; この順番で値を挿入すればページトップのツリー画像のようになります。
3 を挿入します.
1
2
3
4
5
6
fn main() {
let mut tree = bstree::BSTree::new();
tree.insert(8);
tree.insert(3);
println!("{:#?}", tree);
}
fn _insert(&mut self, node: &mut OBNode, data: Data) この中で親の値と比較しています。
すでに 8 が挿入されているので、8 と 3 を比較します。 3 は 8 より小さいので左ノードに挿入します。
1
fn _insert(左ノード, 3)
左ノードは None ですので、新しいノードを作成しています。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
BSTree {
root: Some(
Node {
data: 8,
left: Some(
Node {
data: 3,
left: None,
right: None,
},
),
right: None,
},
),
}
10 を挿入します。 8 より大きいので右に挿入します。右ノードは None なので、新しいノードを作成します。
1 を挿入します。8 より小さいので左に挿入します。 左ノードは 3 です。3 より小さいので左ノードに挿入します。 3 の左ノードは None ですので、新しいノードを作成します。
6 を挿入します。8より小さいので左に挿入します。 左ノードは 3 です。3 より大きいので右に挿入します。 3 の右ノードは None ですので、新しいノードを作成します。
残りの 14, 4, 7, 13 も順番に挿入します。
昇順ソートされた値を順番に挿入していくと一直線となってしまい探索効率が悪くなります。
記事が長くなるので分割します。他の記事は下記ページをご覧ください。
目次：プログラミング学習
所感
私は rust 入門者です。JavaScript だったらこう書くのにと思いながら多くのエラーと格闘しながらコードを書きました。 最初にやろうとしたことはフローチャートを描句ことだったのですが、その前にツリーの絵を描きました。値の挿入はどのように動いているのかを画像で理解して、 次にフローチャートだと思ったおですが、値の挿入が左なのか右なのかということだけだったのでフローチャートは書きませんでした。 挿入操作以外も実装して所有権関連が一番引っかかったと思います。所有権さえ理解できれば rust は難しく無いのではとも思いました。
このページで紹介している画像はコードを書いた後に作成したものです。コードを書く前は None は書いていませんでした。null チェックで良いだろうと考えてしまっていたので、、、