Hands-On Data Structures and Algorithms with Rust

Balancing the tree

After the node is added properly, fix_tree() takes care of restoring the red-black tree's properties—iteratively. While this is nicely descriptive and demonstrative it is long, so let's break it up into parts. Initially, the function determines whether it should stop (or not even start)—which only happens in two cases:

• When it's already the root node
• When the parent of the currently inspected node is red

Clearly, the former is the regular exit criterion as well, as the loop optimizes and moves the current pointer (n as in node) from the bottom toward the root of the tree to stop there:

fn fix_tree(&mut self, inserted: BareTree) -> Tree {    let mut not_root = inserted.borrow().parent.is_some();    let root = if not_root {