Function is_balance

src/tree/binary/rb2.rs:358–373

does every path from the root to a leaf have the given number of black links?

(root: Option<NonNull<Node<K, V>>>)

/// does every path from the root to a leaf have the given number of black links?
fn is_balance<K, V>(root: Option<NonNull<Node<K, V>>>) -> bool {
    fn counter<K, V>(h: Option<NonNull<Node<K, V>>>, mut black: usize) -> bool {
        if h.is_none() {
            0 == black
        } else {
            let h = NodeQuery::new(h);
            if !h.is_red() {
                black -= 1;
            }
            counter(h.left().node, black) && counter(h.right().node, black)
        }
    }

    let black = calc_blacks(root);
    counter(root, black)
}

/// Assuming that h is red and both h.left and h.left.left
/// are black, make h.left or one of its children red.