Struct truetree::AvlTree

pub struct AvlTree<T: Clone + Ord + Eq + Debug + Display + Hash> { /* fields omitted */ }

Implementations

impl<'a, T: 'a + Clone + Ord + Eq + Debug + Display + Hash> AvlTree<T>

This is a balanced tree implementation (also called as AVL tree) We allow you to define a custom type T to pass a the tree payload This payload should have the clone, ord, eq, debug and display trait derived The Ord trait is used to insert the values and to get it (this allow to match only partial payload) The Eq trait is used to remove a node The Clone trait is used to copy the value inside the tree The Display trait is used to print/dump the tree

pub fn new() -> Self

Create a new tree (a tree is defined as an optional heap pointer to a Node of type T) By default we made a wrapper around the internal implementation with a root node

pub fn with(value: &T) -> Self

Create a new tree (a tree is defined as an optional heap pointer to a Node of type T) with a default value, all value passed are cloned and should implement Clone, Ord, Eq and Debug There is an example of such Payload creation in integration_avl

pub fn insert(&mut self, value: &T) -> Result<&mut Self, &str>

Insert a value in the tree and return itself if no errors (by default we allow duplicate key value (using Eq trait, not Ord) You can chain multiple insert

pub fn delete(self)

Delete all the values in the tree, the structure holding the tree should theoretically not be reused This is effectively the same as clear()

pub fn clear(&mut self)

Delete all the values in the tree, the structure holding the tree can be reused afterwards This is effectively the same as delete()

pub fn remove(&mut self, value: &T) -> Result<&mut Self, &str>

Remove a value from the tree and return itself if was successful else return an error Warning we use Eq to remove the correct value, if you don't know all the fields, use the get which use Ord only See integration for an example.

pub fn print(&self, prettify: bool)

Print the tree as a JSON formatted string, It's possible to prettify it with the boolean

pub fn dump(&self, prettify: bool) -> Result<String, &str>

Dump the tree as a JSON formatted string, It's possible to prettify it with the boolean

pub fn get(&self, value: &T) -> Option<T>

Get a value based only on Ord (not Eq), this allow loosy check in case of complex payload This return only the value or none, for a subtree see find If duplicate keys this will return only the tree ordered first one

pub fn get_exact(&self, value: &T) -> Option<T>

Get a value based only on Ord (not Eq), this allow loosy check in case of complex payload This return only the value or none, for a subtree see find If duplicate keys this will return the exact match if any else None

pub fn get_set(&self, value: &T) -> HashSet<T>

Get the set of value based only on Ord (not Eq), this allow loosy check in case of complex payload This return only the value or none, for a subtree see find

pub fn find(&self, value: &T) -> Result<Self, &str>

Find a value and return it as the subtree (equivalent as get but allow to chain operation on the subtree) Warning this is Ord based so if there is duplicate you might get the wrong value here but you can check the duplicates to find it

pub fn contains(&self, value: &T) -> bool

Check if a value is contained in the tree with Ord trait only

pub fn contains_exact(&self, value: &T) -> bool

Check if a value is contained in the tree with Eq trait

pub fn is_empty(&self) -> bool

Check if the tree is empty or not

pub fn fail(&mut self) -> Result<&mut Self, &str>

Failing case for test

pub fn works(&mut self) -> Result<&mut Self, &str>

Working case for test

pub fn height(&self) -> usize

Return the height of the tree as a fast heuristic (this could be wrong if you tampered the tree)

pub fn depth(&self) -> usize

Return the true depth of the tree by going through all the nodes

pub fn width(&self) -> usize

Get the number of leaves, a leave is a node which has one or more children missing (so a node with only one child is a leave also) 1 1 \ /
2 2 3 Those have a width of 2

pub fn count(&self) -> usize

Get the number of nodes in the tree

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

Get the minimum of the tree (or the left most)

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

Get the maximum of the tree (or the right most)

pub fn is_balanced(&self) -> bool

Check if the tree is balanced (this is quite intensive but gave correct result)

pub fn is_correct(&self) -> bool

Check if the heights are correct (might have not be registered correctly, this is a soft check)

Trait Implementations

impl<T: Clone + Ord + Eq + Debug + Display + Hash> Clone for AvlTree<T>

pub fn clone(&self) -> AvlTree<T>

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<T: Debug + Clone + Ord + Eq + Display + Hash> Debug for AvlTree<T>

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

Formats the value using the given formatter.

impl<T: PartialEq + Clone + Ord + Eq + Debug + Display + Hash> PartialEq<AvlTree<T>> for AvlTree<T>

pub fn eq(&self, other: &AvlTree<T>) -> bool

This method tests for self and other values to be equal, and is used by ==.

pub fn ne(&self, other: &AvlTree<T>) -> bool

This method tests for !=.

impl<T: Clone + Ord + Eq + Debug + Display + Hash> StructuralPartialEq for AvlTree<T>