Comparative Performance Evaluation of Suboptimal Binary Search Trees - Štrbac-Savić, Svetlana; Tomašević, Milo; Minchev, Zlatogor; Maček, Nemanja (Journal of Computer and Forensic Sciences, 2023)
Three relevant types of suboptimal binary search trees are comparatively evaluated in this paper: two well-known representatives of height-balanced approaches (the AVL and red-black trees) and a popular self-adjusting splay tree. After a brief theoretical background, an evaluation method was described that employs a suitable synthetic workload method capable of producing diverse desired workload characteristics (different distributions and ranges of key values, varying input sequence lengths, etc.). Evaluation analysis was conducted for search, insert, and delete operations separately for each particular type and in appropriate combinations. Experimental results for an average operation cost as well as for tree maintenance cost are comparatively presented and carefully discussed. Finally, the suggested favorable conditions for application of each tree type are summarized.
Keywords: binary search trees; AVL trees; red-black trees; splay-trees; self-adjusting trees