binary_tree.rs

gistfile1.txt

#[derive(Debug, PartialEq)]
struct BinaryTree<T> {
    root: Option<Box<Node<T>>>,
}

#[derive(Debug, PartialEq)]
struct Node<T> {
    value: T,
    left: Option<Box<Node<T>>>,
    right: Option<Box<Node<T>>>,
}

impl<T> Node<T>
where T: PartialOrd + PartialEq {
    pub fn leaf(v: T) -> Self {
        Node { value: v, left: None, right: None }
    }

    pub fn node(v: T, left: Node<T>, right: Node<T>) -> Self {
        Node { value: v, left: Some(Box::new(left)), right: Some(Box::new(right)) }
    }

    pub fn is_leaf(&self) -> bool {
        self.left.is_none() && self.right.is_none()
    }

    pub fn delete(&mut self) -> Option<Box<Self>> {
        match (self.left.take(), self.right.take()) {
            (None, None) => None,
            (Some(left), None) => Some(left),
            (None, Some(right)) => Some(right),
            (Some(mut left), Some(right)) => {
                if let Some(mut right_most) = left.rightmost_child() {
                    right_most.left = Some(left);
                    right_most.right = Some(right);
                    Some(right_most)
                } else {
                    left.right = Some(right);
                    Some(left)
                }
            },
        }
    }

    pub fn rightmost_child(&mut self) -> Option<Box<Self>> {
        if self.right.is_none() {
            return None;
        } else if self.right.as_ref().map(|node| node.right.is_some()).unwrap_or(false) {
            let mut curr_node = self.right.as_mut().map(|node| &mut **node);
            while let Some(n) = curr_node.take() {
                if n.right.as_ref().map(|node| node.right.is_some()).unwrap_or(false) {
                    curr_node = n.right.as_mut().map(|node| &mut **node);
                } else {
                    let mut rightmost = n.right.take();
                    n.right = rightmost.as_mut().and_then(|node| node.left.take());
                    return rightmost;
                }
            }
            return None;
        } else {
            return self.right.take();
        }
    }
}

impl<T: PartialEq + PartialOrd> BinaryTree<T> {

    pub fn empty() -> Self {
        BinaryTree{ root: None }
    }

    pub fn insert(&mut self, v: T) {
        if self.root.is_none() {
            self.root = Some(Box::new(Node::leaf(v)));
        } else {
            let mut curr_node: Option<&mut Node<T>> = self.root.as_mut().map(|node| &mut **node);
            while let Some(node) = curr_node.take() {
                if node.value > v && node.left.is_some() {
                    curr_node = node.left.as_mut().map(|node| &mut **node);
                } else if node.value < v && node.right.is_some() {
                    curr_node = node.right.as_mut().map(|node| &mut **node);
                } else if node.value > v && node.left.is_none() {
                    node.left = Some(Box::new(Node::leaf(v)));
                    break;
                } else if node.value < v && node.right.is_none() {
                    node.right = Some(Box::new(Node::leaf(v)));
                    break;
                }
            }
        }
    }

    pub fn from_vec(vec: Vec<T>) -> Self {
        let mut tree = BinaryTree::empty();
        for v in vec.into_iter() {
            tree.insert(v);
        }
        tree
    }

    pub fn delete(&mut self, v: &T) {
        if self.root.is_some() {
            if self.root.as_ref().map(|node| node.value == *v).unwrap_or(false) {
                let mut curr_node = self.root.as_mut().map(|node| &mut **node).take();
                self.root = curr_node.take().and_then(|node| node.delete());
            } else {
                let mut curr_node: Option<&mut Node<T>> = self.root.as_mut().map(|node| &mut **node);
                while let Some(node) = curr_node.take() {
                    if node.value > *v && node.left.is_some() {
                        if node.left.as_ref().map(|node| node.value == *v).unwrap_or(false) {
                            node.left = node.left.as_mut().and_then(|node| node.delete());
                        } else {
                            curr_node = node.left.as_mut().map(|node| &mut **node);
                        }
                    } else if node.value < *v && node.right.is_some() {
                        if node.right.as_ref().map(|node| node.value == *v).unwrap_or(false) {
                            node.right = node.right.as_mut().and_then(|node| node.delete());
                        } else {
                            curr_node = node.right.as_mut().map(|node| &mut **node);
                        }
                    } else if node.value == *v {

                    }
                }
            }
        }
    }

}

#[cfg(test)]
mod test {

    use super::*;

    #[test]
    fn test_leaf() {
        assert_eq!(Node{ value: 10, left: None, right: None },
                   Node::leaf(10));
    }

    #[test]
    fn test_is_leaf() {
        let n1 = Node{ value: 10, left: None, right: None };
        assert!(n1.is_leaf());

        let n2 = Node{ value: 10, left: Some(Box::new(Node::leaf(5))), right: Some(Box::new(Node::leaf(12))) };
        assert!(!n2.is_leaf());

        let n3 = Node{ value: 10, left: None, right: Some(Box::new(Node::leaf(12))) };
        assert!(!n3.is_leaf());

        let n4 = Node{ value: 10, left: Some(Box::new(Node::leaf(5))), right: None };
        assert!(!n4.is_leaf());
    }

    #[test]
    fn test_rightmost() {
        let mut n = Node{ value: 10, left: None, right: Some(Box::new(Node{ value: 11, left: None, right: Some(Box::new(Node::leaf(12))) })) };
        assert_eq!(Some(Box::new(Node::leaf(12))), (&mut n).rightmost_child());

        let mut n = Node{ value: 10, left: None, right: Some(Box::new(Node{ value: 12, left: Some(Box::new(Node::leaf(11))), right: Some(Box::new(Node::leaf(13))) })) };
        assert_eq!(Some(Box::new(Node::leaf(13))), (&mut n).rightmost_child());

        let mut n = Node{ value: 10,
                          left: None,
                          right: Some(Box::new(Node{ value: 13,
                                                     left: Some(Box::new(Node::leaf(11))),
                                                     right: Some(Box::new(Node{ value: 14,
                                                                                left: Some(Box::new(Node::leaf(12))),
                                                                                right: None }))}))};
        assert_eq!(Some(Box::new(Node::leaf(14))), (&mut n).rightmost_child());
        assert_eq!(Node{ value: 10,
                         left: None,
                         right: Some(Box::new(Node{ value: 13,
                                                    left: Some(Box::new(Node::leaf(11))),
                                                    right: Some(Box::new(Node::leaf(12))) })) },
                   n);
    }

    #[test]
    fn test_empty() {
        assert_eq!(BinaryTree{ root: None }, BinaryTree::<i32>::empty());
    }

    #[test]
    fn test_insert() {
        let mut t = BinaryTree::empty();
        &t.insert(10);
        assert_eq!(BinaryTree{ root: Some(Box::new(Node{ value: 10, left: None, right: None})) },
                   t);

        &t.insert(5);
        assert_eq!(BinaryTree{ root: Some(Box::new(Node{ value: 10,
                                                         left: Some(Box::new(Node{ value: 5, left: None, right: None })),
                                                         right: None})) },
                   t);

        &t.insert(11);
        assert_eq!(BinaryTree{ root: Some(Box::new(Node{ value: 10,
                                                         left: Some(Box::new(Node{ value: 5, left: None, right: None })),
                                                         right: Some(Box::new(Node{ value: 11, left: None, right: None }))})) },
                   t);
    }

    #[test]
    fn test_from_vec() {
        assert_eq!(BinaryTree::from_vec(vec![10,5,15,6,3,20,11]),
                   BinaryTree{ root: Some(Box::new(Node::node(10,
                                                             Node::node(5, Node::leaf(3), Node::leaf(6)),
                                                             Node::node(15, Node::leaf(11), Node::leaf(20))))) });
    }

    #[test]
    fn test_delete() {
        let mut t = BinaryTree::empty();

        &t.delete(&10);
        assert_eq!(BinaryTree{ root: None }, t);

        &t.insert(10);
        &t.delete(&5);
        assert_eq!(BinaryTree{ root: Some(Box::new(Node{ value: 10, left: None, right: None})) },
                   t);

        &t.delete(&10);
        assert_eq!(BinaryTree{ root: None }, t);

        &t.insert(10);
        &t.insert(5);
        &t.delete(&5);
        assert_eq!(BinaryTree{ root: Some(Box::new(Node{ value: 10, left: None, right: None})) },
                   t);

        &t.insert(15);
        &t.delete(&15);
        assert_eq!(BinaryTree{ root: Some(Box::new(Node{ value: 10, left: None, right: None})) },
                   t);

        &t.insert(15);
        &t.insert(11);
        &t.insert(16);
        &t.delete(&15);
        assert_eq!(BinaryTree{ root: Some(Box::new(Node{ value: 10,
                                                         left: None,
                                                         right: Some(Box::new(Node { value: 11,
                                                                                     left: None,
                                                                                     right: Some(Box::new(Node::leaf(16))) })) })) },
                   t);
    }

    #[test]
    fn test_traverse_order() {

    }

}