Namaran

Code daily. Without assist.

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 に置かれます。