Struct BSearchTree

pub struct BSearchTree<T, U> { /* private fields */ }

Implementation of a binary search tree

Example

use algods::data_structure::BSearchTree;
let mut bt = BSearchTree::new();
bt.insert(0,"1");
bt.insert(1,"2");
bt.insert(2,"3");
assert_eq!(bt.len(), 3);
assert!(bt.contains(&0));
assert_eq!(bt.get(&2), Some(&"3"));

Implementations

impl<T, U> BSearchTree<T, U>

pub fn new() -> Self

Creates an empty tree instance.

Example

use algods::data_structure::BSearchTree;
let bt = BSearchTree::<usize, isize>::new();
assert_eq!(bt.len(), 0);

pub fn init(key: T, value: U) -> Self

Creates a new tree with an initial (key, value) pair.

Example

use algods::data_structure::BSearchTree;
let bt = BSearchTree::init("btree", 0);
assert_eq!(bt.len(), 1);

pub fn len(&self) -> usize

Gives the number of (key, value) pairs in the tree.

Example

use algods::data_structure::BSearchTree;
let bt = BSearchTree::<usize, usize>::new();
assert_eq!(bt.len(),0);

pub fn is_empty(&self) -> bool

Tests whether or not the tree is empty.

Example

use algods::data_structure::BSearchTree;
let mut bt = BSearchTree::new();
bt.insert(1,1);
assert!(!bt.is_empty());

impl<T: Eq + Ord, U: Eq> BSearchTree<T, U>

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

Tests whether or not the tree contains a given key.

Example

use algods::data_structure::BSearchTree;
let bt = BSearchTree::init("btree", "one");
assert!(bt.contains(&"btree"));

pub fn get(&self, key: &T) -> Option<&U>

Returns a reference of the value associated to a key if any exists in the tree. Returns None otherwise.

Example

use algods::data_structure::BSearchTree;
let bt = BSearchTree::init("btree", "one");
assert_eq!(bt.get(&"no btree"), None);
assert_eq!(bt.get(&"btree"), Some(&"one"));

impl<T: Ord, U> BSearchTree<T, U>

pub fn insert(&mut self, key: T, value: U)

Inserts a (key, value) pair in the tree.

Example

use algods::data_structure::BSearchTree;
let mut bt = BSearchTree::<isize, usize>::new();
bt.insert(-1, 2);
bt.insert(-2, 3);
bt.insert(-1, 4);
assert_eq!(bt.len(), 2);
assert_eq!(bt.get(&-2), Some(&3));

impl<T: Eq + Ord, U: Ord> BSearchTree<T, U>

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

Returns the smallest key in the tree.

Example

use algods::data_structure::BSearchTree;
let mut bt = BSearchTree::<isize, usize>::init(1, 0);
bt.insert(-1, 2);
assert_eq!(bt.min(), Some(&-1));

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

Returns the largest key in the tree.

Example

use algods::data_structure::BSearchTree;
let mut bt = BSearchTree::<isize, usize>::init(0, 0);
bt.insert(-1, 2);
assert_eq!(bt.max(), Some(&0));

pub fn floor(&self, key: &T) -> Option<&T>

Returns for the largest key in the tree smaller or equal to the input key.

Example

use algods::data_structure::BSearchTree;
let mut bt = BSearchTree::<isize, usize>::init(1, 0);
bt.insert(-1, 2);
bt.insert(-2, 3);
assert_eq!(bt.floor(&1), Some(&1));
assert_eq!(bt.floor(&0), Some(&-1));

Trait Implementations

impl<T: Clone, U: Clone> Clone for BSearchTree<T, U>

fn clone(&self) -> BSearchTree<T, U>

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl<T: Debug, U: Debug> Debug for BSearchTree<T, U>

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

Formats the value using the given formatter.

impl<T, U> Default for BSearchTree<T, U>

fn default() -> Self

Returns the “default value” for a type.