[JoshTriplett]

For a graph, I agree.

For a tree with parent pointers, I'd absolutely use Rc, with Weak for the parent pointers.