Rust tries to keep your memory safe by preventing you from doing things that could be potentially unsafe. Since this analysis is performed at compile time, the compiler can only speculate on a subset of manipulations that are known to be safe.
In Rust, you can easily save either a reference to the parent (borrowing the parent, thereby preventing mutations), or a list of child nodes (by owning them, which gives you more freedom), but not both (without using unsafe ). This is especially problematic for your addNode implementation, which requires modified access to the given node parent. However, if you store the parent pointer as a mutable reference, then since only one mutable reference to a specific object can be used at a time, the only way to access the parent is through the child of the node, and you can only have one child of the node. otherwise, you have two mutable links to the same parent node.
If you want to avoid unsafe code, there are many alternatives, but all of them will require some sacrifice.
The simplest solution is to simply remove the parent field. We can define a separate data structure in order to remember the parent element of the node while we are crossing the tree, rather than saving it in the node itself.
First, define Node :
#[derive(Debug)] struct Node<T> { data: T, children: Vec<Node<T>>, } impl<T> Node<T> { fn new(data: T) -> Node<T> { Node { data: data, children: vec![] } } fn add_child(&mut self, child: Node<T>) { self.children.push(child); } }
(I added the data field because the tree is not super useful without data in nodes!)
Now let's define another structure for tracking the parent during navigation:
#[derive(Debug)] struct NavigableNode<'a, T: 'a> { node: &'a Node<T>, parent: Option<&'a NavigableNode<'a, T>>, } impl<'a, T> NavigableNode<'a, T> { fn child(&self, index: usize) -> NavigableNode<T> { NavigableNode { node: &self.node.children[index], parent: Some(self) } } } impl<T> Node<T> { fn navigate<'a>(&'a self) -> NavigableNode<T> { NavigableNode { node: self, parent: None } } }
This solution works fine if you don’t need to mutate the tree while moving it, and you can save NavigableNode objects around it (which works great for a recursive algorithm, but doesn't work too well if you want to save NavigableNode in some other data structure and save it). The second limitation can be alleviated by using something other than a borrowed pointer to hold the parent; if you want maximum versatility, you can use Borrow trait to allow direct values, borrowed pointers, Box es, Rc , etc.
Now let's talk about lightning . In functional programming, lightnings are used to "focus" on a particular element of the data structure (list, tree, map, etc.), so access to this element takes a constant time, while retaining all the data in this data structure. If you need to move around the tree and mutate while navigating while still being able to navigate the tree, you can turn the tree into a zipper and make changes through the zipper. p>
Here we can implement the zipper for Node described above:
To use this lightning, you need to own the root of the tree node. By observing nodes, lightning can move things around to avoid copying or cloning nodes. When we move the zipper, we actually discard the old zipper and create a new one (although we could also do this by changing self , but I thought it was more understandable, plus this allows you to chain method calls).
If the above parameters are not satisfactory, and you should completely save the parent element of the node in node, then the next best option is to use Rc<RefCell<Node<T>>> to refer to the parent and children. Rc provides sharing, but adds overhead to perform reference counting at runtime. RefCell provides internal volatility, but adds overhead to track active roles at runtime. See DK. answer for implementation using Rc and RefCell .