Expand description
A safe, arena-backed (indexed) AVL tree
§About
Adelson-Velsky and Landis (AVL) trees represent theoretically optimal balanced binary search trees. AVL trees guarantee ~1.44 * log(n) height, and provide O(log(n)) search, insert, and delete operations. Red-black trees tend to be more popular even though they only guarantee <= 2 * log(n) height. The imperfect height is offset by the fact that red-black trees often require fewer rotations, and the average number of rebalance operations is fewer than with AVL trees.
§Design
The design uses a flat, Vec-backed structure with iterative (read non-recursive) navigation. This arena-allocated design provides robust, performant operations while keeping runtime checks to a minimum. The goal of this approach is to avoid unnecessary overhead with recursive operations and extra heap allocations, making it suitable for low-spec environments.
The structure trades spatial efficiency for O(1) insert operations. All “pointers” represent absolute positions (as indexes) and cannot be re-calculated in less than O(n) time. Thus, remove(key) operations do not actually shrink the physical size of the structure, leaving a None “hole” in the removed node’s place. The structure can only grow.
Due to common usage when implementing sorted map and set structures, this implementation does not accept duplicate entries by default. The structure contains an internal SearchResult enum that allows for duplicates by way of Ordering::Equal, but it is yet implemented in this version.
§Example
use dsa_rust::hierarchies::avl_tree::AVLTree;
let mut tree: AVLTree<u8> = AVLTree::new();
// Create the following AVL tree
//
// 39
// / \
// 17 41
// / \ \
// 13 23 43
// / / \
// 8 19 31
//
let v = [31, 13, 23, 39, 41, 43, 8, 17, 19];
for e in v.iter() {
tree.insert(*e);
}
assert_eq!(tree.get_root(), Some(&39)); // Prove that its properly rooted
// Remove 41 which results in the following restructure
//
// 17
// / \
// 13 39
// / / \
// 8 23 43
// / \
// 19 31
//
assert!(tree.contains(&41)); // Prove that its here today
let removed = tree.remove(&41).unwrap();
assert_eq!(removed, 41);
assert!(!tree.contains(&41)); // ...and gone tomorrow
tree.insert(34);
tree.insert(67);
tree.insert(2);
tree.insert(4);
tree.insert(5);
tree.insert(1);
// The tree is still intact, and its root has shifted
assert_eq!(tree.get_root().unwrap(), &31);
// In-order "snapshot" iterator
let mut sorted = Vec::new();
for e in tree.iter() {
sorted.push(*e)
}
assert_eq!(sorted, [1, 2, 4, 5, 8, 13, 17, 19, 23, 31, 34, 39, 43, 67]);