Parallel Algorithms For Balancing Tlireaded Binary Scarcl1 'hem
Enamul Haq, Si-Qing Zheng · 1989
Parallel algorithms for balancing any threaded binary search tree of 2-' - 1 < N 5 2 - 1 nodes are developed. Shared memory model is used for the proposed algorithms. The number of processors used in the algorithms is reduced from (2 - 1) to the number of nodes in the tree. The developed parallel algorithms have constant time complexity and require O(N) addi%ional space.