Simplify tree implementation?

code review
1

I'm currently doing Advent of Code in Rust to learn and yesterday (Day 07) was the first time I really struggled to implement the solution. Basically, the solution called for a tree. Reading through the countless posts regarding what makes it hard to implement them properly in Rust, I think I understand why this is the case and that there is no "simple" way around that while keeping all the other guarantees.

Still, I wanted to give it a shot and followed this Medium article. As one commenter points out, the implementation is flawed since it creates cyclic references and thus the memory will never be freed. For this reason, I used std::rc::Weak rather than std::rc::Rc for the back references.

I managed to get it work, but TBH I'm not sure I understand everything I did myself. I want to do a deep dive into what is happening, but before I do that I'm looking for possible simplification. Maybe I simply did a stupid thing out of ignorance. A potential diff might also help me understanding.

2

As I mentioned before, it is a misunderstanding on your part that trees can't be easily represented in Rust. What I think you might have read is that general graphs aren't, but trees are specifically well-suited for Rust's single-ownership (i.e., one parent) model.

Accordingly, you don't need any reference counting, interior mutability, parent/sibling links, or cyclic/self-references in order to solve this problem: Playground.

The gist of the type definition is a Node, containing a Vec<Node> representing children. Both computations the puzzle asks for are basically nothing more than a depth-first, post-order traversal, differing only in the accumulator, and then a single minimum finding at the end of the 2nd task. Parsing and construction of the FS tree can also be regarded as a depth-first, pre-order traversal if you look at it the right way (i.e., top-down). Hence, everything simplifies down to a single basic recursion pattern, which lends itself naturally to a single-ownership tree representation.

1 Like
3

That is true. Basically, I tried

struct Node {
     parent: Node,
     children: Vec<Node>,
}

and was hit with E0072. Just skimming over the error, I failed to realize that just the parent field was the issue rather than children as well. I cannot fully reproduce the further search history, but basically this threw me off looking for tree implementations that could handle this. Ultimately, this is how I ended up with the monstrosity above.

The reason I wanted the back reference to the parent in the first place, was an (possibly micro-) optimization: your example basically creates the tree first and afterwards traverses and aggregates everything. My implementation does the aggregation during the construction so I only have to traverse later.

Let me try to "reproduce" your solution. Maybe I find a few more nuggets in there.

4

Just wanted to report back, that I needed a tree again for day 13 and this time the experience was much smoother: aoc-2022-rust/13.rs at main · pmeier/aoc-2022-rust · GitHub

Especially, the "node as enum" pattern, i.e.

enum Node<T>{
    Internal {children: Vec<Node>},
    Leaf {value: T}
}

was really helpful. Thanks again!

5

Trees don't translate easily if you have parent pointers.

6

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.