[−][src]Trait treers::SedgewickMap
Required methods
fn new() -> Self
fn size(&self) -> usize
fn get(&self, key: &K) -> Option<&V>
fn put(&mut self, key: K, value: V)
fn height(&self) -> Option<usize>
fn min(&self) -> Option<&K>
fn max(&self) -> Option<&K>
Provided methods
fn is_empty(&self) -> bool
fn contains(&self, key: &K) -> bool
Checks if key exists in Tree
Examples
Basic usage:
use treers::bst::BST; use treers::SedgewickMap; use treers::rbtree::RedBlackTree; use treers::btree::BalancedTree; let mut bst: BST<char, u32> = BST::new(); let mut rbtree: RedBlackTree<char, u32> = RedBlackTree::new(); let mut btree: BalancedTree<char, u32> = BalancedTree::new(); bst.put('a', 2); rbtree.put('a', 2); btree.put('a', 2); assert_eq!(bst.contains(&'a'), true); assert_eq!(bst.contains(&'b'), false); assert_eq!(rbtree.contains(&'a'), true); assert_eq!(rbtree.contains(&'b'), false); assert_eq!(btree.contains(&'a'), true); assert_eq!(btree.contains(&'b'), false);
Implementors
impl<K: Ord + Clone, V: Clone> SedgewickMap<K, V> for RedBlackTree<K, V>
[src]
fn new() -> Self
[src]
Inits a new instance of Red-Black Tree.
Examples
Basic usage:
use treers::rbtree::RedBlackTree; use treers::SedgewickMap; let rbtree: RedBlackTree<char, i32> = RedBlackTree::new(); assert_eq!(rbtree.is_empty(), true);
fn size(&self) -> usize
[src]
Returns a size of elements in Red-Black Tree
.
Examples
Basic usage:
use treers::rbtree::RedBlackTree; use treers::SedgewickMap; let mut rbtree: RedBlackTree<char, i32> = RedBlackTree::new(); assert_eq!(rbtree.size(), 0_usize); rbtree.put('a', 1); rbtree.put('b', 2); rbtree.put('c', 3); rbtree.put('d', 4); assert_eq!(rbtree.size(), 4_usize);
fn get(&self, key: &K) -> Option<&V>
[src]
Returns a reference to optional reference to value.
Examples
Basic usage:
use treers::rbtree::RedBlackTree; use treers::SedgewickMap; let mut rbtree: RedBlackTree<char, i32> = RedBlackTree::new(); rbtree.put('a', 1); assert_eq!(rbtree.get(&'a'), Some(&1)); assert_eq!(rbtree[&'a'], 1); assert_eq!(rbtree.get(&'b'), None);
fn put(&mut self, key: K, value: V)
[src]
Insert a key-value pair into the Red-Black Tree
.
Examples
Basic usage:
use treers::rbtree::RedBlackTree; use treers::SedgewickMap; let mut rbtree: RedBlackTree<char, i32> = RedBlackTree::new(); assert_eq!(rbtree.is_empty(), true); rbtree.put('a', 1_i32); assert_eq!(rbtree.is_empty(), false); assert_eq!(rbtree.get(&'a'), Some(&1_i32)); assert_eq!(rbtree[&'a'], 1_i32);
fn height(&self) -> Option<usize>
[src]
Get height of Red-Black Tree
.
Red-Black Tree is a balanced tree.
Examples
Basic usage:
use treers::rbtree::RedBlackTree; use treers::SedgewickMap; let mut rbtree: RedBlackTree<char, i32> = RedBlackTree::new(); rbtree.put('a', 1); rbtree.put('b', 2); rbtree.put('c', 3); rbtree.put('d', 4); // b <-- height: 0 // / \ // a d <-- height: 1 // / \ // c <-- height: 2 // Note -The Height of red-black tree with single node is taken as zero. assert_eq!(rbtree.get(&'a'), Some(&1_i32)); assert_eq!(rbtree.height(), Some(2_usize)); assert_eq!(rbtree.size(), 4_usize);
fn is_empty(&self) -> bool
[src]
Checks if Red-Black Tree
node is empty.
Examples
Basic usage:
use treers::rbtree::RedBlackTree; use treers::SedgewickMap; let mut rbtree: RedBlackTree<char, i32> = RedBlackTree::new(); assert_eq!(rbtree.is_empty(), true); rbtree.put('a', 2); assert_eq!(rbtree.is_empty(), false);
fn min(&self) -> Option<&K>
[src]
Returns a optional reference to minimal key
Examples
Basic usage:
use treers::rbtree::RedBlackTree; use treers::SedgewickMap; let mut rbtree: RedBlackTree<char, i32> = RedBlackTree::new(); assert_eq!(rbtree.min(), None); rbtree.put('c', 1); rbtree.put('a', 2); rbtree.put('b', 3); rbtree.put('d', 4); assert_eq!(rbtree.min(), Some(&'a'));
fn max(&self) -> Option<&K>
[src]
Returns a optional reference to maximum key
Examples
Basic usage:
use treers::rbtree::RedBlackTree; use treers::SedgewickMap; let mut rbtree: RedBlackTree<char, i32> = RedBlackTree::new(); assert_eq!(rbtree.max(), None); rbtree.put('c', 1); rbtree.put('a', 2); rbtree.put('b', 3); rbtree.put('d', 4); assert_eq!(rbtree.max(), Some(&'d'));
impl<K: Ord + Clone, V: Clone> SedgewickMap<K, V> for BalancedTree<K, V>
[src]
fn new() -> Self
[src]
Inits a new instance of Balanced Tree.
Examples
Basic usage:
use treers::btree::BalancedTree; use treers::SedgewickMap; let btree: BalancedTree<char, i32> = BalancedTree::new(); assert_eq!(btree.is_empty(), true);
fn size(&self) -> usize
[src]
Returns a size of elements in BST
.
Examples
Basic usage:
use treers::btree::BalancedTree; use treers::SedgewickMap; let mut btree: BalancedTree<char, i32> = BalancedTree::new(); assert_eq!(btree.size(), 0_usize); btree.put('a', 1); btree.put('b', 2); btree.put('c', 3); btree.put('d', 4); assert_eq!(btree.size(), 4_usize);
fn get(&self, key: &K) -> Option<&V>
[src]
Returns a reference to optional reference to value.
Examples
Basic usage:
use treers::btree::BalancedTree; use treers::SedgewickMap; let mut btree: BalancedTree<char, i32> = BalancedTree::new(); btree.put('a', 1); assert_eq!(btree.get(&'a'), Some(&1)); assert_eq!(btree.get(&'b'), None); assert_eq!(btree[&'a'], 1);
fn put(&mut self, key: K, value: V)
[src]
Insert a key-value pair into the BTree
.
Examples
Basic usage:
use treers::btree::BalancedTree; use treers::SedgewickMap; let mut btree: BalancedTree<char, i32> = BalancedTree::new(); assert_eq!(btree.is_empty(), true); btree.put('a', 1_i32); assert_eq!(btree.is_empty(), false); assert_eq!(btree.get(&'a'), Some(&1_i32)); assert_eq!(btree[&'a'], 1_i32);
fn height(&self) -> Option<usize>
[src]
Get height of BTree
.
BTree is balanced tree. TODO: add more text
Examples
Basic usage:
use treers::btree::BalancedTree; use treers::SedgewickMap; let mut btree: BalancedTree<char, i32> = BalancedTree::new(); assert_eq!(btree.height(), Some(0_usize)); btree.put('a', 1); btree.put('b', 2); btree.put('c', 3); btree.put('d', 4); btree.put('e', 5); btree.put('f', 6); btree.put('g', 7); // |a|c|e| <-- height: 0 // / | \ // |b| |d| |f|g| <-- height: 1 // // Note -The Height of balanced tree with single node is taken as zero, // but empty BTree is 0, not None. assert_eq!(btree.height(), Some(1_usize)); assert_eq!(btree.get(&'g'), Some(&7_i32)); assert_eq!(btree[&'g'], 7_i32); assert_eq!(btree.size(), 7_usize);
fn min(&self) -> Option<&K>
[src]
Returns a optional reference to minimal key
Examples
Basic usage:
use treers::btree::BalancedTree; use treers::SedgewickMap; let mut btree: BalancedTree<char, i32> = BalancedTree::new(); assert_eq!(btree.min(), None); btree.put('c', 1); btree.put('a', 2); btree.put('b', 3); btree.put('d', 4); assert_eq!(btree.min(), Some(&'a'));
fn max(&self) -> Option<&K>
[src]
Returns a optional reference to maximum key
Examples
Basic usage:
use treers::btree::BalancedTree; use treers::SedgewickMap; let mut btree: BalancedTree<char, i32> = BalancedTree::new(); assert_eq!(btree.max(), None); btree.put('c', 1); btree.put('a', 2); btree.put('b', 3); btree.put('d', 4); assert_eq!(btree.max(), Some(&'d'));
impl<K: Ord, V> SedgewickMap<K, V> for BST<K, V>
[src]
fn new() -> Self
[src]
Inits a new instance of Binary Search Tree.
Examples
Basic usage:
use treers::bst::BST; use treers::SedgewickMap; let bst: BST<char, i32> = BST::new(); assert_eq!(bst.is_empty(), true);
fn size(&self) -> usize
[src]
Returns a size of elements in BST
.
Examples
Basic usage:
use treers::bst::BST; use treers::SedgewickMap; let mut bst: BST<char, i32> = BST::new(); assert_eq!(bst.size(), 0_usize); bst.put('a', 1); bst.put('b', 2); bst.put('c', 3); bst.put('d', 4); assert_eq!(bst.size(), 4_usize);
fn get(&self, key: &K) -> Option<&V>
[src]
Returns a reference to optional reference to value.
Examples
Basic usage:
use treers::bst::BST; use treers::SedgewickMap; let mut bst: BST<char, i32> = BST::new(); bst.put('a', 1); assert_eq!(bst.get(&'a'), Some(&1)); assert_eq!(bst.get(&'b'), None); assert_eq!(bst[&'a'], 1);
fn put(&mut self, key: K, value: V)
[src]
Insert a key-value pair into the BST
.
Examples
Basic usage:
use treers::bst::BST; use treers::SedgewickMap; let mut bst: BST<char, i32> = BST::new(); assert_eq!(bst.is_empty(), true); bst.put('a', 1_i32); assert_eq!(bst.is_empty(), false); assert_eq!(bst.get(&'a'), Some(&1_i32)); assert_eq!(bst[&'a'], 1_i32);
fn height(&self) -> Option<usize>
[src]
Get height of BST
.
BST is not balanced tree, so in worst-case scenario, height will be same as size, like a Linked-List.
Examples
Basic usage:
use treers::bst::BST; use treers::SedgewickMap; let mut bst: BST<char, i32> = BST::new(); bst.put('a', 1); bst.put('b', 2); bst.put('c', 3); bst.put('d', 4); // a <-- height: 0 // / \ // b <-- height: 1 // / \ // c <-- height: 2 // / \ // d <-- height: 3 // Note -The Height of binary tree with single node is taken as zero. assert_eq!(bst.get(&'a'), Some(&1_i32)); assert_eq!(bst.height(), Some(3_usize)); assert_eq!(bst.size(), 4_usize);
fn is_empty(&self) -> bool
[src]
Checks if BST
node is empty.
Examples
Basic usage:
use treers::bst::BST; use treers::SedgewickMap; let mut bst: BST<char, i32> = BST::new(); assert_eq!(bst.is_empty(), true); bst.put('a', 2); assert_eq!(bst.is_empty(), false);
fn min(&self) -> Option<&K>
[src]
Returns a optional reference to minimal key
Examples
Basic usage:
use treers::bst::BST; use treers::SedgewickMap; let mut bst: BST<char, i32> = BST::new(); assert_eq!(bst.min(), None); bst.put('c', 1); bst.put('a', 2); bst.put('b', 3); bst.put('d', 4); assert_eq!(bst.min(), Some(&'a'));
fn max(&self) -> Option<&K>
[src]
Returns a optional reference to maximum key
Examples
Basic usage:
use treers::bst::BST; use treers::SedgewickMap; let mut bst: BST<char, i32> = BST::new(); assert_eq!(bst.max(), None); bst.put('c', 1); bst.put('a', 2); bst.put('b', 3); bst.put('d', 4); assert_eq!(bst.max(), Some(&'d'));