Module collections::bst

BST<K,V> (unbalanced binary search tree)

struct BST<int, int, Less<int>> t = std::BST::new();   // natural order
struct BST<Name, int, FnOrder<Name>> u = std::BST::new_with(std::FnOrder::of(cmp_name));
t.insert(50, 500);
match (t.get(50)) { case some(v): *v = 501; case null: ... }
t.foreach_inorder(print_pair);   // ascending key order
t.free();

C is a compile-time ordering, an Order (see std/cmp.h): every key comparison is a direct, inlinable call to C::cmp — no function pointer per compare. Keys and values are stored by value, one node per entry, drawn from the tree's own NodePool (see node_pool.h). Every operation is iterative — no recursion — so a degenerate (sorted-insert) tree costs O(n) time per lookup but never overflows a small bare-metal stack. get()/min_key()/max_key() hand out references into a node, valid until that entry is removed.

A BST owns its keys and values: it is a Drop type, and K/V may own something themselves (String, Vec, ...). insert() takes both by value (overwriting drops the old value and the duplicate key; an entry it can't store is dropped), remove() moves the value out and drops the key, and clear()/drop() drop every entry. Lookups take the key by value too and drop it.