A Tree Structure implemented in Rust.

Rust is known to be notorious difficult when it comes to certain data structures like linked lists, trees, etc. Many of such data structures have in common the necessity of several variables pointing to one value. For instance in a graph, two vertices could have a connection to a shared vertex. But when removing just one of these vertices, the shared vertex should not be dropped. In other words, non of these vertices can own the shared vertex in the strict sense.

Rust’s answer to this requirement is a Rc reference. A Rc reference owns a so called ‘inner value’. Moreover, we can clone borrowed references to Rc references and thus can have many such clones referring to the same Rc‘s inner value. This is the solution to the above stated problem, since now the shared vertex could be wrapped as inner value by a Rc reference (the owner of the vertex) and further all vertices having a connection to this shared vertex could be given a clone of this Rc reference:

use std::rc:Rc;
let ref = Rc::new(value); // moves 'value' into Rc
let clone1 = Rc::clone(&ref); // create a clone of a reference
let clone2 = Rc::clone(&ref); // creates another clone

If we just had moved the shared vertex into one of the others, and had provided a borrowed reference to the others, the…