Crate subms_treap 

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);

// Ordered navigation, no feature flag needed.
assert_eq!(t.first().map(|(k, _)| *k), Some(2));
assert_eq!(t.ceiling(&3).map(|(k, _)| *k), Some(3));
assert_eq!(t.predecessor(&3).map(|(k, _)| *k), Some(2));
assert_eq!(t.iter().map(|(k, _)| *k).collect::<Vec<_>>(), vec![2, 3]);

Full writeup, design notes and measured benchmarks: https://www.submillisecond.com/cookbook/recipes/subms-treap

Re-exports

pub use features::concurrent_reads::TreapSnapshot;

pub use features::merge_split::SplittableTreap;

pub use features::persistent::PersistentTreap;

Modules

features

Opt-in treap feature catalog. Each submodule is gated by its own Cargo feature flag and adds a focused capability without bloating the base treap build.

recipe

SubMsRecipe impl.

Structs

Iter

Ascending in-order iterator. See Treap::iter.

IterRev

Descending in-order iterator. See Treap::iter_rev.

RangeIter

Treap

Enums

RangeBound

One end of a range query.

TreapError

The one fallible operation’s error.