treers/
lib.rs

1pub mod bst;
2pub mod btree;
3pub mod rbtree;
4
5pub trait SedgewickMap<K: Ord, V> {
6    fn new() -> Self;
7    fn size(&self) -> usize;
8    fn get(&self, key: &K) -> Option<&V>;
9    fn put(&mut self, key: K, value: V);
10    fn height(&self) -> Option<usize>;
11    fn is_empty(&self) -> bool {
12        self.size().eq(&0_usize)
13    }
14
15    /// Checks if key exists in `Tree`
16    ///
17    ///
18    /// # Examples
19    ///
20    /// Basic usage:
21    ///
22    /// ```
23    /// use treers::bst::BST;
24    /// use treers::SedgewickMap;
25    /// use treers::rbtree::RedBlackTree;
26    /// use treers::btree::BalancedTree;
27    ///
28    /// let mut bst: BST<char, u32> = BST::new();
29    /// let mut rbtree: RedBlackTree<char, u32> = RedBlackTree::new();
30    /// let mut btree: BalancedTree<char, u32> = BalancedTree::new();
31    ///
32    /// bst.put('a', 2);
33    /// rbtree.put('a', 2);
34    /// btree.put('a', 2);
35    ///
36    /// assert_eq!(bst.contains(&'a'), true);
37    /// assert_eq!(bst.contains(&'b'), false);
38    ///
39    /// assert_eq!(rbtree.contains(&'a'), true);
40    /// assert_eq!(rbtree.contains(&'b'), false);
41    ///
42    /// assert_eq!(btree.contains(&'a'), true);
43    /// assert_eq!(btree.contains(&'b'), false);
44    /// ```
45    fn contains(&self, key: &K) -> bool {
46        self.get(&key).is_some()
47    }
48    fn min(&self) -> Option<&K>;
49    fn max(&self) -> Option<&K>;
50}
51
52/// A immutable recursive traversals over Binary Trees.
53///
54/// `Pre order`
55/// `In order`
56/// `Post order`
57/// `Level order`
58///
59/// # Examples
60///
61/// Basic usage:
62///
63/// ```
64/// use treers::bst::BST;
65/// use treers::{SedgewickMap, Traversals, TreeTraversal};
66///
67/// let mut bst: BST<char, i32> = BST::new();
68/// bst.put('c', 3);
69/// bst.put('d', 4);
70/// bst.put('b', 2);
71/// bst.put('a', 1);
72///
73/// // Pre order Traversal by keys
74/// for (a, _) in bst.traverse(&Traversals::PreOrder) {
75///     print!("{}, ", *a);
76/// }
77///
78/// // In order Traversal by keys
79/// for (a, _) in bst.traverse(&Traversals::InOrder) {
80///     print!("{}, ", *a);
81/// }
82///
83/// // Post order Traversal by keys
84/// for (a, _) in bst.traverse(&Traversals::PostOrder) {
85///     print!("{}, ", *a);
86/// }
87///
88/// // Level order Traversal by keys
89/// for (a, _) in bst.traverse(&Traversals::LevelOrder) {
90///     print!("{}, ", *a);
91/// }
92/// ```
93pub trait TreeTraversal<K: Ord, V>: SedgewickMap<K, V> {
94    fn traverse(&self, traverse: &Traversals) -> std::vec::IntoIter<(&K, &V)> {
95        let mut vec = Vec::with_capacity(self.size());
96        match traverse {
97            Traversals::PreOrder => self.pre_order(&mut vec),
98            Traversals::InOrder => self.in_order(&mut vec),
99            Traversals::PostOrder => self.post_order(&mut vec),
100            Traversals::LevelOrder => {
101                for level in 0..=self.height().unwrap() {
102                    self.level_order(&mut vec, level);
103                }
104            }
105        }
106        vec.into_iter()
107    }
108    fn pre_order<'a>(&'a self, vec: &mut Vec<(&'a K, &'a V)>);
109    fn in_order<'a>(&'a self, vec: &mut Vec<(&'a K, &'a V)>);
110    fn post_order<'a>(&'a self, vec: &mut Vec<(&'a K, &'a V)>);
111    fn level_order<'a>(&'a self, vec: &mut Vec<(&'a K, &'a V)>, level: usize);
112}
113
114pub enum Traversals {
115    PreOrder,
116    InOrder,
117    PostOrder,
118    LevelOrder,
119}
120
121#[cfg(test)]
122mod tests {
123    use crate::bst::BST;
124    use crate::btree::BalancedTree;
125    use crate::rbtree::RedBlackTree;
126    use crate::SedgewickMap;
127
128    #[test]
129    fn its_42() {
130        assert_eq!(20 + 22, 42);
131    }
132
133    fn is_empty<K: Ord, V>(map: &impl SedgewickMap<K, V>) -> bool {
134        map.is_empty()
135    }
136
137    #[test]
138    fn test_empty() {
139        let bst: BST<i32, i32> = BST::new();
140        let rbt: RedBlackTree<i32, i32> = RedBlackTree::new();
141        let btree: BalancedTree<i32, i32> = BalancedTree::new();
142
143        assert_eq!(is_empty(&bst), true);
144        assert_eq!(is_empty(&rbt), true);
145        assert_eq!(is_empty(&btree), true);
146    }
147}
treers/lib.rs

treers/
lib.rs
