2026-10-26
zigzag_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;
let keys = (0..4).flat_map(|i| [2 * i, 7 - 2 * i]);
println!("{}", keys.map(|k| insert(&mut t, k)).max().unwrap());
}
これは何を出力するでしょうか?
Answer
6 です。
insert は、新しいキーを置いた深さを返します。根に置けば 1 で、子へ1段降りるたびに 1 が足されます。降りる先は usize::from(key > n.key) で決まり、キーがそのノードより大きければ右の子(kids[1])、そうでなければ左の子(kids[0])です。map は遅延して評価されるので、max が要素を1つ取り出すたびに insert が1回呼ばれ、max はその深さのうち最も深いものを返します。これが木の高さです。
flat_map は i ごとに [2 * i, 7 - 2 * i] を並べるので、挿入するキーは 0, 7, 2, 5, 4, 3, 6, 1 の順です。小さい値と大きい値が交互に来るので、木は左右に枝分かれし、8個なら高さは 4 程度に収まると読みたくなります。
実際に置いていくと、7 は 0 の右、2 は 7 の左、5 は 2 の右、4 は 5 の左、3 は 4 の左に付き、深さは 1 から 6 まで1つずつ増えます。どのキーも、それまでに置いた小さい側の最大と大きい側の最小のあいだに入るので、直前に置いたノードの下に付くしかありません。両端から中央へ詰める順は、昇順と同じように一直線の木を作ります。
最後の2つは、この列から外れます。6 は 0 の右、7 の左、2 の右、5 の右と進んで深さ 5 に、1 は 0 の右、7 の左、2 の左で深さ 4 に置かれます。どちらも 6 より浅いので、高さは 6 です。8個すべてが一直線につながると考えると、8 と答えることになります。