Looking for the best idiomatic way to work on trees as fast as possible

Hello, i'm just looking at an effective way to work on tree data structure with rust
and I found that this way of pointing on memory to seam to be kin of .... impractical .... to use is
every one is alright with this following code or I missing a super efficient way to "follow" through the stack in the most efficient way ? I have found by the way that the indirection Box for sized trait was the idiomatic way to work on Tree in Rust but I may miss something with this one... maybe not ....!?

/*
    this kind of struc dont own the data which mean that the memory
    pointed at should always live longer than the struct itself
    almost impratical to use with a real interest.
*/
    #[derive(Debug)]
    struct Tree_r<'a> {
        value: i8,
        right: &'a mut Option<Tree_r<'a>>,
        left: &'a mut Option<Tree_r<'a>>,
    }
    impl<'a> Tree_r<'a> {
        /*
        the folowing values (value, right and left) should point on valid memory with at least the same life time
        as the struct itself...
        */
        fn new(
            value: i8,
            right: &'a mut Option<Tree_r<'a>>,
            left: &'a mut Option<Tree_r<'a>>,
        ) -> Self {
            Self { value, right, left }
        }
    }

You want this structure:

struct Tree {
    value: i8,
    right: Option<Box<Tree>>,
    left: Option<Box<Tree>>,
}

Using & or &mut references in recursive data types is generally wrong and will cause you headaches. Instead, each Tree node should own its children using the owning pointer Box.

4 Likes

yes this is what I use thanks

references are not necessarily bad in data structures, & references are very useful in recursive data structures when all & references in the data structure have the same lifetime -- this can be achieved using an arena to allocate nodes and using the arena's lifetime (or the lifetime of a struct with all your different-typed arenas in it) for the & references. I use the typed-arena crate for this purpose in my code.

1 Like

Yes, I found this https://rust-leipzig.github.io/architecture/2016/12/20/idiomatic-trees-in-rust/ also, and if anyone have some documentations about this ?
what i'm trying to do is recursive parent reference like this but unsuccessfully:

 pub struct TreeT<'a,T> {
        pub value: T,
        pub right: Option<Box<TreeT<'a,T>>>,
        pub left: Option<Box<TreeT<'a,T>>>,
        pub parent: Option<&'a mut TreeT<'a,T>>,
    }

but maybe the concept of "memory arena" is the only way to achieve this purpose ...
any additional information will be welcome...
thx anyone, by the way that's an interesting topic for Rust .

Right, you can't use conventional references to build that kind of data structure, with links from child to parent. You'll need shared ownership (Rc + Weak) or some kind of arena, possibly one built around indices instead of references.

1 Like