Summary
目次：プログラミング学習
前回は探索を実装しました。 今回は二分探索木の操作、探索をするためのコードを書いていきます。
削除
二分探索木の構造の制約 「左の子の値 ≤ 親の値 ≤ 右の子の値」から探索を検討します。
子ノードが無い場合 （ １ を削除する場合）
１の子は左右両方とも None のため、そのまま削除（None）
子ノードが１つの場合 ( １0 を削除する場合)
10 には子が１つ、右に 14 があるので、10 を削除して 14 を 10 の場所にする。
子ノードが２つの場合 ( 6 を削除する場合)
6 には 4 と 7 の二つの子ノードがあります。二分探索木の構造の制約 「左の子の値 < 親の値 ≤ 右の子の値」を満たすように子ノードを移動させる必要があります。 この制約を満たすことができるのは 4 です。
子ノードが２つの場合 ( 8 を削除する場合)
8 には 3 と 10 の二つの子ノードがあります。制約を満たすためには左のノードの値 3 を持ってくればよさそうですが、3 を持って来るためには 3 を削除します。 3 についても制約を満たす必要があるので、左ノードの 1 を持ってきます。
これだと制約を満たしていません。3 の左ノードは全て 3 よりも小さくなければいけませんが、 1 の右ノードに 6 があります。 制約を満たすためには、削除するノードの左ノードにある最大値と交換します。
このツリーは制約を満たしています。 子ノードが２つある場合は、対象のノードを削除して左ノード（左のツリー）の最大値を持ってくる。最大値のノードも削除する。
実装
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
pub fn delete(&mut self, data: Data) {
// root から削除対象を探索
// データを改変するので mutable
let mut tmp = self.root.take();
self._delete(&mut tmp, data);
self.root = tmp;
}
fn _delete(&self, node: &mut OBNode, data: Data) {
// node 以下を探索
*node = match node.take() {
mut n @ Some(_) => {
let nd = n.as_mut().unwrap();
match data.cmp(&nd.data) {
Equal => self._delete_node(&mut n),
Less => self._delete(&mut n.as_mut().unwrap().left, data),
Greater => self._delete(&mut n.as_mut().unwrap().right, data),
}
n
}
None => None,
}
}
fn _delete_node(&self, node: &mut OBNode) {
if let Some(mut n) = node.take() {
// 削除対象ノード を None にする
// 子ノードの数によって分岐
// 削除対象ノードに結果を戻す
*node = match (n.left.take(), n.right.take()) {
(None, None) => None, // 子ノード 0 個
(x @ Some(_), None) | (None, x @ Some(_)) => x, // 子ノード 1 個
(mut l @ Some(_), r @ Some(_)) => { // 子ノード 2 個
let max_node = self.get_max_node(&mut l);
if let Some(max) = max_node {
let tmp = n.data;
n.data = max.data;
// max.data = tmp; // 不要
self._delete_node(max_node);
}
n.right = r;
n.left = l; // move するので データの入れ替え後に実行する
Some(n)
}
};
}
}
fn get_max_node<'a>(&'a self, node: &'a mut OBNode) -> &'a mut OBNode {
if node.as_ref().unwrap().right.is_some() {
// 右の子ノードがある場合は、さらに探索
return self.get_max_node(&mut node.as_mut().unwrap().right);
} else {
// 右に子ノードがなければ自身が最大値
return node;
}
}
delete, _delete は探索操作の場合と同じく削除対象となるノードを探しています。 _delete_node は子ノードがなければ削除、
１個あれば、そのノードに置き換え、２個ある場合は左ノード（ツリー）の最大値を取得し、data を交換し、最大値として取得したノードを削除しています。
探索操作のコードを修正すれば delete, _delete メソッドは必要なくなりそうですね。
ノードインスタンスを交換するのではなく、data だけを入れ替えるようにしました。
コード全体