Function left_rotate

publication/code/chapter08/rbtree.rs:808–840

(tree: &mut RBTree<K, V>, x: *mut RBNode<K, V>)

// 节点左旋
#[inline]
unsafe fn left_rotate<K: Ord + Debug, V>(tree: &mut RBTree<K, V>, x: *mut RBNode<K, V>) {
    /*
     * x 处左旋
     * (x could also be the left child of p)
     *
     *  p           p
     *   \           \
     *    x    -->    y
     *   / \         / \
     *      y       x
     *     / \     / \
     *    c           c
     */

    let p = (*x).parent;
    let y = (*x).right;
    let c = (*y).left;

    (*y).left = x;
    (*x).parent = y;
    (*x).right = c;
    if !c.is_null() {
        (*c).parent = x;
    }
    if p.is_null() {
        tree.root = y;
    } else if (*p).left == x {
        (*p).left = y;
    } else {
        (*p).right = y;
    }
    (*y).parent = p;
}

// 节点右旋
#[inline]