Struct AVLTree

pub struct AVLTree<T> {
    pub arena: Vec<Option<AVLNode<T>>>,
    /* private fields */
}

About

See the module-level documentation for more information.

Fields

arena: Vec<Option<AVLNode<T>>>

Implementations

impl<T> AVLTree<T>

where T: Ord,

pub fn new() -> Self

Creates a new, empty binary search tree.

pub fn new_with_capacity(size: usize) -> Self

Creates a new, empty binary search tree with a given (growable) initial capacity.

pub fn get_node<Q>(&self, key: &Q) -> Option<&T>

where Q: Ord + ?Sized, T: Borrow<Q>,

Gets a reference to the value of a key, if Some.

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

pub fn contains<Q>(&self, key: &Q) -> bool

where Q: Ord + ?Sized, T: Borrow<Q>,

Returns true if the key exists in the tree.

pub fn insert(&mut self, key: T)

where T: Ord,

Inserts the given key into the tree maintaining an AVL structure.

NOTE: Does not handle duplicate keys by convention, but may overwrite values for arbitrarily complex T with custom Ordering.

pub fn remove<Q>(&mut self, key: &Q) -> Option<T>

where Q: Ord + ?Sized, T: Borrow<Q>,

Removes and returns an element from the AVL tree as an owned value.

pub fn iter(&self) -> InOrderIter<'_, T>

Produces a “snapshot” iterator over immutable references to the tree in its current state.

Trait Implementations

impl<T: Debug> Debug for AVLTree<T>

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

Formats the value using the given formatter.

impl<T> Default for AVLTree<T>

where T: Ord,

fn default() -> Self

Returns the “default value” for a type.