純粋な二分木

purebtree.rs

use std::rc::Rc;
use std::convert::From;

#[derive(Debug, Clone)]
pub enum PureBTree<T: Ord+Clone> {
    Empty,
    Node(T, Rc<PureBTree<T>>, Rc<PureBTree<T>>)
}

impl<T: Ord+Clone> From<T> for PureBTree<T> {
    fn from(x: T) -> Self {
        PureBTree::Node(x, Rc::new(PureBTree::Empty), Rc::new(PureBTree::Empty))
    }
}

impl<T: Ord+Clone> PureBTree<T> {
    pub fn new() -> PureBTree<T> {
        PureBTree::Empty
    }

    pub fn search(&self, needle: &T) -> bool {
        match *self {
            PureBTree::Empty => false,
            PureBTree::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!();
                }
            }
        }
    }

    pub fn insert(&self, value: T) -> PureBTree<T> {
        match *self {
            PureBTree::Empty => PureBTree::from(value),
            PureBTree::Node(ref x, ref left, ref right) => {
                if value < *x {
                    PureBTree::Node(x.clone(), Rc::new(left.insert(value)), right.clone())
                } else if value > *x {
                    PureBTree::Node(x.clone(), left.clone(), Rc::new(right.insert(value)))
                } else {
                    self.clone()
                }
            }
        }
    }
}