How to traverse a binary tree in a thread safe way?

Question

I need a way to traverse a binary tree, using multiple threads and store elements that matches a criteria into a list. How do I do that, in a thread safe way?

Answer 1

You miss a few points that would help with an answer.

If the multiple threads are all read-only in their traversal, and the tree does not change for the duration of their traversal, and they all are putting those found matches into lists that those traversal threads own, then you should have no worries at all.

As you relax any of those constraints, you will need to either add in locking, or other appropriate means of making sure they play nicely together.

Answer 2

The easiest way would be to lock the entry points of the binary tree class, and assume it's locked on the recursive traversal functions (for insertion, lookup, deletion).

If you have many readers and fewer writers, you can use ReaderLocks and WriterLocks to allow concurrent lookups, but completely lock on mutations.

If you want something finer grained, it will get much more complicated. You'll have to define what you really need from "thread safety", you might have to pare down your binary tree API, and you'll probably need to lock nodes individually, possibly for the duration of a sub-tree traversal.

Answer 3

As SDG points out the answer depends a lot on the exact nature of your problem. If you want to decompose the traversal (i.e. traverse in parallel) then you can have threads acting on different sub-trees after say level 2. Each thread can then append to its own list, which can then be merged/concatenated at a join point. The simplest thing to do is to prevent mods to the tree while doing a traversal.

I just have to add that you don't keep firing off threads after you reach your level. You only do it once. So at level 2 you fire of a maximum of 4 threads. Each traveral thread treats it's subtree as its own rooted tree. You also don't do this unless you have a buttload of nodes, and a reasonably balanced tree. Buttload is a technical term meaning "measure". The part of the traversal up to the splitting point is traversed by the UI thread. If this was my problem I would think long and hard about what it was I needed to achieve, as it may make all the difference.

Let me add one more thing (is this becoming a Monty Python sketch?). You don't really need to concat or merge the result lists into a new list if all you need is to process the results. Even if you need the results ordered then it is still better to sort each list seperately (perhaps in parallel) and then "merging" them in a GetNextItem pull fashion. That way you don't need som much additional memory. You can merge 4 lists at once in this fashion by having two "buffers" (can be pointers /indices to the actual entries). I'm trying to find a way to explain it without drawing a pic.

                     0 1 2 3 4 5 6 7 8 9   

             L1(0):  4 4 4 5 5 6 8 
    B1[L2,3]        \  
             L2[1]:  3 4 5 5 6 7 7 8 9
 \   
             L3[1]:  2 2 4 4 5 5 6 8 
    B2[L3,2]          /
             L4[0]:  2 4 5 5 6 7 7 8 9

You keep pulling from whichever list satisfies the order you need. If you pull from B2, then you only need to update B2 and its sublists (in this case we pulled 2 from L3 and moved the L3's index to the next entry).