Struct RedBlackTree 

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

A Red-black tree which is an approximately balanced binary search tree.

All RedBlackTree tree binary search tree operations: insert, remove, contains, min, max, predecessor, successor have a worst case time complexity of O(log n).

Implementations

impl<T> RedBlackTree<T>

pub fn new() -> Self

Returns an empty RedBlackTree.

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

where T: Ord,

Inserts the given value into the tree. Duplicates are permitted and will lead to duplicate values in the tree.

This operation is O(log n).

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

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

Removes the first pre-order node with the given value from the tree, returning the removed value, if there was one to remove.

This operation is O(log n).

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

Returns the minimum value, returning None if the tree is empty.

This operation is O(log n). To obtain the node with the minimum value &Node<T> use max_node().

pub fn extract_min(&mut self) -> Option<T>

where T: Ord,

Removes and returns the minimum value, returning None if the tree is empty.

This operation is O(log n). If the minimum value is not unique in the tree, the first pre-order node is removed. To obtain the value without removing it use min().

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

Returns the maximum value, returning None if the tree is empty.

This operation is O(log n). To obtain the node with the maximum value, use max_node().

pub fn extract_max(&mut self) -> Option<T>

where T: Ord,

Removes and returns the maximum value, returning None if the tree is empty.

This operation is O(log n). If the maximum value is not unique in the tree, the first pre-order node is removed. To obtain the value without removing it use max().

pub fn predecessor<'t>(&self, t: &'t T) -> Option<&T>

where T: Ord,

Returns the predecessor value, which is the previous in-order value, of the given value.

This operation is O(log n). To obtain the predecessor node, use get_node(t).map_or_default(|n| n.predecessor()).

pub fn successor<'t>(&self, t: &'t T) -> Option<&T>

where T: Ord,

Returns the successor value, which is the next in-order value, of the given value.

This operation is O(log n). To obtain the successor node, use get_node(t).map_or_default(|n| n.successor()).

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

where T: Ord,

Returns true if the tree contains the given value.

This operation is O(log n).

pub fn clear(&mut self)

Removes all values from the tree.

This operation is O(n) and is equivalent to dropping the tree and creating a new one.

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

Returns the root value of the tree.

This operation is O(1). To obtain the root node, use root_node().

pub fn len(&self) -> usize

Returns the number of elements in the tree.

pub fn is_empty(&self) -> bool

Returns true if the tree contains no elements.

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

Returns an in-order iterator over shared references of the values in the tree.

Iterator creation is O(1).

impl<T> RedBlackTree<T>

pub fn get_node<'a, Q>(&'a self, q: &Q) -> Option<&'a Node<T>>

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

Finds the node with the given value in the tree and returns it, if it exists.

This operation is O(n). If you only need to know whether the value exists, use contains().

pub fn min_node(&self) -> Option<&Node<T>>

Returns the node with the minimum value.

This operation is O(log n). To obtain the value directly, use min.

pub fn max_node(&self) -> Option<&Node<T>>

Returns the node with the maximum value.

This operation is O(log n). To obtain the value directly, use max.

pub fn root_node(&self) -> Option<&Node<T>>

Returns the root value of the tree.

This operation is O(1).

pub fn iter_node(&self) -> IterNode<'_, T>

Returns an in-order iterator over shared references of the nodes in the tree.

Iterator creation is O(1).

Trait Implementations

impl<T: Clone> Clone for RedBlackTree<T>

fn clone(&self) -> Self

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl<T: Debug> Debug for RedBlackTree<T>

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

Formats the value using the given formatter.

impl<T> Default for RedBlackTree<T>

fn default() -> Self

Returns the “default value” for a type.

impl<T: Display> Display for RedBlackTree<T>

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

Formats the value using the given formatter.

impl<T> Drop for RedBlackTree<T>

fn drop(&mut self)

Executes the destructor for this type.

fn pin_drop(self: Pin<&mut Self>)

🔬This is a nightly-only experimental API. (pin_ergonomics)

Execute the destructor for this type, but different to Drop::drop, it requires self to be pinned.

impl<T: Eq> Eq for RedBlackTree<T>

impl<A: Ord> Extend<A> for RedBlackTree<A>

fn extend<T: IntoIterator<Item = A>>(&mut self, iter: T)

Extends a collection with the contents of an iterator.

fn extend_one(&mut self, item: A)

🔬This is a nightly-only experimental API. (extend_one)

Extends a collection with exactly one element.

fn extend_reserve(&mut self, additional: usize)

🔬This is a nightly-only experimental API. (extend_one)

Reserves capacity in a collection for the given number of additional elements.

impl<A: Ord> FromIterator<A> for RedBlackTree<A>

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

Creates a value from an iterator.

impl<'a, T> IntoIterator for &'a RedBlackTree<T>

type Item = &'a T

The type of the elements being iterated over.

type IntoIter = Iter<'a, T>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<T> IntoIterator for RedBlackTree<T>

type Item = T

The type of the elements being iterated over.

type IntoIter = IntoIter<T>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<T: PartialEq> PartialEq for RedBlackTree<T>

fn eq(&self, other: &Self) -> bool

Equality operator ==.

fn ne(&self, other: &Rhs) -> bool

Inequality operator !=.

impl<T: Send> Send for RedBlackTree<T>

impl<T: Sync> Sync for RedBlackTree<T>