Struct binary_tree::count::CountTree

pub struct CountTree<T>(_);

Counting tree.

A balanced binary tree which keeps track of total number of child nodes in each node, so that elements can be inserted and deleted using its in-order index. The algorithm used internally is a variation of AVL Tree. Time complexities mentioned below are that of worst case scenario (and are of the same order as that of an AVL tree).

Examples

let mut ct: CountTree<i32> = CountTree::new();
ct.push_front(20);
ct.push_front(10);
assert_eq!(ct.pop_back().unwrap(), 20);

You can also use collect to create one from an iterator. This has a time complexity of O(n), which is much more efficient than inserting iteratively.

let mut ct: CountTree<i32> = (0..100).collect();
assert_eq!(ct.remove(32), 32);

Methods

impl<T> CountTree<T>

fn new() -> CountTree<T>

Returns an empty CountTree

fn is_empty(&self) -> bool

Returns true if the tree contains no elements.

fn len(&self) -> usize

Returns the number elements in the tree. Time complexity: O(1)

fn clear(&mut self)

Clears the tree, dropping all elements iteratively.

fn get(&self, index: usize) -> Option<&T>

Returns the element at the given index, or None if index is out of bounds. Time complexity: O(log(n))

fn get_mut(&mut self, index: usize) -> Option<&mut T>

Returns a mutable reference to the element at the given index, or None if out of bounds. Time complexity: O(log(n))

fn insert(&mut self, index: usize, value: T)

Inserts an element at the given index. Time complexity: O(log(n))

Panics

Panics if index is greater than self.len()

fn push_front(&mut self, value: T)

Prepends an element at the beginning.

fn push_back(&mut self, value: T)

Appends an element at the end.

fn remove(&mut self, index: usize) -> T

Removes the element at the given index. Time complexity: O(log(n))

Panics

Panics if index is out of bounds.

fn pop_front(&mut self) -> Option<T>

Removes and returns the first element, or None if empty.

fn pop_back(&mut self) -> Option<T>

Removes and returns the last element, or None if empty.

Trait Implementations

impl<T> BinaryTree for CountTree<T>

type Node = CountNode<T>

fn root(&self) -> Option<&Self::Node>

impl<T> Debug for CountTree<T> where T: Debug

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

impl<T> Drop for CountTree<T>

fn drop(&mut self)

impl<T> FromIterator<T> for CountTree<T>

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

Time complexity: Θ(n + log²(n))

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

type Item = &'a T

type IntoIter = Iter<'a, T>

fn into_iter(self) -> Self::IntoIter

impl<T> IntoIterator for CountTree<T>

type Item = T

type IntoIter = IntoIter<T>

fn into_iter(self) -> Self::IntoIter