Struct BinarySearchTree

pub struct BinarySearchTree<T: Ord> {
    pub size: usize,
    /* private fields */
}

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>

pub fn new() -> Self

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

С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

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)

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>

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

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

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

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>

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>

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>

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>

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>

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>

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

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>

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>

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>

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>

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>

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>

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>

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>

fn clone(&self) -> BinarySearchTree<T>

Returns a copy of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<T: Debug + Ord> Debug for BinarySearchTree<T>

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<T: Ord + Debug> Display for BinarySearchTree<T>

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<T: Ord> Extend<T> for BinarySearchTree<T>

fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I)

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]);

fn extend_one(&mut self, item: A)

🔬This is a nightly-only experimental API. (extend_one)

Extends a collection with exactly one element.

fn extend_reserve(&mut self, additional: usize)

🔬This is a nightly-only experimental API. (extend_one)

Reserves capacity in a collection for the given number of additional elements.

impl<T: Ord> FromIterator<T> for BinarySearchTree<T>

fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self

С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 for BinarySearchTree<T>

fn eq(&self, other: &BinarySearchTree<T>) -> bool

Tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

Tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.