Trait BinarySearchTree

pub trait BinarySearchTree<T: Ord> {
    // Required methods
    fn size(&self) -> usize;
    fn is_empty(&self) -> bool;
    fn is_not_empty(&self) -> bool;
    fn insert(&mut self, value: T);
    fn contains(&self, value: &T) -> bool;
    fn remove(&mut self, value: &T);
    fn retrieve(&self, value: &T) -> Option<&T>;
    fn retrieve_as_mut(&mut self, value: &T) -> Option<&mut T>;
    fn height(&self) -> Option<isize>;
    fn min(&self) -> Option<&T>;
    fn max(&self) -> Option<&T>;
    fn remove_min(&mut self) -> Option<T>;
    fn remove_max(&mut self) -> Option<T>;
    fn asc_order_vec(&self) -> Vec<&T>;
    fn pre_order_vec(&self) -> Vec<&T>;
    fn in_order_vec(&self) -> Vec<&T>;
    fn post_order_vec(&self) -> Vec<&T>;
    fn level_order_vec(&self) -> Vec<&T>;
    fn asc_order_iter(&self) -> IntoIter<&T>;
    fn pre_order_iter(&self) -> IntoIter<&T>;
    fn in_order_iter(&self) -> IntoIter<&T>;
    fn post_order_iter(&self) -> IntoIter<&T>;
    fn level_order_iter(&self) -> IntoIter<&T>;
    fn into_asc_order_iter(self) -> IntoIter<T>;
    fn into_pre_order_iter(self) -> IntoIter<T>;
    fn into_in_order_iter(self) -> IntoIter<T>;
    fn into_post_order_iter(self) -> IntoIter<T>;
    fn into_level_order_iter(self) -> IntoIter<T>;
}

A trait containing all the common operations of Binary Search Trees.

Examples

Examples are extended from crate level “Quick Start”

use bst_rs::{BinarySearchTree, IterativeBST, RecursiveBST};

// Create new empty binary search trees
let mut iterative_bst = IterativeBST::new();
assert!(iterative_bst.is_empty());///

let mut recursive_bst = RecursiveBST::new();
assert!(recursive_bst.is_empty());

// Insert elements (no duplicates are allowed)
iterative_bst.insert(10);
iterative_bst.insert(10);   // Element is not inserted
iterative_bst.insert(5);
iterative_bst.insert(2);
iterative_bst.insert(15);
iterative_bst.insert(25);
assert_eq!(iterative_bst.size(), 5);

recursive_bst.insert(10);
recursive_bst.insert(10);   // Element is not inserted
recursive_bst.insert(5);
recursive_bst.insert(2);
recursive_bst.insert(15);
recursive_bst.insert(25);
assert_eq!(recursive_bst.size(), 5);

// Check if element exists
assert!(iterative_bst.contains(&5));    // true
assert!(!iterative_bst.contains(&0));   // false

assert!(recursive_bst.contains(&5));    // true
assert!(!recursive_bst.contains(&0));   // false

// Remove elements
iterative_bst.remove(&10);
iterative_bst.remove(&50);              // No change to tree as element does not exist
assert_eq!(iterative_bst.size(), 4);

recursive_bst.remove(&10);
recursive_bst.remove(&50);              // No change to tree as element does not exist
assert_eq!(recursive_bst.size(), 4);

// Get height of tree
assert_eq!(iterative_bst.height(), Some(2));
assert_eq!(recursive_bst.height(), Some(2));

// Get minimum element of tree
assert_eq!(iterative_bst.min(), Some(&2));
assert_eq!(recursive_bst.min(), Some(&2));

// Get maximum element of tree
assert_eq!(iterative_bst.max(), Some(&25));
assert_eq!(recursive_bst.max(), Some(&25));

// Retrieve reference to element in tree
assert_eq!(iterative_bst.retrieve(&5), Some(&5));
assert_eq!(iterative_bst.retrieve(&100), None); // Element does not exist so None is returned
assert_eq!(recursive_bst.retrieve(&5), Some(&5));
assert_eq!(recursive_bst.retrieve(&100), None); // Element does not exist so None is returned

// View pre-order, in-order, post-order and level-order traversals
assert_eq!(iterative_bst.pre_order_vec(), vec![&15, &5, &2, &25]);
assert_eq!(iterative_bst.in_order_vec(), vec![&2, &5, &15, &25]);
assert_eq!(iterative_bst.post_order_vec(), vec![&2, &5, &25, &15]);
assert_eq!(iterative_bst.level_order_vec(), vec![&15, &5, &25, &2]);

assert_eq!(recursive_bst.pre_order_vec(), vec![&15, &5, &2, &25]);
assert_eq!(recursive_bst.in_order_vec(), vec![&2, &5, &15, &25]);
assert_eq!(recursive_bst.post_order_vec(), vec![&2, &5, &25, &15]);
assert_eq!(recursive_bst.level_order_vec(), vec![&15, &5, &25, &2]);

// Compare equality/in-equality of trees
assert_eq!(iterative_bst.asc_order_vec(), recursive_bst.asc_order_vec());
assert_ne!(iterative_bst, IterativeBST::new());
assert_ne!(recursive_bst, RecursiveBST::new());

Required Methods

fn size(&self) -> usize

Returns the total number of nodes within the tree.

fn is_empty(&self) -> bool

Returns true if the binary search tree contains no nodes.

fn is_not_empty(&self) -> bool

Returns true if the binary search tree contains one or more nodes.

fn insert(&mut self, value: T)

Inserts given value as a node.

Duplicate values are not allowed.

fn contains(&self, value: &T) -> bool

Returns true if the binary search tree contains an element with the given value.

fn remove(&mut self, value: &T)

Removes the given value.

Tree will not be modified if trying to remove element that does not exist.

fn retrieve(&self, value: &T) -> Option<&T>

Returns a reference to the element or None if element does not exist.

fn retrieve_as_mut(&mut self, value: &T) -> Option<&mut T>

Returns a mutable reference to the element (see retrieve) or None if element does not exist.

fn height(&self) -> Option<isize>

Returns the height or None if tree is empty.

The height is the number of edges between the root and it’s furthest leaf node.

Example

Given a tree that looks like:

 //         4
 //       /  \
 //      2    6
 //     / \  / \
 //    1  3 5   7

The height is: 2

fn min(&self) -> Option<&T>

Returns a reference to the minimum element of the tree or None if tree is empty.

fn max(&self) -> Option<&T>

Returns a reference to the maximum element of the tree or None if tree is empty.

fn remove_min(&mut self) -> Option<T>

Removes and returns the minimum element from the tree or None if tree is empty.

fn remove_max(&mut self) -> Option<T>

Removes and returns the maximum element from the tree or None if tree is empty.

fn asc_order_vec(&self) -> Vec<&T>

Returns references to the elements of the tree in ascending order.

Important

This is function is analogous to in_order_vec as the underlying behaviour is exactly the same.

fn pre_order_vec(&self) -> Vec<&T>

Returns references to the elements of the tree in the order of a pre-order traversal.

Example

Given a tree that looks like:

 //         4
 //       /  \
 //      2    6
 //     / \  / \
 //    1  3 5   7

The pre_order_vec is: [&4, &2, &1, &3, &6, &5, &7].

fn in_order_vec(&self) -> Vec<&T>

Returns references to the elements of the tree in the order of an in-order traversal.

Important

This is function is analogous to asc_order_vec as the underlying behaviour is exactly the same.

Example

Given a tree that looks like:

 //         4
 //       /  \
 //      2    6
 //     / \  / \
 //    1  3 5   7

The in_order_vec is: [&1, &2, &3, &4, &5, &6, &7].

fn post_order_vec(&self) -> Vec<&T>

Returns references to the elements of the tree in the order of a post-order traversal.

Example

Given a tree that looks like:

 //         4
 //       /  \
 //      2    6
 //     / \  / \
 //    1  3 5   7

The post_order_vec is: [&1, &3, &2, &5, &7, &6, &4].

fn level_order_vec(&self) -> Vec<&T>

Returns references to the elements of the tree in the order of a level-order traversal.

Example

Given a tree that looks like:

 //         4
 //       /  \
 //      2    6
 //     / \  / \
 //    1  3 5   7

The post_order_vec is: [&4, &2, &6, &1, &3, &5, &7].

fn asc_order_iter(&self) -> IntoIter<&T>

Returns an iterator over asc_order_vec.

Important

This is function is analogous to in_order_iter as the underlying behaviour is exactly the same.

fn pre_order_iter(&self) -> IntoIter<&T>

Returns an iterator over pre_order_vec.

fn in_order_iter(&self) -> IntoIter<&T>

Returns an iterator over in_order_vec.

Important

This is function is analogous to asc_order_iter as the underlying behaviour is exactly the same.

fn post_order_iter(&self) -> IntoIter<&T>

Returns an iterator over post_order_vec.

fn level_order_iter(&self) -> IntoIter<&T>

Returns an iterator over level_order_vec.

fn into_asc_order_iter(self) -> IntoIter<T>

Returns asc_order_iter AND consumes the tree.

Important

This is function is analogous to into_in_order_iter as the underlying behaviour is exactly the same.

fn into_pre_order_iter(self) -> IntoIter<T>

Returns pre_order_iter AND consumes the tree.

fn into_in_order_iter(self) -> IntoIter<T>

Returns in_order_iter AND consumes the tree.

Important

This is function is analogous to into_asc_order_iter as the underlying behaviour is exactly the same.

fn into_post_order_iter(self) -> IntoIter<T>

Returns post_order_iter AND consumes the tree.

fn into_level_order_iter(self) -> IntoIter<T>

Returns level_order_iter AND consumes the tree.

Implementors

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

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