Expand description
Treap - probabilistic balanced BST.
Each node carries a random priority. The tree is a BST on keys and a
max-heap on priorities. Insert + delete rebalance via tree rotations.
With uniform priorities the expected height is O(log n).
Nodes are stored in a contiguous Vec<Node> and referenced by u32
indices (NULL = u32::MAX). This is the production-style memory
layout: avoids one heap allocation per insert (the Box::new(Node)
pattern), keeps nodes cache-dense, and lets the tree resize via
Vec::push amortised O(1) instead of fragmenting the global heap.
use subms_treap::Treap;
let mut t: Treap<u32, &'static str> = Treap::new(42);
t.insert(3, "three");
t.insert(1, "one");
t.insert(2, "two");
assert_eq!(t.get(&2).copied(), Some("two"));
assert_eq!(t.len(), 3);
assert_eq!(t.remove(&1), Some("one"));
assert_eq!(t.len(), 2);