Namaran

Code daily. Without assist.

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) のような専用の型を使うと、ほかの整数と取り違えにくくなります。