3 ms·
That sounds like a pretty run-of-the-mill balanced binary tree? Rust has a BTreeMap: https://doc.rust-lang.org/std/collections/struct.BTreeMap.html https://doc.
by Munksgaard 4y ago
That sounds like a pretty run-of-the-mill balanced binary tree? Rust has a BTreeMap: https://doc.rust-lang.org/std/collections/struct.BTreeMap.html https://doc.rust-lang.org/std/collections/struct.BTreeMap.ht...
- vanviegen 4y agoInserting into an array increments the indexes of all subsequent values. How would a regular BTree emulate that behavior?
- AstralStorm 4y agoIt would rebalance on insert with O(log N) performance but chunky constant factor, keeping the ordering so access by index is also O(log N) with low constant factor... Which is why usually you would use a red-black tree rather than a BTree, as it has much lower constant for insertion and access by index. However higher for traversal in order.