Struct AVL

pub struct AVL<T> { /* private fields */ }

Description

An AVL tree is a self-balancing binary search tree that maintains a height difference of at most 1 between its left and right subtrees. This property ensures that the tree remains balanced, which in turn guarantees that the time complexities of insertion, deletion,lookup are all O(log(n)) Compared to normal binary search trees, AVL trees provide faster lookups and insertions, but slower deletions. Compared to heaps, AVL trees are more strictly balanced, which makes them faster for lookups, but slower for insertions and deletions.

Time complexities

The following table shows the time complexities of various operations in an AVL tree:

Operation	Time complexity
Insertion	O(log n)
Deletion	O(log n)
Lookup	O(log n)

Implementations

impl<T> AVL<T>

pub fn new() -> Self

Creates and returns a new AVL tree

pub fn len(&self) -> usize

Returns the number of nodes in this AVL tree. This operation has a strict time complexity of O(1)

pub fn height(&self) -> usize

pub fn clear(&mut self)

pub fn levels(&self) -> impl Iterator<Item = impl Iterator<Item = Option<&T>>>

pub fn iter(&self) -> impl Iterator<Item = &T>

pub fn increasing(&self) -> impl Iterator<Item = &T>

Returns an in-order traversal iterator over the elements in the binary tree. This ensures the returned values are in an increasing order according to their implementation of the Ord trait.

Although this implementation does not make the iterator lazy, that is, initializing this iterator uses time complexity of O(log(n)), it makes the average time complexity of next be amortized O(1) with worst case scenario of O(log(n)) and ratio of average case to worst case is 1: log(n). More generally speaking, this implementation performs better than other implementations and also uses no extra space.

pub fn into_increasing(self) -> impl Iterator<Item = T>

pub fn into_decreasing(self) -> impl Iterator<Item = T>

pub fn decreasing(&self) -> impl Iterator<Item = &T>

pub fn is_empty(&self) -> bool

impl<T: Ord> AVL<T>

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

pub fn insert_distinct(&mut self, val: T) -> bool

pub fn delete(&mut self, val: &T) -> bool

pub fn union(self, other: Self) -> Self

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

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

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

traverses the binary search tree and returns the minimum value.

pub fn nearest_to<'a, F>(&'a self, target: &'a T, by: F) -> Option<&'a T>

where F: 'static + Fn(&'a T, &'a T) -> &'a T, T: 'a,

pub fn farthest_to<'a, F>(&'a self, target: &'a T, by: F) -> Option<&'a T>

where F: 'static + Fn(&'a T, &'a T) -> &'a T, T: 'a,

pub fn greater_than<'a>(&'a self, lower: &'a T) -> impl Iterator<Item = &'a T>

pub fn less_than<'a>(&'a self, upper: &'a T) -> impl Iterator<Item = &'a T>

impl<T: Ord + Nearness> AVL<T>

pub fn nearest<'a>(&'a self, target: &'a T) -> Option<&'a T>

pub fn farthest<'a>(&'a self, target: &'a T) -> Option<&'a T>

Trait Implementations

impl<T: Clone> Clone for AVL<T>

fn clone(&self) -> AVL<T>

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<T: Debug> Debug for AVL<T>

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

Formats the value using the given formatter.

impl<T: Ord> FromIterator<T> for AVL<T>

fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self

Creates a value from an iterator.

impl<T> IntoIterator for AVL<T>

type IntoIter = IntoIter<T>

Which kind of iterator are we turning this into?

type Item = T

The type of the elements being iterated over.

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.