Struct BinaryTree 

pub struct BinaryTree<K, V> { /* private fields */ }

A binary tree containing key-value pairs where the keys can be ordered.

It should be noted that for most applications, a std::collections::HashMap will offer superior performance to that of a binary tree, since each node in the tree requires a heap allocation (apart from the root). Hash maps also provided amortized-constant lookup times where a binary tree gives O(log(n)).

For efficiency, the tree maintains a count of the number of elements inserted so that the len and is_empty methods are constant-time complexity.

Examples

This example shows how the binary tree functions much like a std::collections::HashMap, but gives O(log(n)) lookup time for keys that are of an ordinal type.

use collect_me::tree::binary_tree::BinaryTree;

let mut tree = BinaryTree::new();
tree.insert(0, "John");
tree.insert(42, "Neo");
tree.insert(2, "Alice");

assert_eq!(tree.get(&0), Some(&"John"));
assert_eq!(tree.get(&42), Some(&"Neo"));
assert_eq!(tree.get(&2), Some(&"Alice"));

Implementations

impl<K, V> BinaryTree<K, V>

pub fn new() -> Self

Constructs an empty tree

impl<K, V> BinaryTree<K, V>

where K: PartialOrd + Eq,

pub fn insert(&mut self, key: K, value: V) -> Option<V>

Inserts a key-value pair into the BinaryTree.

Returns None if the key did not exist, otherwise updates the value and returns Some with the old value.

Note

Like with std::collections::HashMap the key does not get updated.

pub fn get<Q>(&self, key: &Q) -> Option<&V>

where K: Borrow<Q>, Q: PartialOrd + Eq,

Returns a reference to the value corresponding to the key.

pub fn get_mut<Q>(&mut self, key: &Q) -> Option<&mut V>

where K: Borrow<Q>, Q: PartialOrd + Eq,

Returns a mutable reference to the value corresponding to the key.

pub fn len(&self) -> usize

Returns the number of elements in the tree with constant-time complexity.

pub fn is_empty(&self) -> bool

Returns true if the tree is empty.

Trait Implementations

impl<K: Clone, V: Clone> Clone for BinaryTree<K, V>

fn clone(&self) -> BinaryTree<K, V>

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl<K: Debug, V: Debug> Debug for BinaryTree<K, V>

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

Formats the value using the given formatter.

impl<K: Default, V: Default> Default for BinaryTree<K, V>

fn default() -> BinaryTree<K, V>

Returns the “default value” for a type.

impl<K: Eq, V: Eq> Eq for BinaryTree<K, V>

impl<K, V> Index<&K> for BinaryTree<K, V>

where K: PartialOrd + Eq,

fn index(&self, index: &K) -> &Self::Output

Returns a reference to the value corresponding to the supplied key.

Panics

Panics if the key is not present in the binary tree.

type Output = V

The returned type after indexing.

impl<K: PartialEq, V: PartialEq> PartialEq for BinaryTree<K, V>

fn eq(&self, other: &BinaryTree<K, V>) -> 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.

impl<K, V> StructuralPartialEq for BinaryTree<K, V>