Function insert_fix

src/tree/binary/rb.rs:155–192

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

}

fn insert_fix<K, V>(
    root: Option<NonNull<Node<K, V>>>,
    x: Option<NonNull<Node<K, V>>>,
) -> Option<NonNull<Node<K, V>>> {
    let mut t = NodeQuery::new(root);
    let mut x = NodeQuery::new(x);
    while x.parent().color() == Some(Color::Red) {
        if x.uncle().color() == Some(Color::Red) {
            // case 1: ((a:R x:R b) y:B c:R) => ((a:R x:B b) y:R c:B)
            x.parent().set_color(Color::Black);
            x.grandparent().set_color(Color::Red);
            x.uncle().set_color(Color::Black);
            x = x.grandparent();
        } else if x.parent().i_am_left() {
            if x.i_am_right() {
                // case 2: ((a x:R b:R) y:B c) => case 3
                x = x.parent();
                t.node = rotate_left(t.node, x.node.unwrap());
            }
            // case 3: ((a:R x:R b) y:B c) => (a:R x:B (b y:R c))
            x.parent().set_color(Color::Black);
            x.grandparent().set_color(Color::Red);
            t.node = rotate_right(t.node, x.grandparent().node.unwrap());
        } else {
            if x.i_am_left() {
                // case 2': (a x:B (b:R y:R c)) => case 3'
                x = x.parent();
                t.node = rotate_right(t.node, x.node.unwrap());
            }
            // case 3': (a x:B (b y:R c:R)) => ((a x:R b) y:B c:R)
            x.parent().set_color(Color::Black);
            x.grandparent().set_color(Color::Red);
            t.node = rotate_left(t.node, x.grandparent().node.unwrap());
        }
    }
    t.set_color(Color::Black);
    t.node
}

/*
左旋操作变换为: