Struct rudac::tree::BinomialTree

pub struct BinomialTree<T: Ord> { /* fields omitted */ }

A binomial tree of rank(order) k is a general tree with a recursive definition

B_k:

• k = 0: consists of only one node which is the root
• k > 0: consists of one root and children of binomial trees of degrees {B₀, B₁, ... , B_k-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

impl<T: Ord> BinomialTree<T>

pub fn init_min(payload: T) -> BinomialTree<T>

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"))

pub fn init_max(payload: T) -> BinomialTree<T>

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"))

pub fn init(payload: T, min: bool) -> BinomialTree<T>

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>

Merges two binomial trees

Arguments

• binomial_tree_1 - first binomial tree
• binomial_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);

pub fn rank(&self) -> usize

Returns rank of the binomial tree

Examples

use rudac::tree::BinomialTree;

let bt = BinomialTree::init_min("rudac is awesome");

assert_eq!(bt.rank(), 0);

pub fn is_min(&self) -> bool

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);

pub fn is_max(&self) -> bool

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);

pub fn get_payload(&mut self) -> T

Extracts and returns the payload from the node and replaces it with None

Panics

• panics if payload is None

Examples

use rudac::tree::BinomialTree;

let mut bt = BinomialTree::init_min("rudac is awesome");

assert_eq!(bt.get_payload(), "rudac is awesome");

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

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"));

pub fn is_smaller_or_equal(
    first: &BinomialTree<T>,
    other: &BinomialTree<T>
) -> bool

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));

pub fn is_greater_or_equal(
    first: &BinomialTree<T>,
    other: &BinomialTree<T>
) -> bool

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));

pub fn children_mut(&mut self) -> &mut Vec<Option<BinomialTree<T>>>

Returns a mutable reference to vector of children

pub fn children(&self) -> &Vec<Option<BinomialTree<T>>>

Returns an immutable reference to vector of children

impl<T: Ord + Display> BinomialTree<T>

pub fn preorder(root: &BinomialTree<T>) -> String

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")
);

Trait Implementations

impl<T: Debug + Ord> Debug for BinomialTree<T>

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

Formats the value using the given formatter.