Can binary tree search be paralleled using rayon？

[jianshu93]

I am wondering whether the search and inserting step could be paralleled for huge tree.

Thanks，

Jianshu

[starovoid]

Parallel searching is definitely possible, since the max(), min() and contains() methods do not mutate the tree.
But I don't see any opportunities for correct parallel insertion. Even if rayan allows this to be implemented, it will definitely not be possible to avoid serious overhead and/or algorithmic tricks, including adding new functions specifically for parallel insertion. In theory, it is possible to insert several elements in parallel, but for this you need to be sure that their positions are in different subtrees.

[jianshu93]

Thanks for quick response. Yes since insert is fast compare to search. I think it would be interesting to have a parallel search.binary tree search is the key step for nearest neighbor search based on k dimension tree et.al. like the Annoy by Spotify.

Thanks，

Jianshu