目次：プログラミング学習
前回は挿入操作を実装しました。 今回は二分探索木の操作、探索をするためのコードを書いていきます。
探索
二分探索木の構造の制約 「左の子の値 ≤ 親の値 ≤ 右の子の値」から探索を検討します。
- root から探索を開始し、対象ノードの値と検索値を比較します。
- 同じであれば探索終了
- 探索値の方が小さければ左ノードを探索します
- 探索値の方が大きければ右ノードを探索します
- 探索するノードがなければ None を返します
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
use std::cmp::Ordering::*;
impl BSTree {
pub fn find(&self, data: Data) -> &OBNode {
// root から探索を開始する
self._find(&self.root, data)
}
fn _find<'a>(&self, node: &'a OBNode, data: Data) -> &'a OBNode {
// 'a ライフタイムを指定
// 返却する値はノードへの参照
// 与えられるノードと返却するノードのライフタイムが一致する必要がある
// Data のコピーを返却するのであればライフタイムは気にする必要がなくなる
match node {
Some(boxed_node) => match data.cmp(&boxed_node.data) {
Equal => node, // 探索終了
Less => {
// 探索値の方が小さいので左ノードを探索
return self._find(&boxed_node.left, data);
}
Greater => {
// 探索値の方が大きいので右ノードを探索
return self._find(&boxed_node.right, data);
}
},
None => &None, // 見つからなかった
}
}
}
14 を探索
14 を探索してみます。
返却される値は data=14、left.data=13, right=None となるはずです。（省略して書いてます）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
fn main() {
let data = 14;
let list = [8, 3, 10, 1, 6, 14, 4, 7, 13];
let mut tree = BSTree::new();
for i in 0..list.len() {
tree.insert(list[i]);
}
println!("\n\n=====================\n\n探索：{}", data);
let node = tree.find(data);
println!("探索結果：{:#?}", node);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
$ cargo run
=====================
探索：14
探索結果：Some(
Node {
data: 14,
left: Some(
Node {
data: 13,
left: None,
right: None,
},
),
right: None,
},
)
期待した結果になりました。
- ルートノード（８）から探索を開始します
- 14 は 8 より大きいので右ノード(10)を探索します
- 14 は 10 より大きいので右ノード(14)を探索します
- 14 と 14 が一致したので、このノードを返却します
１２を探索
次に 12 を探索します。12 はツリーに登録されていないので None が返されることを期待します。
1
let data = 12;
1
2
3
4
5
$ cargo run
=====================
探索：12
探索結果：None
期待通り None が返却されました。
- 8 より大きいので右(10)
- 10 より大きいので右(14)
- 14 より小さいので左(13)
- 13 より小さいので左(None)
- ノードが無い(None) なので &None を返却
所感
探索結果の返却値をノードへの参照としたためライフタイムを気にする必要がありました。それ以外では挿入とさほど変わらず難しいコードは無いと思います。 次回は削除操作を実装します。これは挿入、探索とは違って複雑な処理になりそうです。