Parallel Binary Search Tree Construction Inspired by Thread-Level Speculation
Hiroaki Hirata, Atsushi Nunome · 2022
Binary search trees (BSTs) are one of the most important data structures in computer science. A parallel construction algorithm of a BST can be easily derived from the sequential algorithm. Since the structure of the generated BST is different depending on the order of inserted nodes, however, such a parallel algorithm cannot generate a BST with the same structure (node position) as a BST generated by the sequential algorithm. So this paper presents a new parallel algorithm to construct a BST having the same structure as a BST the sequential algorithm constructs. This algorithm was derived based on the concept of thread-level speculation but is a purely (non-speculatively) parallel one. Our experiments showed that for the large enough size of BSTs, the program implementing our new algorithm could construct a BST with a single structure by only 9% performance loss than the program that constructs BST having different structures every time of execution.