Function balance

src/tree/binary/rb2.rs:343–355

restore red-black tree invariant

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

/// restore red-black tree invariant
fn balance<K, V>(h: Option<NonNull<Node<K, V>>>) -> Option<NonNull<Node<K, V>>> {
    let mut h = NodeQuery::new(h);
    if h.right().is_red() && !h.left().is_red() {
        h.node = rotate_left(h.node);
    }
    if h.left().is_red() && h.left().left().is_red() {
        h.node = rotate_right(h.node);
    }
    if h.left().is_red() && h.right().is_red() {
        flip_colors(h.node);
    }
    h.node
}

/// 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 {