Does a thread-safe Binary Search Tree exist?

Hi all,

Is there any existing open-source implementation of a thread-safe Binary Search Tree (BST) in Rust?

I've found a few helpful single-threaded examples [1] [2], but no multi-threaded.

My current approach is based off of The Complete Rust Programming Reference Guide's single-threaded red-black tree with Arcs instead of their Rcs, but I haven't had much success. This is for benchmarking a research project, so I'd love to just drop in an existing implementation instead of having to write my own.

A quick search with the keywords concurrent and tree showed this crate.
There were some other crates too, so it might be worth a look.

Thank you for sharing! This implementation is a bit more complicated than I was looking for -- it would be great for educational purposes to have a super minimal example. I searched around and couldn't find a really simple one.

I got my implementation working -- take a look here if you're curious!

Looks good so far :slight_smile:
One thing to consider is to replace the recursive functions with loops.
This would be especially important as your implementation does not balance the tree and thus with some bad luck the stack might overflow. Nice bonus would be, that non recursive implementations topically tend to be faster.

1 Like