Cited By
View all- Štrbac-Savić STomašević MMaček NMinchev Z(2022)Comparative performance evaluation of suboptimal binary search treesJournal of Computer and Forensic Sciences10.5937/1-427091:1(29-45)Online publication date: 2022
Comparative performance evaluation of the AVL and red-black trees
Pages 14 - 19
Abstract
The AVL and red-black trees are the suboptimal variants of the binary search trees which can achieve the logarithmic performance of the search operation withot an excessive cost of the optimal balancing. After presenting a brief theoretical background, the paper comparatively evaluates the performance of these two structures. The evaluation was performed by means of simulation with a synthetic workload model. In order to obtain a better insight, the performance indicators are chosen to be implementation and platform independent. Some representative results of the evalution are given and discussed. Finally, the findings of this study are summarized into the suggestions for an optimal use of the analyzed trees.
References
[1]
Tomašević M. 2011. Algorithms and Data Structures, Academic mind, Belgrade (in Serbian).
[2]
Adelson--Velski G. M. and Landis E. M. 1962. An Algorithm for the Organization of Informations", Soviet Mathematics Doklady. 3: 1259--1263.
[3]
Živković M. 2000., Algorithms, Matematički fakultet, Beograd. (in Serbian).
[4]
Cormen T., Leiseron Ch., Rivest R. 1990. Introduction to Algorithms, The MIT Press, McGrawHill.
[5]
Flaming B. 1993. Practical Data Structures in C++, John Wiley and Sons.
[6]
Knuth D. 1997., The Art of Computer Programing, Vol. 3, Third Edition, Addison -- Wesley.
[7]
Urošević D. 1996. Algorithms in C programming language, Mikro knjiga. (in Serbian).
[8]
Aho A., Hopcroft J., Ullman J. 1983., Data Structures and Algorithms, Addison-Wesley.
[9]
Bayer R. 1971. Binary B-Trees for Virtual Memory, Proceedings of 1971 ACM-SIGFIDET Workshop on Data Description, Access and Control, San Diego, California, November 11--12.
[10]
Karlton P. L., Fuller S. H., Scrogas R. E. and Kaehler E. B. 1976. Performance of heigh-balanced trees, Communications of the ACM, vol 19, no1, pp23--28.
[11]
Bear J. L. and Schwab B. 1977. A Comparation of Tree-balancing Algorithms, Comunications of the AC, 20(5):pp. 322--330.
[12]
Writght W. E. 1980. An Empirical Evaluation of Algorithms for Dynamically Maintaining Binary Search Trees, Proceedings of the ACM 1980 annual conference, pp. 505--515.
[13]
Nievergelt J. and Reingold E. M. 1973. Binary Search Trees of Bounded Balance, SIAM Journal Computing 2, pp 33--43.
[14]
Bell J. and Gupta G. 1993. An Evaluation of Self-Adjusting Binary Search Tree Technics, Software -Practice and Experience, v23. pp. 369--8.
[15]
Bitner J. R. 1979. Heuristics That Dynamically Organize Data Structures, SIAM J. Computing, 8, pp 82--110.
[16]
Allen B. and Munro I. 1978., Self-organising Binary Search Trees, JACM, 25, pp 526--535.
[17]
Sleator D. D. and Trajan R. E. 1985, Self--adjusting Binary Search Trees, Journal of the Association for Computing Machinery, Vol. 32, No. 3, July 1985, pp. 652--686.
[18]
Štrbac-Savić S., Tomašević M. 2012. Analiza tehnika za reorganizaciju samopodešavajućih stabala, In Proceedings of the Infoteh. 2012. (March 21--23. 2012.) Jahorina
[19]
Pfaff B. 2004. Performance Analysis of BSTs in System Software, ACM SIGMETRICS, pp410--411.
[20]
Neyer M. P. 2009A Comparison of Dictionary Implementations. http://www.cs.unc.edu/~plaisted/comp750/Neyer%20paper.pdf
Index Terms
- Comparative performance evaluation of the AVL and red-black trees
Recommendations
Rank-Balanced Trees
Since the invention of AVL trees in 1962, many kinds of binary search trees have been proposed. Notable are red-black trees, in which bottom-up rebalancing after an insertion or deletion takes O(1) amortized time and O(1) rotations worst-case. But the ...
A comparison of tree-balancing algorithms
Several algorithms — height-balance (i.e. AVL and extensions), weight-balance (i.e. BB and WB), and total restructuring — for building balanced binary search trees are compared. The criteria for comparison encompass theoretical aspects (e.g. path ...
Teaching Self-Balancing Trees Using a Beauty Contest
ITiCSE '19: Proceedings of the 2019 ACM Conference on Innovation and Technology in Computer Science EducationTrees data structures and their performance is one of the main topics to teach in a data structures course. Appreciating the importance of tree structure and tree height in software performance is an important concept to teach. In this paper, a simple ...
Reviews
Simon Berkovich
Balancing binary trees provides efficient searching with overall O(log n) performance for retrieval and maintenance operations. The first data structure of this kind was proposed by Adelson-Velskii and Landis 50 years ago, and is now known as the AVL tree. Since then, balanced binary trees have been suggested based on growth-by-splitting, as in dynamic files for B-trees and extendible hashing. Popular red-black (RB) trees actually implement two-element B-trees, while binary labeling of the tree nodes is just for convenience. Both types of trees, AVL and RB, show similar O(log n) behavior. According to this paper, the general performance for both is basically the same. Differences depend on the statistical variations in the distribution of keys and the mixture of operations. The distinction lies in programming complexity. For example, a lecture on the AVL details takes about an hour, while explaining the RB takes less than ten minutes. Online Computing Reviews Service
Access critical reviews of Computing literature here
Become a reviewer for Computing Reviews.
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
September 2012
312 pages
Copyright © 2012 ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]
Sponsors
- MSTD: Ministry of Education, Science and Technological Development - Serbia
- Novi Sad: Faculty of Technical Sciences, University of Novi Sad
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 16 September 2012
Check for updates
Author Tags
Qualifiers
- Research-article
Conference
BCI '12
Sponsor:
- MSTD
- Novi Sad
Acceptance Rates
Overall Acceptance Rate 97 of 250 submissions, 39%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations1Total Citations
- 573Total Downloads
- Downloads (Last 12 months)45
- Downloads (Last 6 weeks)2
Reflects downloads up to 12 Nov 2024
Other Metrics
Citations
Cited By
View all- Štrbac-Savić STomašević MMaček NMinchev Z(2022)Comparative performance evaluation of suboptimal binary search treesJournal of Computer and Forensic Sciences10.5937/1-427091:1(29-45)Online publication date: 2022
View Options
Get Access
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in