Struct rudac::tree::BinomialTree [−][src]
pub struct BinomialTree<T: Ord> { /* fields omitted */ }
Expand description
A binomial tree of rank(order) k is a general tree with a recursive definition
Bk:
- k = 0: consists of only one node which is the root
- k > 0: consists of one root and children of binomial trees of degrees {B0, B1, … , Bk-1}
Examples
use rudac::tree::BinomialTree;
// create two min binomial trees of rank 0
let bt1 = BinomialTree::init_min(0);
let bt2 = BinomialTree::init_min(1);
// merge two trees and get a binomial tree of rank 1
let merged_tree = BinomialTree::merge(bt1, bt2);
// preorder traversal of the heap is equal to 0 1
assert_eq!(BinomialTree::preorder(&merged_tree), String::from("0 1"));
assert_eq!(merged_tree.rank(), 1);
Implementations
Creates a min binomial tree with rank 0 which holds the payload
.
in this binomial tree each node is smaller than its children
Arguments
payload
- data stored inside the node
Examples
use rudac::tree::BinomialTree;
let bt1 = BinomialTree::init_min(0);
let bt2 = BinomialTree::init_min(1);
let merged_tree = BinomialTree::merge(bt1, bt2);
assert_eq!(BinomialTree::preorder(&merged_tree), String::from("0 1"))
Creates a max binomial tree with rank 0 which holds the payload
.
in this binomial tree each node is greater than its children
Arguments
payload
- data stored inside the node
Examples
use rudac::tree::BinomialTree;
let bt1 = BinomialTree::init_max(0);
let bt2 = BinomialTree::init_max(1);
let merged_tree = BinomialTree::merge(bt1, bt2);
assert_eq!(BinomialTree::preorder(&merged_tree), String::from("1 0"))
Note: this method is for internal use. use init_min or init_max functions instead.
pub fn merge(
binomial_tree_1: BinomialTree<T>,
binomial_tree_2: BinomialTree<T>
) -> BinomialTree<T>
pub fn merge(
binomial_tree_1: BinomialTree<T>,
binomial_tree_2: BinomialTree<T>
) -> BinomialTree<T>
Merges two binomial trees
Arguments
binomial_tree_1
- first binomial treebinomial_tree_2
- second binomial tree
Panics
- panics if rank of two binomial trees are not the same
- panics if trees are of different types(ex. one is min binomial tree and the other is max binomial tree)
Examples
use rudac::tree::BinomialTree;
// create two binomial trees of rank 0
let bt1 = BinomialTree::init_min(0);
let bt2 = BinomialTree::init_min(1);
// merge two trees and get a binomial tree of rank 1
let merged_tree = BinomialTree::merge(bt1, bt2);
// preorder traversal of the heap is equal to 0 1
assert_eq!(BinomialTree::preorder(&merged_tree), "0 1");
assert_eq!(merged_tree.rank(), 1);
Returns rank of the binomial tree
Examples
use rudac::tree::BinomialTree;
let bt = BinomialTree::init_min("rudac is awesome");
assert_eq!(bt.rank(), 0);
Returns true if binomial tree is initialized as a min binomial tree
Examples
use rudac::tree::BinomialTree;
let bt1 = BinomialTree::init_min("rudac is awesome");
let bt2 = BinomialTree::init_max("rudac is cute");
assert_eq!(bt1.is_min(), true);
assert_eq!(bt2.is_min(), false);
Returns true if binomial tree is initialized as a max binomial tree
Examples
use rudac::tree::BinomialTree;
let bt1 = BinomialTree::init_min("rudac is awesome");
let bt2 = BinomialTree::init_max("rudac is cute");
assert_eq!(bt1.is_max(), false);
assert_eq!(bt2.is_max(), true);
Returns a reference to payload
Examples
use rudac::tree::BinomialTree;
let mut bt = BinomialTree::init_min("rudac is awesome");
assert_eq!(*bt.peek_payload(), Some("rudac is awesome"));
Compares payloads which reside in roots of two binomial trees first
and other
.
Returns true if payload of first
is smaller or equal than payload of other
Examples
use rudac::tree::BinomialTree;
let bt1 = BinomialTree::init_min(0);
let bt2 = BinomialTree::init_min(1);
assert_eq!(true, BinomialTree::is_smaller_or_equal(&bt1, &bt2));
assert_eq!(false, BinomialTree::is_smaller_or_equal(&bt2, &bt1));
Compares payloads which reside in roots of two binomial trees first
and other
.
Returns true if payload of first
is greater or equal than payload of other
Examples
use rudac::tree::BinomialTree;
let bt1 = BinomialTree::init_min(0);
let bt2 = BinomialTree::init_min(1);
assert_eq!(false, BinomialTree::is_greater_or_equal(&bt1, &bt2));
assert_eq!(true, BinomialTree::is_greater_or_equal(&bt2, &bt1));
Returns a mutable reference to vector of children
Returns an immutable reference to vector of children
Returns the preorder representation of the heap
Arguments
root
: root of the binomial tree
Examples
use rudac::tree::BinomialTree;
let bt1 = BinomialTree::init_min(0);
let bt2 = BinomialTree::init_min(1);
let merged_tree_1 = BinomialTree::merge(bt1, bt2);
let bt3 = BinomialTree::init_min(2);
let bt4 = BinomialTree::init_min(3);
let merged_tree_2 = BinomialTree::merge(bt3, bt4);
let merged_tree = BinomialTree::merge(merged_tree_1, merged_tree_2);
assert_eq!(
BinomialTree::preorder(&merged_tree),
String::from("0 1 2 3")
);