How to get the lower bound and upper bound of an e

Question

Reading the BTreeSet documentation, I can't seem to figure out how to get the least value greater than, or greatest value less than an element from a BTreeSet in logarithmic time.

I see there is a range method that can give the values in an arbitrary (min, max) range, but what if I don't know the range and I just want the previous and/or the next element in logarithmic time?

This would be similar to lower_bound and upper_bound in std::set in C++.

Answer 1

but what if I don't know the range

Then use an unbounded range:

use std::collections::BTreeSet;

fn neighbors(tree: &BTreeSet<i32>, val: i32) -> (Option<&i32>, Option<&i32>) {
    use std::ops::Bound::*;

    let mut before = tree.range((Unbounded, Excluded(val)));
    let mut after = tree.range((Excluded(val), Unbounded));

    (before.next_back(), after.next())
}

fn main() {
    let tree: BTreeSet<_> = [1, 3, 5].iter().cloned().collect();

    let (prev, next) = neighbors(&tree, 2);

    println!("greatest less than 2: {:?}", prev);
    println!("least bigger than 2:  {:?}", next);
}

greatest less than 2: Some(1)
least bigger than 2:  Some(3)

BTreeSet::range returns a double-ended iterator, so you can pull from either side of it.

Note that we are using the very explicit Bound operator so that we do not include the value we are looking around.

---

There have been discussions about enhancing BTreeMap / BTreeSet to have a "cursor" API that might allow you to find an element and then "move around" inside the tree. This would allow you to avoid searching through the tree to find the start node twice, but it has not been implemented.

A pull request was opened to do so, but it was closed because it was deemed that there should be more discussion about how such an API should look and work.

Answer 2

Well... if you don't mind modifying the current collection and taking a performance hit... it appears that you can use split_off creatively.

let mut tree = BTreeSet::new();
tree.insert(1);
tree.insert(3);
tree.insert(5);

let other = tree.split_off(&2);

println!("{:?}", tree);
println!("{:?}", other);

Will print {1} and {3, 5}:

• the lower-bound is the first element of the second range,
• the upper-bound is the first element of the second range if not equal, and the second otherwise.

Once you are done, you can reassemble the tree using tree.append(other).

---

And yes, it's really less than ideal...

Answer 3

If you can change your data structure, you can use intrusive collections.

You have the desired methods:

• RBTree::lower_bound
• RBTree::upper_bound