Struct rudac::tree::AVL [−][src]
pub struct AVL<K: Ord, V> { /* fields omitted */ }
Expand description
An AVL tree is a self-balancing binary search tree. For lookup-intensive applications, AVL trees are faster than red–black trees because they are more strictly balanced
Examples
use rudac::tree::AVL;
// initialize an AVL tree with keys of type usize and values of type String
let mut avl_tree = AVL::<usize, String>::init();
// insert items into tree
avl_tree.insert(1, String::from("rudac"));
avl_tree.insert(2, String::from("is"));
avl_tree.insert(3, String::from("awesome"));
avl_tree.insert(4, String::from("!"));
// lookup for items
assert_eq!(*avl_tree.get(&1).unwrap(), String::from("rudac"));
assert_eq!(*avl_tree.get(&2).unwrap(), String::from("is"));
assert_eq!(*avl_tree.get(&3).unwrap(), String::from("awesome"));
assert_eq!(*avl_tree.get(&4).unwrap(), String::from("!"));
// delete items from tree
avl_tree.delete(&4);
assert_eq!(avl_tree.get(&4), None);
Implementations
Initializes an empty AVL tree
Examples
use rudac::tree::AVL;
let usize_to_string = AVL::<usize, String>::init();
let string_to_usize = AVL::<String, usize>::init();
let string_to_string = AVL::<String, String>::init();
Returns true
if tree is empty and false
otherwise
Examples
use rudac::tree::AVL;
let mut avl_tree = AVL::<usize,usize>::init();
assert_eq!(avl_tree.is_empty(), true);
avl_tree.insert(1,1);
assert_eq!(avl_tree.is_empty(), false);
avl_tree.delete(&1);
assert_eq!(avl_tree.is_empty(), true);
Returns total number of nodes in the tree
Examples
use rudac::tree::AVL;
let mut avl_tree = AVL::<usize,usize>::init();
assert_eq!(avl_tree.size(), 0);
avl_tree.insert(1,1);
avl_tree.insert(2,4);
avl_tree.insert(3,8);
assert_eq!(avl_tree.size(), 3);
Returns the height of the tree. An empty tree has height -1 and a tree with one node has height 0
Returns true
if tree contains the specified key
, false otherwise
Arguments
key
: key to be searched in the tree
Examples
use rudac::tree::AVL;
let mut avl_tree = AVL::<usize,usize>::init();
avl_tree.insert(1,10);
assert_eq!(avl_tree.contains(&1), true);
avl_tree.delete(&1);
assert_eq!(avl_tree.contains(&1), false);
Returns a reference to value associated with specified key
in tree, None
otherwise
Arguments
key
: key to be searched in the tree
Examples
use rudac::tree::AVL;
let mut avl_tree = AVL::<usize,usize>::init();
avl_tree.insert(1,10);
assert_eq!(*avl_tree.get(&1).unwrap(), 10);
avl_tree.delete(&1);
assert_eq!(avl_tree.get(&1), None);
Insert a node which contains the specified key
and value
into the tree.
if key
already exists, this method will replace value
as the new value of the node
Arguments
key
: key of the new nodevalue
: value associated with thekey
Examples
use rudac::tree::AVL;
let mut avl_tree = AVL::<usize,usize>::init();
avl_tree.insert(1,10);
avl_tree.insert(2,20);
avl_tree.insert(3,30);
avl_tree.insert(4,40);
assert_eq!(*avl_tree.get(&1).unwrap(), 10);
avl_tree.insert(1,11);
assert_eq!(*avl_tree.get(&1).unwrap(), 11);
Deletes the node containing the specified key
Arguments
key
: key of the node to be deleted from the tree
Examples
use rudac::tree::AVL;
let mut avl_tree = AVL::<usize,usize>::init();
avl_tree.insert(1,10);
avl_tree.insert(2,20);
avl_tree.insert(3,30);
avl_tree.insert(4,40);
avl_tree.delete(&1);
assert_eq!(avl_tree.get(&1), None);
Deletes node with smallest key from the tree
Examples
use rudac::tree::AVL;
let mut avl_tree = AVL::<usize,usize>::init();
avl_tree.insert(1,10);
avl_tree.insert(2,20);
avl_tree.insert(3,30);
avl_tree.insert(4,40);
avl_tree.delete_min();
assert_eq!(avl_tree.get(&1), None);
avl_tree.delete_min();
assert_eq!(avl_tree.get(&2), None);
Deletes node with largest key from the tree
Examples
use rudac::tree::AVL;
let mut avl_tree = AVL::<usize,usize>::init();
avl_tree.insert(1,10);
avl_tree.insert(2,20);
avl_tree.insert(3,30);
avl_tree.insert(4,40);
avl_tree.delete_max();
assert_eq!(avl_tree.get(&4), None);
avl_tree.delete_max();
assert_eq!(avl_tree.get(&3), None);
Returns the largest key in the tree less than or equal to key
Arguments
key
: key to be searched for
Examples:
use rudac::tree::AVL;
let mut avl_tree = AVL::<usize,usize>::init();
avl_tree.insert(1,10);
avl_tree.insert(3,20);
avl_tree.insert(5,30);
avl_tree.insert(7,40);
assert_eq!(*avl_tree.floor(&2).unwrap(), 1);
assert_eq!(avl_tree.floor(&0), None);
Returns the smallest key in the tree greater than or equal to key
Arguments
key
: key to be searched for
Examples:
use rudac::tree::AVL;
let mut avl_tree = AVL::<usize,usize>::init();
avl_tree.insert(1,10);
avl_tree.insert(3,20);
avl_tree.insert(5,30);
avl_tree.insert(7,40);
assert_eq!(*avl_tree.ceiling(&6).unwrap(), 7);
assert_eq!(avl_tree.ceiling(&8), None);
Returns the kth smallest key and its associated value in the tree
Arguments
k
: the order statistic
Panics
- panics if k is not in range: 0 <= k <= size - 1
Examples
use rudac::tree::AVL;
let mut avl_tree = AVL::<usize,usize>::init();
avl_tree.insert(1,10);
avl_tree.insert(3,20);
avl_tree.insert(5,30);
avl_tree.insert(7,40);
let (key, value) = avl_tree.select(1).unwrap();
assert_eq!(*key, 3);
assert_eq!(*value, 20);
Returns the smallest key and its associated value in the tree
Examples
use rudac::tree::AVL;
let mut avl_tree = AVL::<usize,usize>::init();
avl_tree.insert(1,10);
avl_tree.insert(3,20);
avl_tree.insert(5,30);
avl_tree.insert(7,40);
let (key, value) = avl_tree.min().unwrap();
assert_eq!(*key, 1);
assert_eq!(*value, 10);
avl_tree.delete_min();
let (key, value) = avl_tree.min().unwrap();
assert_eq!(*key, 3);
assert_eq!(*value, 20);
Returns the largest key and its associated value in the tree
Examples
use rudac::tree::AVL;
let mut avl_tree = AVL::<usize,usize>::init();
avl_tree.insert(1,10);
avl_tree.insert(3,20);
avl_tree.insert(5,30);
avl_tree.insert(7,40);
let (key, value) = avl_tree.max().unwrap();
assert_eq!(*key, 7);
assert_eq!(*value, 40);
avl_tree.delete_max();
let (key, value) = avl_tree.max().unwrap();
assert_eq!(*key, 5);
assert_eq!(*value, 30);
Returns all keys in the tree following an in-order traversal. Therefore keys are sorted from smallest to largest
Examples
use rudac::tree::AVL;
let mut avl_tree = AVL::<usize, usize>::init();
for i in (1..100).rev() {
avl_tree.insert(i, i);
}
let mut i = 1;
// keys are sorted: [1, 2, 3,..., 99]
for key in avl_tree.keys() {
assert!(*key == i);
i += 1;
}
Returns all keys in the tree following a level-order traversal
Returns all keys in the symbol table between low_key
(inclusive) and high_key
(exclusive)
Arguments
low_key
: lowest key of the rangehigh_key
: highest key of the range
Examples
use rudac::tree::AVL;
let mut avl_tree = AVL::<usize, usize>::init();
for i in (1..100).rev() {
avl_tree.insert(i, i);
}
let keys = avl_tree.keys_between(&1, &99);
assert_eq!(keys.len(), 98);
Returns the number of keys in the tree between low_key
(inclusive) and high_key
(exclusive)
Arguments
low_key
: lowest key of the rangehigh_key
: highest key of the range
Examples
use rudac::tree::AVL;
let mut avl_tree = AVL::<usize, usize>::init();
for i in (1..100).rev() {
avl_tree.insert(i, i);
}
let keys = avl_tree.size_between(&1, &99);
assert_eq!(keys, 98);