Comparative Performance Evaluation of Suboptimal Binary Search Trees

  • Svetlana Štrbac-Savić Academy of Technical and Art Applied Studies, School of Electrical and Computer Engineering, Belgrade
  • Milo Tomašević School of Electrical Engineering, University of Belgrade
  • Zlatogor Minchev Joint Training Simulation and Analysis Center, Institute of ICT, Institute of Mathematics and Informatics, Bulgarian Academy of Sciences
  • Nemanja Maček Academy of Technical and Art Applied Studies, School of Electrical and Computer Engineering, Belgrade, Serbia & University Business Academy in Novi Sad, Serbia & SECIT Security Consulting, Serbia
DOI: https://doi.org/10.5937/1-42709
Keywords: binary search trees, AVL trees, red-black trees, splay-trees, self-adjusting trees

Abstract


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.

 

Author Biographies

Svetlana Štrbac-Savić, Academy of Technical and Art Applied Studies, School of Electrical and Computer Engineering, Belgrade

 

 

Milo Tomašević, School of Electrical Engineering, University of Belgrade

 

 

Zlatogor Minchev, Joint Training Simulation and Analysis Center, Institute of ICT, Institute of Mathematics and Informatics, Bulgarian Academy of Sciences

 

 

Nemanja Maček, Academy of Technical and Art Applied Studies, School of Electrical and Computer Engineering, Belgrade, Serbia & University Business Academy in Novi Sad, Serbia & SECIT Security Consulting, Serbia

 

 

References

[1] S. Štrbac-Savić and M. Tomašević, “Comparative performance evaluation of the AVL and red-black trees,” In Proceedings of the Fifth Balkan Conference in Informatics, September (BCI ’12), 2012, pp. 14–19.


[2] G. M. Adelson-Velskii and E. M. Landis, “An Algorithm for the Organization of Information,” Soviet Mathematics Doklady, vol. 3, pp. 1259–1263, 1962.


[3] M. Tomašević, Algorithms and Data Structures. Belgrade, Serbia: Academic Mind, (in Serbian), 2011.


[4] D.Е. Knuth, Тhe Art of Computer Programming, Volume 3: Sorting and Searching, Reading, Massachusetts: Addison-Wesley, 1998.


[5] T. Cormen, Ch. Leiserson, and R. Rivest, Introduction to Algorithms. The MIT Press, McGraw-Hill, 2009.


[6] A. Aho, J. Hopcroft, and J. Ullman, Data Structures and Algorithms. Addison-Wesley, 1983.


[7] B. Flaming, Practical Data Structures in C++. New York: John Wiley and Sons, 1993.


[8] C. Okasaki, “Red-black trees in a functional setting,” Journal of Functional Programming, Vol. 9, No. 4, pp. 471–477, 1999.


[9] D. Sleator and R. E. Trajan, “Self-Adjusting Binary Search Trees,” Journal of the Association for Computing Machinery, Vol. 32, No. 3, pp. 652–686, 1985.


[10] M. A. Weiss, Data Structures and Algorithm Analysis in C. Reading, MA: Addison- Wesley, 1997.


[11] R. Cole, “On the Dynamic Finger Conjecture for Splay Trees, Part II: The Proof,” SIAM Journal on Computing, Vol. 30, pp. 44–85, 2000.


[12] J. Bell and G. Gupta, “An Evaluation of Self-Adjusting Binary Search Tree Techniques,” Software – Practice and Experience, Vol. 23, pp. 369–382, 1993.


[13] B. Allen and I. Munro, “Self-Organising Binary Search Trees,” JACM, Vol. 25, pp. 526–535, 1978.


[14] B. Pfaff, “Performance Analysis of BSTs in System Software,” ACM SIGMETRICS, Vol. 32, Issue 1, pp. 410–411, 2004.


[15] R. Wiener, “AVL Trees,” In Generic Data Structures and Algorithms in Go, Berkeley, CA: Apress, 2022, pp. 315–347.


[16] H. Canli and S. Toklu, “AVL Based Settlement Algorithm and Reservation System for Smart Parking Systems in IoT-based Smart Cities,” The International Arab Journal of Information Technology, Vol. 19, No. 5, pp. 793–801, 2022.


[17] R. Wiener, “Red-Black Trees,” In Generic Data Structures and Algorithms in Go, Berkeley, CA: Apress, 2022, pp. 363–385.


[18] B. A. Berendsohn and L. Kozma, “Splay trees on trees,” In Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2022, pp. 1875–1900.


[19] T. Luo, “Learning Augmented Binary Search Trees,” Doctoral thesis, Carnegie Mellon University, Pittsburgh, PA, 2022.


 

Published
2023/02/07
Issue
Vol. 1 No. 1 (2022): Journal of Computer and Forensic Sciences
Section
Članci

I (we), the author(s), hereby declare under full moral, financial and criminal liability that the manuscript submitted for publication to the Journal of Computer and Forensic Sciences

a) is the result of my (our) own original research and that I (we) hold the right to publish it;

b) does not infringe any copyright or other third-party proprietary rights;

c) complies with the Journal’s research and publishing ethics standards;

d) has not been published elsewhere, under this or any other title;

e) is not under consideration by another publication, under this or any other title.

I (we) also declare under full moral, financial and criminal liability:

f) that all conflicts of interest that may directly or potentially influence or impart bias on the work have been disclosed in the manuscript;

g) that if the article has been accepted for publishing I (we) will transfer all copyright ownership of the manuscript to the University of Criminal Investigation and Police Studies in Belgrade.

Signed by the Corresponding Author on behalf of the all other authors.