rust bst

bst.rs

use std::rc::Rc;
use std::fmt::String as StringFmt;
use Tree::{Node, Tip};

#[derive(Show)]
enum Tree<T> {
    Tip,
    Node(Rc<Tree<T>>, T, Rc<Tree<T>>),
}

impl<T: Ord + Clone + StringFmt> Tree<T> {
    fn insert(&self, x: T) -> Tree<T> {
        match *self {
            Node(ref l, ref v, ref r) if x < *v => Node(Rc::new(l.insert(x)), v.clone(), r.clone()),
            Node(ref l, ref v, ref r) => Node(l.clone(), v.clone(), Rc::new(r.insert(x))),
            Tip => Node(Rc::new(Tip), x, Rc::new(Tip))
        }
    }

    fn contains(&self, x: T) -> bool {
        match *self {
            Tip => false,
            Node(ref l, ref v, _) if x < *v => l.contains(x),
            Node(_, ref v, ref r) if x > *v => r.contains(x),
            _ => true
        }
    }

    fn unit(v: T) -> Tree<T> {
        Node(Rc::new(Tip), v, Rc::new(Tip))
    }

    fn new(xs: &Vec<T>) -> Tree<T> {
        xs.iter().fold(Tip, |t, v| t.insert(v.clone()))
    }
}

fn main() {
    let t = Tree::new(&vec![1, 9, 3, 8, 4, 6, 7, 5, 2]);
    println!("Tree: {:?}", t);
    println!("t.contains(2) = {}", t.contains(2));
    println!("t.contains(11) = {}", t.contains(11));
}