The problem that our users face is clear: if a binary search tree encounters sorted data (such as incremental IDs), it can only ever append to one side, creating an unbalanced tree. A red-black tree is able to handle this at the cost of more operations being executed during insert (such as rotating subtrees), which is acceptable for the users.
This tree has similar nodes to the binary search tree, with the addition of a color field and a parent field, the latter of which triggers a wider change compared to the binary search tree. Thanks to the pointer back, the tree nodes cannot exclusively own the pointers to the children and parent (because, who owns this value, the parent or the child?), which requires a well-known pattern in Rust: interior mutability. As discussed in an earlier chapter, RefCell owns the data's portion of the memory and handles borrow-checking at runtime so that mutable and immutable references can be obtained:
type BareTree = Rc<...
