Rustではじめるデータ構造とアルゴリズム
このシリーズ最高にいい。
Box<BinaryTree<T>> (重要)
left: BinaryTree<T> のように書きたくなるが、これでは再帰的な型定義となってしまい、 BinaryTree 型のサイズが確定できない(「 BinaryTree のサイズは… val のバイト数と、 left の BinaryTree のサイズを足して… ってそれを今計算してるのに😫」)。これを回避するために、”BinaryTree 型へのポインタ型” としてサイズが確定できるよう Box に包む。
「サイズが確定できない」から再帰的な定義ができないとはっきり教えてくれる。
// 型の解説:
// right: &mut Box<BinaryTree>
// *right: mut Box<BinaryTree>
// **right: mut BinaryTree
ありがとう。
「ハッシュテーブルがあれば二分探索木はいらない😤」とならないのは、二分探索木では 範囲検索 が効率的にできるためです。
知らなかった。
private な再帰関数 find_nil_to_add() が登場します。これは意味合い的には add() の中の内部関数で十分なのですが、型パラメーター T を内部関数に持ってくることができないため、 BinarySearchTree のメソッドとして定義しています。
「型パラメーター T を内部関数に持ってくることができないため」とか自分では絶対気が付かない。
今でも理由はよく分かってないけど、こう言っておいてくれれば、後で調べることができる。
/// 生存期間パラメータの解説:
/// - 't : 二分探索木自体の生存期間。 cur_node (現在探索中のノード) も、置き換えるべき Nil も、二分探索木自体の生存期と一致している。
/// - 'v : 追加する要素の生存期間
fn find_nil_to_add<'t, 'v>(
ライフタイムの実践的な使い方。