Struct Walk

pub struct Walk<'r, TP: TreeProperties, D = (), A = ()> { /* private fields */ }

Walk tree

Some algorithms need to remember how they reached the current node via WalkedDirection as D.

When walking manually it might be useful to be able to store additional data via A; look for functions with the suffix _with.

Implementations

impl<'r, TP: TreeProperties, D, A> Walk<'r, TP, D, A>

pub fn up(&mut self) -> Option<D>

Walk up to parent node or tree if not at tree

pub fn up_with(&mut self) -> Option<(D, A)>

Walk up to parent node or tree if not at tree

pub fn current(&self) -> NodeOrTree<Option<&'r Node<TP>>, &'r Node<TP>>

Current node or tree

impl<'r, TP: TreeProperties, D, A> Walk<'r, TP, D, A>

where D: From<WalkedDirection>,

pub fn down_root_with(&mut self, add: A) -> bool

Walk down from tree to root node (if present)

pub fn down_left_with(&mut self, add: A) -> bool

Walk down to left node if present and not currently at tree

pub fn down_right_with(&mut self, add: A) -> bool

Walk down to right node if present and not currently at tree

pub fn down_with(&mut self, side: bool, add: A) -> bool

Walk down to specified node if present and not currently at tree

false picks left and true picks right.

impl<'r, TP: TreeProperties, D> Walk<'r, TP, D, ()>

where D: From<WalkedDirection>,

pub fn down_root(&mut self) -> bool

Walk down from tree to root node (if at tree and not empty)

pub fn down_left(&mut self) -> bool

Walk down to left node if present and not currently at tree

pub fn down_right(&mut self) -> bool

Walk down to right node if present and not currently at tree

pub fn down(&mut self, side: bool) -> bool

Walk down to specified node if present and not currently at tree

false picks left and true picks right.

impl<'r, TP: TreeProperties, D> Walk<'r, TP, D>

where D: From<WalkedDirection>,

pub fn goto_insert(&mut self, key: &TP::Key) -> Option<InsertPosition>

Walk to node where we’d have to insert key at

This can either be:

• root if and only if the tree is empty
• node with exactly matching key
• node where the key is between the parent node (possibly root) and the node
  • to insert the key here we might have to create a new inner node and move the existing node down

impl<'r, TP: TreeProperties> Walk<'r, TP, WalkedDirection>

pub fn next_pre_order(&mut self) -> Option<&'r Node<TP>>

Tree traversal: depth-first pre-order

pub fn next_in_order(&mut self) -> Option<&'r Node<TP>>

Tree traversal: depth-first in-order

pub fn next_leaf(&mut self) -> Option<&'r Node<TP>>

Tree traversal: depth-first in-order leaf nodes only

pub fn next_post_order(&mut self) -> Option<&'r Node<TP>>

Tree traversal: depth-first post-order