Struct Tree 

pub struct Tree { /* private fields */ }

A radix-4 tree.

Implementations

impl Tree

pub fn nb_nodes_for_leaves(nb_leaves: usize) -> usize

Calculate the total number of nodes a tree would have for the given number of leaves.

pub fn new(nb_leaves: usize) -> Tree

pub fn nb_leaves(&self) -> usize

pub fn nb_nodes(&self) -> usize

pub fn nb_internal_nodes(&self) -> usize

The number of internal nodes

pub fn node_at(&self, node_idx: usize) -> &Node

pub fn root(&self) -> &Node

pub fn iter(&self) -> Iter<'_, Node>

Iterate over all nodes, starting with the leaves, towards the root.

pub fn iter_internal(&self) -> Iter<'_, Node>

Iterate over all internal nodes, starting with the ones right beyond the leaves, towards the root.

pub fn into_iter(self) -> IntoIter<Node>

Iterate over all nodes, starting with the leaves, towards the root.

pub fn iter_branch(&self, leaf_idx: usize) -> BranchIter<'_>

Iterate nodes over a branch starting at the leaf with index leaf_idx ending in the root.

pub fn iter_branch_with_output( &self, node_idx: usize, ) -> BranchWithOutputIter<'_>

Iterate over ancestors of a node with child indices.

Starting from node_idx, walks up towards the root. The starting node is excluded from iteration. Each returned tuple (ancestor_idx, child_idx) indicates that child_idx is the child position that leads back down towards node_idx.

Example

For a node 12 with children [4, 5, 6, 7]:

iter_branch_with_output(6) yields (12, 2), ..., (root_idx, ...)

Node 6 is at child index 2 (0-indexed) of node 12.

pub fn parent_idx_of(&self, idx: usize) -> Option<usize>

pub fn parent_idx_of_with_sibling_idx( &self, idx: usize, ) -> Option<(usize, usize)>

Returns index of the the parent of the node with given idx, and the index of the node among its siblings.

Trait Implementations

impl Clone for Tree

fn clone(&self) -> Tree

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl Debug for Tree

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

Formats the value using the given formatter.