International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
|
Volume 33 - Issue 10 |
Published: November 2011 |
Authors: Vinod Prasad |
![]() |
Vinod Prasad . A Forest of Hashed Binary Search Trees with Reduced Internal Path Length and better Compatibility with the Concurrent Environment. International Journal of Computer Applications. 33, 10 (November 2011), 17-21. DOI=10.5120/4056-5830
@article{ 10.5120/4056-5830, author = { Vinod Prasad }, title = { A Forest of Hashed Binary Search Trees with Reduced Internal Path Length and better Compatibility with the Concurrent Environment }, journal = { International Journal of Computer Applications }, year = { 2011 }, volume = { 33 }, number = { 10 }, pages = { 17-21 }, doi = { 10.5120/4056-5830 }, publisher = { Foundation of Computer Science (FCS), NY, USA } }
%0 Journal Article %D 2011 %A Vinod Prasad %T A Forest of Hashed Binary Search Trees with Reduced Internal Path Length and better Compatibility with the Concurrent Environment%T %J International Journal of Computer Applications %V 33 %N 10 %P 17-21 %R 10.5120/4056-5830 %I Foundation of Computer Science (FCS), NY, USA
We propose to maintain a Binary Search Tree in the form of a forest in such a way that – (a) it provides faster node access and, (b) it becomes more compatible with the concurrent environment. Using a small array, the stated goals were achieved without applying any restructuring algorithm. Empirically, we have shown that the proposed method brings down the total internal path-length of a Binary Search Tree quite considerably. The experiments were conducted by creating two different data structures using the same input - a conventional binary search tree, and a forest of hashed trees. Our empirical results suggest that the forest so produced has lesser internal path length and height in comparison to the conventional tree. A binary search tree is not a well-suited data structure for concurrent processing. The evidence also shows that maintaining a large tree in form of multiple smaller trees (forest) increases the degree of parallelism.