[−][src]Struct binary_search_tree::BinarySearchTree
In this crate, binary search trees store only one valuable value, which is also
used as a key, so all elements must have the Ord
trait implementation.
Examples
extern crate binary_search_tree; use binary_search_tree::BinarySearchTree; // Create a new binary search tree and fill it with numbers from 1 to 5: let mut tree: BinarySearchTree<i32> = BinarySearchTree::new(); for i in vec![3, 1, 2, 5, 4] { tree.insert(i); } // Get them in sorted order assert_eq!(tree.sorted_vec(), vec![&1, &2, &3, &4, &5]); // Let's extract the minimum and maximum. assert_eq!(tree.extract_min(), Some(1)); assert_eq!(tree.extract_max(), Some(5)); assert_eq!(tree.sorted_vec(), vec![&2, &3, &4]); // We can also extend the tree with elements from the iterator. tree.extend((0..6).map(|x| if x%2 == 0 { x } else { -x })); assert_eq!(tree.len(), 9); // If the elements must be unique, you should use insert_without_dup(). tree.insert_without_dup(0); assert_eq!(tree.len(), 9); // Delete the value 0 from the tree and make sure that the deletion actually occurred. tree.remove(&0); assert!(!tree.contains(&0)); // We can clear the tree of any remaining items. tree.clear(); // The tree should now be empty. assert!(tree.is_empty());
Fields
size: usize
Implementations
impl<T: Ord> BinarySearchTree<T>
[src]
pub fn new() -> Self
[src]
Makes a new empty BST.
Does not allocate anything on its own.
Examples
use binary_search_tree::BinarySearchTree; // New bst that will be contains i32 let mut tree: BinarySearchTree<i32> = BinarySearchTree::new();
pub fn is_empty(&self) -> bool
[src]
Сhecking if the tree is empty.
Examples
use binary_search_tree::BinarySearchTree; let mut tree: BinarySearchTree<i32> = BinarySearchTree::new(); assert!(tree.is_empty()); tree.insert(1); assert!(!tree.is_empty());
pub fn len(&self) -> usize
[src]
Returns the number of elements in the tree.
Examples
use binary_search_tree::BinarySearchTree; let mut tree: BinarySearchTree<i32> = BinarySearchTree::new(); assert_eq!(tree.len(), 0); tree.insert(1); assert_eq!(tree.len(), 1);
pub fn clear(&mut self)
[src]
Clears the binary search tree, removing all elements.
Examples
use binary_search_tree::BinarySearchTree; let mut tree: BinarySearchTree<i32> = BinarySearchTree::new(); tree.insert(1); tree.clear(); assert!(tree.is_empty());
pub fn root(&self) -> Option<&T>
[src]
Viewing the root element of the tree.
Examples
use binary_search_tree::BinarySearchTree; let mut tree: BinarySearchTree<i32> = BinarySearchTree::new(); assert!(tree.root().is_none()); // is empty tree.insert(1); tree.insert(0); tree.insert(2); // the first element inserted becomes the root assert_eq!(tree.root(), Some(&1));
pub fn insert(&mut self, value: T) -> bool
[src]
Inserting a new element.
Returns true if an element with the same value already exists in the tree, false otherwise.
Examples
use binary_search_tree::BinarySearchTree; let mut tree: BinarySearchTree<i32> = BinarySearchTree::new(); assert!(!tree.insert(1)); assert!(!tree.insert(0)); assert!(!tree.insert(2)); assert!(tree.insert(1)); // element 1 is already in the tree assert_eq!(tree.size, 4); // Elements in sorted order (inorder traversal) assert_eq!(tree.sorted_vec(), vec![&0, &1, &1, &2]);
pub fn insert_without_dup(&mut self, value: T) -> bool
[src]
Inserting a new unique element.
If an element with the same value is already in the tree, the insertion will not happen. Returns true if an element with the same value already exists in the tree, false otherwise.
Examples
use binary_search_tree::BinarySearchTree; let mut tree: BinarySearchTree<i32> = BinarySearchTree::new(); assert!(!tree.insert_without_dup(1)); assert!(!tree.insert_without_dup(0)); assert!(!tree.insert_without_dup(2)); assert!(tree.insert_without_dup(1)); // element 1 is already in the tree assert_eq!(tree.size, 3); // Elements in sorted order (inorder traversal) assert_eq!(tree.sorted_vec(), vec![&0, &1, &2]);
pub fn contains(&self, target: &T) -> bool
[src]
Checks whether the tree contains an element with the specified value.
Examples
use binary_search_tree::BinarySearchTree; let mut tree: BinarySearchTree<i32> = BinarySearchTree::new(); assert_eq!(tree.contains(&1), false); tree.insert(1); tree.insert(0); tree.insert(2); tree.insert(1); // The contains() method accepts a reference to a value assert!(tree.contains(&2)); assert!(tree.contains(&1)); assert!(!tree.contains(&999));
pub fn min(&self) -> Option<&T>
[src]
The minimum element of the tree.
Returns a reference to the minimum element.
Examples
use binary_search_tree::BinarySearchTree; let mut tree: BinarySearchTree<i32> = BinarySearchTree::new(); assert_eq!(tree.min(), None); tree.insert(1); tree.insert(0); tree.insert(2); tree.insert(1); assert_eq!(tree.min(), Some(&0));
pub fn max(&self) -> Option<&T>
[src]
The maximum element of the tree.
Returns a reference to the maximum element.
Examples
use binary_search_tree::BinarySearchTree; let mut tree: BinarySearchTree<i32> = BinarySearchTree::new(); assert_eq!(tree.max(), None); tree.insert(1); tree.insert(0); tree.insert(2); tree.insert(1); assert_eq!(tree.max(), Some(&2));
pub fn successor(&self, val: &T) -> Option<&T>
[src]
Inorder successor of the element with the specified value
In Binary Search Tree, inorder successor of an input node can be defined as the node with the smallest value greater than the value of the input node. In another way, we can say that the successor of element x is the element immediately following it in sorted order.
Examples
use binary_search_tree::BinarySearchTree; let mut tree: BinarySearchTree<i32> = BinarySearchTree::new(); tree.insert(25); tree.insert(15); tree.insert(40); tree.insert(10); tree.insert(18); tree.insert(45); tree.insert(35); // We have a binary tree with the following structure: // 25 // 15 40 // 10 18 35 45 assert_eq!(tree.sorted_vec(), vec![&10, &15, &18, &25, &35, &40, &45]); // and successor of 25 will be element 35. assert_eq!(tree.successor(&25), Some(&35)); assert_eq!(tree.successor(&40), Some(&45)); assert!(tree.successor(&45).is_none()); // Element 45 has no successors // We can also find successors for missing values in the tree assert_eq!(tree.successor(&20), Some(&25)); // [..., &18, vv &20 vv, &25, ...]
pub fn predecessor(&self, val: &T) -> Option<&T>
[src]
Inorder predecessor of the element with the specified value
In Binary Search Tree, inorder predecessor of an input node can be defined as the node with the greatest value smaller than the value of the input node. In another way, we can say that the predecessor of element x is the element immediately preceding it in sorted order.
Examples
use binary_search_tree::BinarySearchTree; let mut tree: BinarySearchTree<i32> = BinarySearchTree::new(); tree.insert(25); tree.insert(15); tree.insert(40); tree.insert(10); tree.insert(18); tree.insert(45); tree.insert(35); // We have a binary tree with the following structure: // 25 // 15 40 // 10 18 35 45 assert_eq!(tree.sorted_vec(), vec![&10, &15, &18, &25, &35, &40, &45]); // and predecessor of 25 will be element 35. assert_eq!(tree.predecessor(&25), Some(&18)); assert_eq!(tree.predecessor(&40), Some(&35)); assert!(tree.predecessor(&10).is_none()); // Element 10 has no predecessors // We can also find predecessors for missing values in the tree assert_eq!(tree.predecessor(&20), Some(&18)); // [..., &18, vv &20 vv, &25, ...]
pub fn extract_min(&mut self) -> Option<T>
[src]
Remove and return the minimum element.
This operation is much more efficient than searching for the minimum and then deleting it, since only one pass is performed and there are no comparisons between elements at all.
Examples
use binary_search_tree::BinarySearchTree; let mut tree: BinarySearchTree<i32> = BinarySearchTree::new(); assert!(tree.extract_min().is_none()); tree.insert(25); tree.insert(15); tree.insert(40); tree.insert(10); assert_eq!(tree.extract_min(), Some(10)); assert_eq!(tree.extract_min(), Some(15)); assert_eq!(tree.sorted_vec(), vec![&25, &40]);
pub fn extract_max(&mut self) -> Option<T>
[src]
Remove and return the maximum element.
This operation is much more efficient than searching for the maximum and then deleting it, since only one pass is performed and there are no comparisons between elements at all.
Examples
use binary_search_tree::BinarySearchTree; let mut tree: BinarySearchTree<i32> = BinarySearchTree::new(); assert!(tree.extract_max().is_none()); tree.insert(25); tree.insert(15); tree.insert(40); tree.insert(10); assert_eq!(tree.extract_max(), Some(40)); assert_eq!(tree.extract_max(), Some(25)); assert_eq!(tree.sorted_vec(), vec![&10, &15]);
pub fn remove(&mut self, target: &T) -> bool
[src]
Remove the first occurrence of an element with the target value.
Returns true if deletion occurred and false if target is missing from the tree.
Examples
use binary_search_tree::BinarySearchTree; let mut tree: BinarySearchTree<i32> = BinarySearchTree::new(); tree.insert(25); tree.insert(15); tree.insert(40); tree.insert(10); tree.insert(18); tree.insert(45); tree.insert(35); tree.insert(18); assert!(tree.remove(&18)); assert_eq!(tree.sorted_vec(), vec![&10, &15, &18, &25, &35, &40, &45]); assert_eq!(tree.size, 7); tree.remove(&25); assert_eq!(tree.sorted_vec(), vec![&10, &15, &18, &35, &40, &45]); assert_eq!(tree.size, 6); // If you try to delete a value that is missing from the tree, nothing will change assert!(!tree.remove(&99)); assert_eq!(tree.sorted_vec(), vec![&10, &15, &18, &35, &40, &45]); assert_eq!(tree.size, 6);
pub fn sorted_vec(&self) -> Vec<&T>
[src]
Vector of references to elements in the tree in non-decreasing order.
Examples
use binary_search_tree::BinarySearchTree; let mut tree: BinarySearchTree<i32> = BinarySearchTree::new(); tree.insert(25); tree.insert(15); tree.insert(40); tree.insert(10); tree.insert(18); tree.insert(45); tree.insert(35); tree.insert(18); assert_eq!(tree.sorted_vec(), vec![&10, &15, &18, &18, &25, &35, &40, &45]);
pub fn into_sorted_vec(self) -> Vec<T>
[src]
Moving the tree to a sorted vector.
Examples
use binary_search_tree::BinarySearchTree; let tree: BinarySearchTree<i32> = BinarySearchTree::new(); let mut tree: BinarySearchTree<i32> = BinarySearchTree::new(); tree.insert(25); tree.insert(15); tree.insert(40); tree.insert(10); assert_eq!(tree.into_sorted_vec(), vec![10, 15, 25, 40]);
pub fn inorder(&self) -> InorderTraversal<'_, T>ⓘNotable traits for InorderTraversal<'a, T>
impl<'a, T: 'a + Ord> Iterator for InorderTraversal<'a, T> type Item = &'a T;
[src]
Notable traits for InorderTraversal<'a, T>
impl<'a, T: 'a + Ord> Iterator for InorderTraversal<'a, T> type Item = &'a T;
Inorder traverse iterator of binary search tree.
Examples
use binary_search_tree::BinarySearchTree; let tree: BinarySearchTree<i32> = vec![5, 7, 3, 4, 8, 6, 1].into_iter().collect(); // Now we have a tree that looks like this: // 5 // 3 7 // 1 4 6 8 // And we should get the following sequence of its elements: 1, 3, 4, 5, 6, 7, 8 assert_eq!(tree.inorder().collect::<Vec<&i32>>(), vec![&1, &3, &4, &5, &6, &7, &8]);
pub fn reverse_order(&self) -> ReverseOrderTraversal<'_, T>ⓘNotable traits for ReverseOrderTraversal<'a, T>
impl<'a, T: 'a + Ord> Iterator for ReverseOrderTraversal<'a, T> type Item = &'a T;
[src]
Notable traits for ReverseOrderTraversal<'a, T>
impl<'a, T: 'a + Ord> Iterator for ReverseOrderTraversal<'a, T> type Item = &'a T;
Reverse order traverse iterator of binary search tree.
This iterator traverses the elements of the tree in descending order.
Examples
use binary_search_tree::BinarySearchTree; let tree: BinarySearchTree<i32> = vec![5, 7, 3, 4, 8, 6, 1].into_iter().collect(); // Now we have a tree that looks like this: // 5 // 3 7 // 1 4 6 8 // And we should get the following sequence of its elements: 8, 7, 6, 5, 4, 3, 1 assert_eq!(tree.reverse_order().collect::<Vec<&i32>>(), vec![&8, &7, &6, &5, &4, &3, &1]);
pub fn preorder(&self) -> PreorderTraversal<'_, T>ⓘNotable traits for PreorderTraversal<'a, T>
impl<'a, T: 'a + Ord> Iterator for PreorderTraversal<'a, T> type Item = &'a T;
[src]
Notable traits for PreorderTraversal<'a, T>
impl<'a, T: 'a + Ord> Iterator for PreorderTraversal<'a, T> type Item = &'a T;
Preorder traverse iterator of binary search tree.
Examples
use binary_search_tree::BinarySearchTree; let tree: BinarySearchTree<i32> = vec![5, 7, 3, 4, 8, 6, 1].into_iter().collect(); // Now we have a tree that looks like this: // 5 // 3 7 // 1 4 6 8 // And we should get the following sequence of its elements: 5, 3, 1, 4, 7, 6, 8 assert_eq!(tree.preorder().collect::<Vec<&i32>>(), vec![&5, &3, &1, &4, &7, &6, &8]);
pub fn postorder(&self) -> PostorderTraversal<'_, T>ⓘNotable traits for PostorderTraversal<'a, T>
impl<'a, T: 'a + Ord> Iterator for PostorderTraversal<'a, T> type Item = &'a T;
[src]
Notable traits for PostorderTraversal<'a, T>
impl<'a, T: 'a + Ord> Iterator for PostorderTraversal<'a, T> type Item = &'a T;
Postorder traverse iterator of binary search tree.
Examples
use binary_search_tree::BinarySearchTree; let tree: BinarySearchTree<i32> = vec![5, 7, 3, 4, 8, 6, 1].into_iter().collect(); // Now we have a tree that looks like this: // 5 // 3 7 // 1 4 6 8 // And we should get the following sequence of its elements: 1, 4, 3, 6, 8, 7, 5 assert_eq!(tree.postorder().collect::<Vec<&i32>>(), vec![&1, &4, &3, &6, &8, &7, &5]);
pub fn level_order(&self) -> LevelOrderTraversal<'_, T>ⓘNotable traits for LevelOrderTraversal<'a, T>
impl<'a, T: 'a + Ord> Iterator for LevelOrderTraversal<'a, T> type Item = &'a T;
[src]
Notable traits for LevelOrderTraversal<'a, T>
impl<'a, T: 'a + Ord> Iterator for LevelOrderTraversal<'a, T> type Item = &'a T;
Level order binary tree traversal.
Examples
use binary_search_tree::BinarySearchTree; let tree: BinarySearchTree<i32> = vec![5, 7, 3, 4, 8, 6, 1].into_iter().collect(); // Now we have a tree that looks like this: // 5 // 3 7 // 1 4 6 8 // And we should get the following sequence of its elements: 5, 3, 7, 1, 4, 6, 8 assert_eq!(tree.level_order().collect::<Vec<&i32>>(), vec![&5, &3, &7, &1, &4, &6, &8]);
Trait Implementations
impl<T: Ord + Clone> Clone for BinarySearchTree<T>
[src]
pub fn clone(&self) -> BinarySearchTree<T>
[src]
pub fn clone_from(&mut self, source: &Self)
1.0.0[src]
impl<T: Debug + Ord> Debug for BinarySearchTree<T>
[src]
impl<T: Ord + Debug> Display for BinarySearchTree<T>
[src]
impl<T: Ord> Extend<T> for BinarySearchTree<T>
[src]
pub fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I)
[src]
Extend bst with elements from the iterator.
Note: extend doesn't keep track of duplicates, but just uses the whole iterator.
Examples
use binary_search_tree::BinarySearchTree; use std::iter::Extend; let mut tree: BinarySearchTree<i32> = BinarySearchTree::new(); tree.extend(vec![7, 1, 0, 4, 5, 3].into_iter()); assert_eq!(tree.sorted_vec(), [&0, &1, &3, &4, &5, &7]);
pub fn extend_one(&mut self, item: A)
[src]
pub fn extend_reserve(&mut self, additional: usize)
[src]
impl<T: Ord> FromIterator<T> for BinarySearchTree<T>
[src]
pub fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self
[src]
Сreating a bst from an iterator.
Examples
use binary_search_tree::BinarySearchTree; use std::iter::FromIterator; let tree: BinarySearchTree<i32> = BinarySearchTree::from_iter( vec![7, 1, 0, 4, 5, 3].into_iter()); assert_eq!(tree.sorted_vec(), [&0, &1, &3, &4, &5, &7]); let tree: BinarySearchTree<i32> = vec![7, 1, 0, 4, 5, 3].into_iter().collect(); assert_eq!(tree.sorted_vec(), [&0, &1, &3, &4, &5, &7]);
impl<T: Ord> PartialEq<BinarySearchTree<T>> for BinarySearchTree<T>
[src]
Auto Trait Implementations
impl<T> RefUnwindSafe for BinarySearchTree<T> where
T: RefUnwindSafe,
[src]
T: RefUnwindSafe,
impl<T> Send for BinarySearchTree<T> where
T: Send,
[src]
T: Send,
impl<T> Sync for BinarySearchTree<T> where
T: Sync,
[src]
T: Sync,
impl<T> Unpin for BinarySearchTree<T>
[src]
impl<T> UnwindSafe for BinarySearchTree<T> where
T: UnwindSafe,
[src]
T: UnwindSafe,
Blanket Implementations
impl<T> Any for T where
T: 'static + ?Sized,
[src]
T: 'static + ?Sized,
impl<T> Borrow<T> for T where
T: ?Sized,
[src]
T: ?Sized,
impl<T> BorrowMut<T> for T where
T: ?Sized,
[src]
T: ?Sized,
pub fn borrow_mut(&mut self) -> &mut T
[src]
impl<T> From<T> for T
[src]
impl<T, U> Into<U> for T where
U: From<T>,
[src]
U: From<T>,
impl<T> ToOwned for T where
T: Clone,
[src]
T: Clone,
type Owned = T
The resulting type after obtaining ownership.
pub fn to_owned(&self) -> T
[src]
pub fn clone_into(&self, target: &mut T)
[src]
impl<T> ToString for T where
T: Display + ?Sized,
[src]
T: Display + ?Sized,
impl<T, U> TryFrom<U> for T where
U: Into<T>,
[src]
U: Into<T>,
type Error = Infallible
The type returned in the event of a conversion error.
pub fn try_from(value: U) -> Result<T, <T as TryFrom<U>>::Error>
[src]
impl<T, U> TryInto<U> for T where
U: TryFrom<T>,
[src]
U: TryFrom<T>,