2026-11-02
tree_arena.rs
struct Node {
value: i32,
children: Vec<usize>,
}
fn add_child(arena: &mut Vec<Node>, parent: usize, value: i32) -> usize {
}
木のノードをすべて1つの Vec<Node> の arena に置き、ノードを arena の中の添字で指します。children は子ノードの添字の並びです。値 value を持つ新しいノードを arena の末尾に作り、添字 parent のノードの子の最後に加えて、新しいノードの添字を返す add_child を書いてください。新しいノードはまだ子を持ちません。parent は arena の中の有効な添字とします。例では、呼び出しの前と後の arena を、添字の順に 値 [子の添字] を並べて書きます。
入力例 1
[0 []]
add_child(&mut arena, 0, 7)
出力例 1
1
[0 [1], 7 []]
入力例 2
[0 [1], 7 []]
add_child(&mut arena, 1, 9)
出力例 2
2
[0 [1], 7 [2], 9 []]
入力例 3
[0 [1], 7 []]
add_child(&mut arena, 0, 8)
出力例 3
2
[0 [1, 2], 7 [], 8 []]
Reference
fn add_child(arena: &mut Vec<Node>, parent: usize, value: i32) -> usize {
let id = arena.len();
arena.push(Node { value, children: Vec::new() });
arena[parent].children.push(id);
id
}
新しいノードの添字は、push する前の arena.len() です。末尾に積むので、それまでの要素数がそのまま次の添字になります。push のあとに arena.len() を読むなら、1を引く必要があります。
親に添字を足すのは、push を終えてからにします。先に let p = &mut arena[parent]; で親への可変参照を取り、それを持ったまま arena.push を呼ぶと、arena を2か所から同時に可変で借りることになり、コンパイルできません。この規則があるのは、push が Vec の領域を確保し直して要素を移すことがあり、その前に取った参照が古い領域を指したまま残りうるからです。添字は arena を借りていないので、確保し直しのあとも同じノードを指し続けます。ノードどうしを参照ではなく添字でつなぐのは、このためです。
掲載したのは参考実装で、唯一の正解ではありません。添字に struct NodeId(usize) のような専用の型を使うと、ほかの整数と取り違えにくくなります。