DOI 10.17586/0021-3454-2024-67-4-352-358
UDC 004.074
BALANCEABLE DATA STRUCTURE WITH ELEMENT PRIORITIES IN THE PROBLEM OF DISCRETE INFORMATION SOURCE MODELING
St. Petersburg State University of Aerospace Instrumentation, Department of Computing Systems and Networks; Senior Lecturer
Reference for citation: Aksenov А. V. Balanceable data structure with element priorities in the problem of discrete information source modeling. Journal of Instrument Engineering. 2024. Vol. 67, N 4. P. 352—358 (in Russian). DOI: 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.
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.
Keywords: data structure, accelerated access, binary search tree, self-balancing structure, efficient data storage, efficient data retrieval
References:
References:
- Adel'son-Vel'skii G.M., Landis E.M. Doklady Akademii Nauk SSSR, 1962, no. 2(146), pp. 263–266. (in Russ.)
- Cormen Th.H., Leiserson Ch.E., Rivest R.L., Stein C. Introduction to Algorithms, MIT Press, 2009.
- 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.
- Sleator D., Tarjan R.E. Journal of the Association for Computing Machinery, 1985, no. 3(32), pp. 652–686.
- Pfaff B. ACM SIGMETRICS Performance Evaluation Review, 2004, no. 1(32), pp. 410–411.
- 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.
- Seidel R., Aragon C.R. Algorithmica, 1996, vol. 16, рр. 464–497.
- Cleary J., Teahan W. Proceedings of the DCC '95 Data Compression Conference, 1995, р. 480.
- Boehm H., Atkinson R., Plass M. Software—Practice and Experience, 1995, no. 12(25), pp. 1315–1330.
- Hinze R., Paterson R. Journal of Functional Programming, 2006, no. 2(16), pp. 197–217. Data on author
