Enum rust_examples::adts::Tree

pub enum Tree<'a, K, V> {
    Leaf(K, &'a V),
    Node {
        key: K,
        data: &'a V,
        left: Box<Self>,
        right: Box<Self>,
    },
}

An enum representing an Binary Tree Algebraic Data Type (ADT)

This enum defined two distinct types (variants), each of different shape and size:

1. The Tree::Leaf representing a leaf node that wraps (key, ref data)
2. Variant Tree::Node representing an inner node with key and reference to underlying data. Additionally, inner nodes contain references to two heap-allocated child trees.

Notice that the reference to the data must live at least as long as an instance of a tree. This ensures that nodes of any tree will always point to a valid memory section.

An enum is Rust’s version of what in Haskell is called a type constructor while individual variants would be respective data constructors. For instance the definition of Tree below would roughly translate to the following Haskell code (Haskell is a GC language where all values are allocated on the heap so all the reference jugglinlg is hidden away and infinite data structures are possible and common):

data Tree k v = Leaf k v | Node { key :: k, data :: v, left :: (Tree k v), right :: (Tree k v) }

Variants

Leaf(K, &'a V)

Tuple Fields

0: K

1: &'a V

Node

Fields

key: K

data: &'a V

left: Box<Self>

right: Box<Self>

Implementations

impl<'a, K: PartialEq + Eq, V> Tree<'a, K, V>

Note: By not requiring K to be PartialEq on the Tree type itself, we allow users to create tree instances (which is totally valid) but without the option to lookup data by keys.

pub fn search(&self, lookup_key: &K) -> Option<&'a V>

Lookup method that returns either:

• reference to the underlying data if the lookup_key was found
• None if this BST does not contain node or leaf with lookup_key

Trait Implementations

impl<'a, K: Debug, V: Debug> Debug for Tree<'a, K, V>

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

Formats the value using the given formatter.