Rustでスプレー木を作る

/// ## binary_search
/// 比較関数`compare`を引数にとり、条件を満たす最小のノードを返す
fn binary_search<'a, T, C>(root: &'a Option<Box<Node<T>>>, key: &T, compare: C) -> &'a Option<Box<Node<T>>>
where
    T: Ord,
    C: Fn(&T, &T) -> bool
{
    if root.is_none() {
        return root;
    }
    if compare(key, &root.as_ref().unwrap().key) {
        let left = &root.as_ref().unwrap().left;
        let tmp = binary_search(left, key, compare);
        if tmp.is_none() {
            root
        } else {
            tmp
        }
    } else {
        let right = &root.as_ref().unwrap().right;
        binary_search(right, key, compare)
    }
}

/// ## splay
/// 比較関数`compare`を引数にとり、条件を満たす最小のノードを返す
fn splay<T, C>(mut root: Option<Box<Node<T>>>, key: &T, compare: C) -> (Option<Box<Node<T>>>, bool)
where
    T: Ord + Debug,
    C: Fn(&T, &T) -> bool,
{
    if root.is_none() {
        return (root, false);
    }
    if compare(key, &root.as_ref().unwrap().key) {
        let left = &mut root.as_mut().unwrap().left;
        if left.is_none() {
            return (root, true);
        }
        if compare(key, &left.as_ref().unwrap().key) {
            let leftleft = left.as_mut().unwrap().left.take();
            let (mut tmp, is_found) = splay(leftleft, key, compare);
            // 戻す
            swap(&mut left.as_mut().unwrap().left, &mut tmp);
            // 親を右に回転
            let tmp_left = rotate_right(root);
            if !is_found {
                return (tmp_left, true);
            }
            // さらに右回転
            (rotate_right(tmp_left), true)
        } else {
            let leftright = left.as_mut().unwrap().right.take();
            let (mut new_leftright, is_found) = splay(leftright, key, compare);
            // 戻す
            swap(&mut left.as_mut().unwrap().right, &mut new_leftright);
            // root->left->rightがNoneでないとき
            if !is_found {
                return (root, true);
            }
            // 左の子を左回転
            let left = root.as_mut().unwrap().left.take();
            let mut tmp_child = rotate_left(left);
            swap(&mut root.as_mut().unwrap().left, &mut tmp_child);
            // 親を右回転
            (rotate_right(root), true)
        }
    } else {
        let right = &mut root.as_mut().unwrap().right;
        if right.is_none() {
            return (root, false);
        }
        if compare(key, &right.as_ref().unwrap().key) {
            let rightleft = right.as_mut().unwrap().left.take();
            let (mut tmp, is_found) = splay(rightleft, key, compare);
            // 戻す
            swap(&mut right.as_mut().unwrap().left, &mut tmp);
            if is_found {
                // 右の子を右回転
                let right = root.as_mut().unwrap().right.take();
                let mut tmp_child = rotate_right(right);
                swap(&mut root.as_mut().unwrap().right, &mut tmp_child);
            }
            // 親を左回転
            (rotate_left(root), true)
        } else {
            let rightright = right.as_mut().unwrap().right.take();
            let (mut tmp, is_found) = splay(rightright, key, compare);
            // 戻す
            swap(&mut right.as_mut().unwrap().right, &mut tmp);
            // 親を左回転
            let tmp_child = rotate_left(root);
            // さらに左回転
            (rotate_left(tmp_child), is_found)
        }
    }
}