BTreeを実装しようとした

btree.rs

fn main() {
    let mut tree: BTree<i32> = BTree::Empty
        .insert(10)
        .insert(5)
        .insert(15);

    for i in 0..20 {
        tree.insert_mut(i);
    }
    println!("{}", tree.search(&10));
    println!("{}", tree.search(&0));
    println!("{}", tree.search(&20));
    println!("{:?}", tree);

}

#[derive(Debug)]
enum BTree<T: Ord> {
    Empty,
    Node(T, Box<BTree<T>>, Box<BTree<T>>)
}

impl<T: Ord+Clone> Clone for BTree<T> {
    fn clone(&self) -> BTree<T> {
        match *self {
            BTree::Empty => BTree::Empty,
            BTree::Node(ref x, ref left, ref right) => {
                BTree::Node((*x).clone(), (*left).clone(), (*right).clone())
                }
        }
    }
}

impl<T: Ord> BTree<T> {
    fn search(&self, needle: &T) -> bool {
        match *self {
            BTree::Empty => false,
            BTree::Node(ref value, ref left, ref right) => {
                if needle == value {
                    true
                } else if needle < value {
                    left.search(&needle)
                } else if needle > value {
                    right.search(&needle)
                }
                else {
                    unreachable!();
                }
            }
        }
    }

    fn insert_mut(&mut self, value: T) {
        match *self {
            BTree::Empty => {*self = BTree::Node(value, Box::new(BTree::Empty), Box::new(BTree::Empty))}
            BTree::Node(ref x, ref mut left, ref mut right) => {
                if value < *x {
                    left.insert_mut(value)
                } else if value > *x {
                    right.insert_mut(value)
                }
            }
        }
    }
}

impl<T: Ord+Clone> BTree<T> {
    fn insert(&self, value: T) -> BTree<T> {
        match *self {
            BTree::Empty => BTree::Node(value, Box::new(BTree::Empty), Box::new(BTree::Empty)),
            BTree::Node(ref x, ref left, ref right) => {
                if value < *x {
                    BTree::Node((*x).clone(), Box::new(left.insert(value)), (*right).clone())
                } else if value > *x {
                    BTree::Node((*x).clone(), (*left).clone(), Box::new(right.insert(value)))
                } else {
                    self.clone()
                }
            }
        }
    }
}