2026-10-26
unique_keys.rs
struct Node {
key: u32,
kids: [Tree; 2],
}
type Tree = Option<Box<Node>>;
fn insert(t: &mut Tree, key: u32) -> usize {
match t {
None => {
*t = Some(Box::new(Node { key, kids: [None, None] }));
1
}
Some(n) => 1 + insert(&mut n.kids[usize::from(key > n.key)], key),
}
}
fn main() {
let mut t = None;
println!("{:?}", [5, 5, 5, 5, 3].map(|k| insert(&mut t, k)));
}
insert は、二分探索木を重複のないキーの集合として使うつもりの挿入で、キーを置いた深さを返します。キーがすでにあれば何も足さず、そのノードの深さを返します。main は 5, 5, 5, 5, 3 を順に挿入し、それぞれの深さを表示します。本来の出力は [1, 1, 1, 1, 2] ですが、いまは [1, 2, 3, 4, 5] が出ます。
Answer
Wrong
match t {
None => {
*t = Some(Box::new(Node { key, kids: [None, None] }));
1
}
Some(n) => 1 + insert(&mut n.kids[usize::from(key > n.key)], key),
}
usize::from(key > n.key) は、キーがそのノードより大きければ右の子、そうでなければ左の子を選びます。等しいキーも「大きくない」ほうに入るので左へ進み、空いている場所まで降りて新しいノードを作ります。2つ目の 5 は根の左に、3つ目はさらにその左に置かれ、同じキーが4つのノードになって一直線に並びます。最後の 3 もこの列を全部たどり、深さ 5 に置かれます。同じキーが繰り返し届くたびに木は1段ずつ伸び、探索も挿入もキーの数に比例する時間がかかるようになります。
Right
match t {
None => {
*t = Some(Box::new(Node { key, kids: [None, None] }));
1
}
Some(n) if key == n.key => 1,
Some(n) => 1 + insert(&mut n.kids[usize::from(key > n.key)], key),
}
等しいキーの腕を、左右を選ぶ腕より前に置きます。match は上の腕から順に試すので、同じキーのノードに着いたところで止まり、新しいノードを作らずにその深さを返します。何度同じキーが来ても木は伸びず、3 は根の左の深さ 2 に置かれます。