Balanceable Data Structure with Element Priorities in the Problem of Discrete Information Source Modeling
https://doi.org/10.17586/0021-3454-2024-67-4-352-358
Abstract
The features of developing a balanceable data structure focused on accelerated access to elements with high priority are considered. Similar structures can be used in problems of modeling discrete information sources. A self-balancing binary search tree is proposed, optimized for efficient storage and retrieval of data based on priorities that correlate with the probability of symbol generation. The solution overcomes the limitations of existing data structures, taking into account memory and performance requirements in the context of specific information processing tasks.
About the Author
А. V. Aksenov
St. Petersburg State University of Aerospace Instrumentation
Russian Federation
Russian Federation
Aleksey V. Aksenov — Senior Lecturer, Department of Computing Systems and Networks
St. Petersburg
References
1. Adel'son-Vel'skii G.M., Landis E.M. Doklady Akademii Nauk SSSR, 1962, no. 2(146), pp. 263–266. (in Russ.)
2. Cormen Th.H., Leiserson Ch.E., Rivest R.L., Stein C. Introduction to Algorithms, MIT Press, 2009.
3. Guibas L.J., Sedgewick R. Proceedings of the 19th Annual Symposium on Foundations of Computer Science (SFCS 1978), Ann Arbor, MI, USA, 1978, рр. 8–21.
4. Sleator D., Tarjan R.E. Journal of the Association for Computing Machinery, 1985, no. 3(32), pp. 652–686.
5. Pfaff B. ACM SIGMETRICS Performance Evaluation Review, 2004, no. 1(32), pp. 410–411.
6. Galperin I., Rivest R. Proc. of the Fourth Annual ACM-SIAM Symp. on Discrete algorithms (SODA '93), Society for Industrial and Applied Mathematics, USA, 1993, рр. 165–174.
7. Seidel R., Aragon C.R. Algorithmica, 1996, vol. 16, рр. 464–497.
8. Cleary J., Teahan W. Proceedings of the DCC '95 Data Compression Conference, 1995, р. 480.
9. Boehm H., Atkinson R., Plass M. Software—Practice and Experience, 1995, no. 12(25), pp. 1315–1330.
10. Hinze R., Paterson R. Journal of Functional Programming, 2006, no. 2(16), pp. 197–217.
Review
For citations:
Aksenov А.V. Balanceable Data Structure with Element Priorities in the Problem of Discrete Information Source Modeling. Journal of Instrument Engineering. 2024;67(4):352-358. (In Russ.) https://doi.org/10.17586/0021-3454-2024-67-4-352-358
Views:
22
Email this article 