Function insert

src/tree/binary/rb.rs:141–153

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

}

fn insert<K, V>(root: Option<NonNull<Node<K, V>>>, key: K, val: V) -> Option<NonNull<Node<K, V>>>
where
    K: Ord,
{
    // 插入过程与bst是一样的
    if let Ok(x) = unsafe { bst::insert(root, key, val) } {
        let root = if root.is_none() { Some(x) } else { root };
        // 修正，使树恢复平衡
        insert_fix(root, Some(x))
    } else {
        None
    }
}

fn insert_fix<K, V>(
    root: Option<NonNull<Node<K, V>>>,