Skip to main content

AvlTree

avlsort::tree

Struct AvlTree 

Source 
pub struct AvlTree<T> {
    pub root: Option<AvlNode<T>>,
}
Expand description

AVL tree.

Fields§

§root: Option<AvlNode<T>>

Root node.

Implementations§

Source§

impl<T: TreeElem> AvlTree<T>

Source

pub fn new() -> Self

Create an empty AVL tree.

Examples found in repository?
examples/avl.rs (line 5)
3fn main() {
4    let v = vec![1, 8, 7, 3, 5, 6, 2, 9, 4, 0, 4, 9];
5    let mut g = AvlTree::new();
6    println!("=== Push values in v. ===");
7    for &i in v.iter() {
8        let (rank, dup) = g.push(i);
9        println!("value={}| rank={}, dup={}", i, rank, dup);
10    }
11    println!("Elements in the tree = {}", g.len());
12    println!("");
13
14    println!("Height of the tree = {}", g.height());
15    println!("How many 4?: {}", g.count(4));
16    println!("remove 4: {:?}", g.remove(4));
17    println!("4 is in?: {}", g.isin(4));
18    println!("remove 4: {:?}", g.remove(4));
19    println!("4 is in?: {}", g.isin(4));
20    println!("");
21
22    println!("Max value = {}", g.max().unwrap());
23    let (value, dup) = g.pop_max_all().unwrap();
24    println!("Pop all the max value: value={}, dup={}", value, dup);
25    println!("");
26
27    println!("=== Show elements in ascending order. ===");
28    loop {
29        match g.pop_min() {
30            Some(value) => println!("Min value = {}", value),
31            None => break,
32        }
33    }
34}
Source

pub fn push(&mut self, value: T) -> (usize, usize)

Push value and return the rank and the number of duplication of it.

Examples found in repository?
examples/avl.rs (line 8)
3fn main() {
4    let v = vec![1, 8, 7, 3, 5, 6, 2, 9, 4, 0, 4, 9];
5    let mut g = AvlTree::new();
6    println!("=== Push values in v. ===");
7    for &i in v.iter() {
8        let (rank, dup) = g.push(i);
9        println!("value={}| rank={}, dup={}", i, rank, dup);
10    }
11    println!("Elements in the tree = {}", g.len());
12    println!("");
13
14    println!("Height of the tree = {}", g.height());
15    println!("How many 4?: {}", g.count(4));
16    println!("remove 4: {:?}", g.remove(4));
17    println!("4 is in?: {}", g.isin(4));
18    println!("remove 4: {:?}", g.remove(4));
19    println!("4 is in?: {}", g.isin(4));
20    println!("");
21
22    println!("Max value = {}", g.max().unwrap());
23    let (value, dup) = g.pop_max_all().unwrap();
24    println!("Pop all the max value: value={}, dup={}", value, dup);
25    println!("");
26
27    println!("=== Show elements in ascending order. ===");
28    loop {
29        match g.pop_min() {
30            Some(value) => println!("Min value = {}", value),
31            None => break,
32        }
33    }
34}
Source

pub fn isin(&self, value: T) -> bool

Determine if value exists.

Examples found in repository?
examples/avl.rs (line 17)
3fn main() {
4    let v = vec![1, 8, 7, 3, 5, 6, 2, 9, 4, 0, 4, 9];
5    let mut g = AvlTree::new();
6    println!("=== Push values in v. ===");
7    for &i in v.iter() {
8        let (rank, dup) = g.push(i);
9        println!("value={}| rank={}, dup={}", i, rank, dup);
10    }
11    println!("Elements in the tree = {}", g.len());
12    println!("");
13
14    println!("Height of the tree = {}", g.height());
15    println!("How many 4?: {}", g.count(4));
16    println!("remove 4: {:?}", g.remove(4));
17    println!("4 is in?: {}", g.isin(4));
18    println!("remove 4: {:?}", g.remove(4));
19    println!("4 is in?: {}", g.isin(4));
20    println!("");
21
22    println!("Max value = {}", g.max().unwrap());
23    let (value, dup) = g.pop_max_all().unwrap();
24    println!("Pop all the max value: value={}, dup={}", value, dup);
25    println!("");
26
27    println!("=== Show elements in ascending order. ===");
28    loop {
29        match g.pop_min() {
30            Some(value) => println!("Min value = {}", value),
31            None => break,
32        }
33    }
34}
Source

pub fn count(&self, value: T) -> usize

Count the number of value.

Examples found in repository?
examples/avl.rs (line 15)
3fn main() {
4    let v = vec![1, 8, 7, 3, 5, 6, 2, 9, 4, 0, 4, 9];
5    let mut g = AvlTree::new();
6    println!("=== Push values in v. ===");
7    for &i in v.iter() {
8        let (rank, dup) = g.push(i);
9        println!("value={}| rank={}, dup={}", i, rank, dup);
10    }
11    println!("Elements in the tree = {}", g.len());
12    println!("");
13
14    println!("Height of the tree = {}", g.height());
15    println!("How many 4?: {}", g.count(4));
16    println!("remove 4: {:?}", g.remove(4));
17    println!("4 is in?: {}", g.isin(4));
18    println!("remove 4: {:?}", g.remove(4));
19    println!("4 is in?: {}", g.isin(4));
20    println!("");
21
22    println!("Max value = {}", g.max().unwrap());
23    let (value, dup) = g.pop_max_all().unwrap();
24    println!("Pop all the max value: value={}, dup={}", value, dup);
25    println!("");
26
27    println!("=== Show elements in ascending order. ===");
28    loop {
29        match g.pop_min() {
30            Some(value) => println!("Min value = {}", value),
31            None => break,
32        }
33    }
34}
Source

pub fn remove(&mut self, value: T) -> Result<(), ()>

Remove value from the tree and return the result.

If value is a duplicate, return and remove only one.

Examples found in repository?
examples/avl.rs (line 16)
3fn main() {
4    let v = vec![1, 8, 7, 3, 5, 6, 2, 9, 4, 0, 4, 9];
5    let mut g = AvlTree::new();
6    println!("=== Push values in v. ===");
7    for &i in v.iter() {
8        let (rank, dup) = g.push(i);
9        println!("value={}| rank={}, dup={}", i, rank, dup);
10    }
11    println!("Elements in the tree = {}", g.len());
12    println!("");
13
14    println!("Height of the tree = {}", g.height());
15    println!("How many 4?: {}", g.count(4));
16    println!("remove 4: {:?}", g.remove(4));
17    println!("4 is in?: {}", g.isin(4));
18    println!("remove 4: {:?}", g.remove(4));
19    println!("4 is in?: {}", g.isin(4));
20    println!("");
21
22    println!("Max value = {}", g.max().unwrap());
23    let (value, dup) = g.pop_max_all().unwrap();
24    println!("Pop all the max value: value={}, dup={}", value, dup);
25    println!("");
26
27    println!("=== Show elements in ascending order. ===");
28    loop {
29        match g.pop_min() {
30            Some(value) => println!("Min value = {}", value),
31            None => break,
32        }
33    }
34}
Source

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

Return the maximum value in the tree.

Examples found in repository?
examples/avl.rs (line 22)
3fn main() {
4    let v = vec![1, 8, 7, 3, 5, 6, 2, 9, 4, 0, 4, 9];
5    let mut g = AvlTree::new();
6    println!("=== Push values in v. ===");
7    for &i in v.iter() {
8        let (rank, dup) = g.push(i);
9        println!("value={}| rank={}, dup={}", i, rank, dup);
10    }
11    println!("Elements in the tree = {}", g.len());
12    println!("");
13
14    println!("Height of the tree = {}", g.height());
15    println!("How many 4?: {}", g.count(4));
16    println!("remove 4: {:?}", g.remove(4));
17    println!("4 is in?: {}", g.isin(4));
18    println!("remove 4: {:?}", g.remove(4));
19    println!("4 is in?: {}", g.isin(4));
20    println!("");
21
22    println!("Max value = {}", g.max().unwrap());
23    let (value, dup) = g.pop_max_all().unwrap();
24    println!("Pop all the max value: value={}, dup={}", value, dup);
25    println!("");
26
27    println!("=== Show elements in ascending order. ===");
28    loop {
29        match g.pop_min() {
30            Some(value) => println!("Min value = {}", value),
31            None => break,
32        }
33    }
34}
Source

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

Return and remove the maximum value.

If the maximum value is a duplicate, return and remove only one.

Source

pub fn pop_max_all(&mut self) -> Option<(T, usize)>

Return the maximum value and the number of duplication of it, then remove its node.

Examples found in repository?
examples/avl.rs (line 23)
3fn main() {
4    let v = vec![1, 8, 7, 3, 5, 6, 2, 9, 4, 0, 4, 9];
5    let mut g = AvlTree::new();
6    println!("=== Push values in v. ===");
7    for &i in v.iter() {
8        let (rank, dup) = g.push(i);
9        println!("value={}| rank={}, dup={}", i, rank, dup);
10    }
11    println!("Elements in the tree = {}", g.len());
12    println!("");
13
14    println!("Height of the tree = {}", g.height());
15    println!("How many 4?: {}", g.count(4));
16    println!("remove 4: {:?}", g.remove(4));
17    println!("4 is in?: {}", g.isin(4));
18    println!("remove 4: {:?}", g.remove(4));
19    println!("4 is in?: {}", g.isin(4));
20    println!("");
21
22    println!("Max value = {}", g.max().unwrap());
23    let (value, dup) = g.pop_max_all().unwrap();
24    println!("Pop all the max value: value={}, dup={}", value, dup);
25    println!("");
26
27    println!("=== Show elements in ascending order. ===");
28    loop {
29        match g.pop_min() {
30            Some(value) => println!("Min value = {}", value),
31            None => break,
32        }
33    }
34}
Source

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

Return the maximum value in the tree.

Source

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

Return and remove the maximum value.

If the maximum value is a duplicate, return and remove only one.

Examples found in repository?
examples/avl.rs (line 29)
3fn main() {
4    let v = vec![1, 8, 7, 3, 5, 6, 2, 9, 4, 0, 4, 9];
5    let mut g = AvlTree::new();
6    println!("=== Push values in v. ===");
7    for &i in v.iter() {
8        let (rank, dup) = g.push(i);
9        println!("value={}| rank={}, dup={}", i, rank, dup);
10    }
11    println!("Elements in the tree = {}", g.len());
12    println!("");
13
14    println!("Height of the tree = {}", g.height());
15    println!("How many 4?: {}", g.count(4));
16    println!("remove 4: {:?}", g.remove(4));
17    println!("4 is in?: {}", g.isin(4));
18    println!("remove 4: {:?}", g.remove(4));
19    println!("4 is in?: {}", g.isin(4));
20    println!("");
21
22    println!("Max value = {}", g.max().unwrap());
23    let (value, dup) = g.pop_max_all().unwrap();
24    println!("Pop all the max value: value={}, dup={}", value, dup);
25    println!("");
26
27    println!("=== Show elements in ascending order. ===");
28    loop {
29        match g.pop_min() {
30            Some(value) => println!("Min value = {}", value),
31            None => break,
32        }
33    }
34}
Source

pub fn pop_min_all(&mut self) -> Option<(T, usize)>

Return the maximum value and the number of duplication of it, then remove its node.

Source

pub fn len(&self) -> usize

Return the number of elements.

Examples found in repository?
examples/avl.rs (line 11)
3fn main() {
4    let v = vec![1, 8, 7, 3, 5, 6, 2, 9, 4, 0, 4, 9];
5    let mut g = AvlTree::new();
6    println!("=== Push values in v. ===");
7    for &i in v.iter() {
8        let (rank, dup) = g.push(i);
9        println!("value={}| rank={}, dup={}", i, rank, dup);
10    }
11    println!("Elements in the tree = {}", g.len());
12    println!("");
13
14    println!("Height of the tree = {}", g.height());
15    println!("How many 4?: {}", g.count(4));
16    println!("remove 4: {:?}", g.remove(4));
17    println!("4 is in?: {}", g.isin(4));
18    println!("remove 4: {:?}", g.remove(4));
19    println!("4 is in?: {}", g.isin(4));
20    println!("");
21
22    println!("Max value = {}", g.max().unwrap());
23    let (value, dup) = g.pop_max_all().unwrap();
24    println!("Pop all the max value: value={}, dup={}", value, dup);
25    println!("");
26
27    println!("=== Show elements in ascending order. ===");
28    loop {
29        match g.pop_min() {
30            Some(value) => println!("Min value = {}", value),
31            None => break,
32        }
33    }
34}
Source

pub fn height(&self) -> usize

Return the maximum height of the tree.

Examples found in repository?
examples/avl.rs (line 14)
3fn main() {
4    let v = vec![1, 8, 7, 3, 5, 6, 2, 9, 4, 0, 4, 9];
5    let mut g = AvlTree::new();
6    println!("=== Push values in v. ===");
7    for &i in v.iter() {
8        let (rank, dup) = g.push(i);
9        println!("value={}| rank={}, dup={}", i, rank, dup);
10    }
11    println!("Elements in the tree = {}", g.len());
12    println!("");
13
14    println!("Height of the tree = {}", g.height());
15    println!("How many 4?: {}", g.count(4));
16    println!("remove 4: {:?}", g.remove(4));
17    println!("4 is in?: {}", g.isin(4));
18    println!("remove 4: {:?}", g.remove(4));
19    println!("4 is in?: {}", g.isin(4));
20    println!("");
21
22    println!("Max value = {}", g.max().unwrap());
23    let (value, dup) = g.pop_max_all().unwrap();
24    println!("Pop all the max value: value={}, dup={}", value, dup);
25    println!("");
26
27    println!("=== Show elements in ascending order. ===");
28    loop {
29        match g.pop_min() {
30            Some(value) => println!("Min value = {}", value),
31            None => break,
32        }
33    }
34}

Auto Trait Implementations§

§

impl<T> Freeze for AvlTree<T>
where T: Freeze,

§

impl<T> RefUnwindSafe for AvlTree<T>
where T: RefUnwindSafe,

§

impl<T> Send for AvlTree<T>
where T: Send,

§

impl<T> Sync for AvlTree<T>
where T: Sync + Send,

§

impl<T> Unpin for AvlTree<T>
where T: Unpin,

§

impl<T> UnsafeUnpin for AvlTree<T>
where T: UnsafeUnpin,

§

impl<T> UnwindSafe for AvlTree<T>
where T: UnwindSafe,

Blanket Implementations§

Source§

impl<T> Any for T
where T: 'static + ?Sized,

Source§

fn type_id(&self) -> TypeId

Gets the TypeId of self. Read more
Source§

impl<T> Borrow<T> for T
where T: ?Sized,

Source§

fn borrow(&self) -> &T

Immutably borrows from an owned value. Read more
Source§

impl<T> BorrowMut<T> for T
where T: ?Sized,

Source§

fn borrow_mut(&mut self) -> &mut T

Mutably borrows from an owned value. Read more
Source§

impl<T> From<T> for T

Source§

fn from(t: T) -> T

Returns the argument unchanged.

Source§

impl<T, U> Into<U> for T
where U: From<T>,

Source§

fn into(self) -> U

Calls U::from(self).

That is, this conversion is whatever the implementation of From<T> for U chooses to do.

Source§

impl<T, U> TryFrom<U> for T
where U: Into<T>,

Source§

type Error = Infallible

The type returned in the event of a conversion error.
Source§

fn try_from(value: U) -> Result<T, <T as TryFrom<U>>::Error>

Performs the conversion.
Source§

impl<T, U> TryInto<U> for T
where U: TryFrom<T>,

Source§

type Error = <U as TryFrom<T>>::Error

The type returned in the event of a conversion error.
Source§

fn try_into(self) -> Result<U, <U as TryFrom<T>>::Error>

Performs the conversion.
Source§

impl<V, T> VZip<V> for T
where V: MultiLane<T>,

Source§

fn vzip(self) -> V