Struct VEBTree

pub struct VEBTree { /* private fields */ }

The van Emde Boas tree itself.

Implementations

impl VEBTree

pub fn new(max_elem: i64) -> Result<Self, &'static str>

Generates a new van Emde Boas tree. Will return an error if the input is less than 1 or greater than the max value of an isize.

pub fn minimum(&self) -> Option<i64>

Returns the lowest value stored in the tree, or None if it’s empty. Takes constant time.

pub fn maximum(&self) -> Option<i64>

Returns the highest value stored in the tree, or None if it’s empty. Takes constant time.

pub fn universe(&self) -> i64

Returns the maximum value it’s possible to store in the tree. Takes constant time.

pub fn is_empty(&self) -> bool

Returns true if the tree is empty. Takes constant time.

pub fn has(&self, x: i64) -> bool

Returns true if this van Emde Boas tree contains the specified value. Takes O(log(log(U))) time, where U is the argument to the constructor.

pub fn find_next(&self, x: i64) -> Option<i64>

Finds the next highest value in this van Emde Boas tree, or None if it doesn’t exit. Takes O(log(log(U))) time, where U is the argument to the constructor.

pub fn insert(&mut self, x: i64)

Insert a value into this van Emde Boas tree. Takes O(log(log(U))) time, where U is the argument to the constructor.

pub fn delete(&mut self, x: i64)

Removes an element from this van Emde Boas tree. Takes O(log(log(U))) time, where U is the argument to the constructor.

Trait Implementations

impl Clone for VEBTree

fn clone(&self) -> VEBTree

Returns a copy of the value.

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

Performs copy-assignment from source.

impl Debug for VEBTree

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

Formats the value using the given formatter.