Best way to implement a tree

help
1

I tried to implement a tree for practice, and it turned out to be much more difficult than I expected.

So I googled it and found this article that suggests using a memory arena. This means that all nodes are owned by an arena (e.g. a Vec), and to connect nodes in a tree or a graph, unique IDs are used instead of references:

pub struct Arena<T> {
    nodes: Vec<Node<T>>,
}

pub struct Node<T> {
    parent: Option<NodeId>,
    previous_sibling: Option<NodeId>,
    next_sibling: Option<NodeId>,
    first_child: Option<NodeId>,
    last_child: Option<NodeId>,
    
    pub data: T,
}

pub struct NodeId {
    index: usize,
}

However, I believe that this is a memory leak, since the nodes aren't dropped until the arena goes out of scope. This is a problem if the arena lives very long, and nodes are added and removed frequently.

Apart from that, you have to pass the Arena to all methods of Node, which reduces usability. And since NodeId isn't generic over T, fewer bugs can be detected at compile time.

Can some of these issues be fixed, or do you know a better way to implement trees? Can you recommend a crate?

2

Do you need parent and sibling pointers?

3

Yes, I forgot to mention that.

4

I've heard petgraph is good for non-strict trees like this:

1 Like