Tree data structures in rust

1

Hello,
I was wondering what people's thoughts/experiences were implementing tree data structures in rust.

For comparison I've seen this:

And this:

Advocate "memory arena" based tree structures (i.e. a vec of nodes and indices of those nodes) being preferable to Rc<RefCell<Node>> approach.

The difference between the two linked implementations as I see it is:

struct Node<T> {
  first_child: usize,
  last_child: usize,
}

vs

struct Node<T> {
  children: Vec<usize>,
}

I.e. storing the indices of first and last child Vs a vec of children in each node. The latter seems easier to reason with and less error prone so I wondered if there were benefits to the first approach I might have missed. Or any other thoughts :slight_smile:

2

I say this from first-hand experience: it really depends on your use case.
If you're doing a lot of structural rearranging (i.e. modifying which nodes are in a tree and where) then you'll want the Rc<RefCell<Node>> approach because at this time I'm not convinced that it's even possible to keep the indexes straight without expensive operations that rearrange the arena after e.g. removal of a node from the tree.

In fact, it seems that the arena examples don't even provide functionality to remove nodes at all. If they do, it's quite hard to find, and not at all in the place I'd expect.