Recursive & Iterative Binary Search Tree Implementations within Rust
This crate contains Recursive & Iterative Binary Search Tree Implementations. All common operations are included along with common traversal iterators.
All elements within the Binary Search Trees must implement the Ord trait.
It is also important to note that RecursiveBST is more likely to blow the stack.
For more information on why that is the case, please have a look at
The Story of Tail Call Optimizations in Rust.
I have made this library with the personal goals of learning and solidifying concepts such as ownership, borrowing
, generics and lifetimes. I cannot promise that the implementations are particularly efficient, or if they are, it
was not at the forefront of my mind.
That being said, there are some areas I would love to improve upon/include:
I'm more than happy to accept (and encourage) contributions if anyone is kind enough to do so. (Please look at CONTRIBUTING!)
```rust use bst_rs::{BinarySearchTree, IterativeBST, RecursiveBST};
// Create new empty binary search trees let mut iterativebst = IterativeBST::new(); assert!(iterativebst.is_empty());
let mut recursivebst = RecursiveBST::new(); assert!(recursivebst.is_empty());
// Insert elements (no duplicates are allowed) iterativebst.insert(10); iterativebst.insert(10); // Element is not inserted iterativebst.insert(5); iterativebst.insert(2); iterativebst.insert(15); iterativebst.insert(25); asserteq!(iterativebst.size(), 5);
recursivebst.insert(10); recursivebst.insert(10); // Element is not inserted recursivebst.insert(5); recursivebst.insert(2); recursivebst.insert(15); recursivebst.insert(25); asserteq!(recursivebst.size(), 5);
// Check if element exists assert!(iterativebst.contains(&5)); // true assert!(!iterativebst.contains(&0)); // false
assert!(recursivebst.contains(&5)); // true assert!(!recursivebst.contains(&0)); // false
// Remove elements iterativebst.remove(&10); iterativebst.remove(&50); // No change to tree as element does not exist asserteq!(iterativebst.size(), 4);
recursivebst.remove(&10); recursivebst.remove(&50); // No change to tree as element does not exist asserteq!(recursivebst.size(), 4);
// Get height of tree asserteq!(iterativebst.height(), Some(2)); asserteq!(recursivebst.height(), Some(2));
// Get minimum element of tree asserteq!(iterativebst.min(), Some(&2)); asserteq!(recursivebst.min(), Some(&2));
// Get maximum element of tree asserteq!(iterativebst.max(), Some(&25)); asserteq!(recursivebst.max(), Some(&25));
// Retrieve reference to element in tree asserteq!(iterativebst.retrieve(&5), Some(&5)); asserteq!(iterativebst.retrieve(&100), None); // Element does not exist so None is returned asserteq!(recursivebst.retrieve(&5), Some(&5)); asserteq!(recursivebst.retrieve(&100), None); // Element does not exist so None is returned
// View pre-order, in-order, post-order and level-order traversals asserteq!(iterativebst.preordervec(), vec![&15, &5, &2, &25]); asserteq!(iterativebst.inordervec(), vec![&2, &5, &15, &25]); asserteq!(iterativebst.postordervec(), vec![&2, &5, &25, &15]); asserteq!(iterativebst.levelordervec(), vec![&15, &5, &25, &2]);
asserteq!(recursivebst.preordervec(), vec![&15, &5, &2, &25]); asserteq!(recursivebst.inordervec(), vec![&2, &5, &15, &25]); asserteq!(recursivebst.postordervec(), vec![&2, &5, &25, &15]); asserteq!(recursivebst.levelordervec(), vec![&15, &5, &25, &2]);
// Compare equality/in-equality of trees asserteq!(iterativebst.ascordervec(), recursivebst.ascordervec()); assertne!(iterativebst, IterativeBST::new()); assertne!(recursive_bst, RecursiveBST::new()); ```
Please read the CONTRIBUTING.md before contributing! (Thank you!)
The book Learn Rust With Entirely Too Many Linked Lists inspired me to try and implement Binary Search Trees within the language. I had also been wanting to create my first library for other crates to use.