Балансируемая структура данных с приоритетами элементов в задаче моделирования дискретных источников информации
https://doi.org/10.17586/0021-3454-2024-67-4-352-358
Аннотация
Рассматриваются особенности разработки балансируемой структуры данных, ориентированной на ускоренный доступ к элементам, имеющим высокий приоритет. Подобные структуры могут использоваться в задачах моделирования дискретных источников информации. Предложено самобалансирующееся двоичное дерево поиска, оптимизированное для эффективного хранения и поиска данных на основе приоритетов, коррелирующих с вероятностью порождения символов. Решение позволяет преодолеть ограничения существующих структур данных с учетом требований к памяти и производительности в контексте специфических задач обработки информации.
Об авторе
А. В. Аксенов
Санкт-Петербургский государственный университет аэрокосмического приборостроения
Россия
Россия
Алексей Владимирович Аксенов — старший преподаватель, кафедра вычислительных систем и сетей
Санкт-Петербург
Список литературы
1. Адельсон-Вельский Г. М., Ландис Е. М. Один алгоритм организации информации // Докл. АН СССР. 1962. Т. 146, № 2. С. 263—266.
2. Кормен Т. Х., Лейзерсон Ч. Е., Ривест Р. Л., Штайн К. Алгоритмы: построение и анализ. М.: Вильямс, 2013. 1328 с.
3. Guibas L. J., Sedgewick R. A dichromatic framework for balanced trees // Proc. of the 19th Annual Symp. on Foundations of Computer Science (SFCS 1978). Ann Arbor, MI, USA. 1978. Р. 8—21.
4. Sleator D., Tarjan R. E. Self-Adjusting Binary Search Trees // J. of the Association for Computing Machinery. 1985. Vol. 32, N 3. Р. 652—686.
5. Pfaff B. Performance Analysis of BSTs in System Software // ACM SIGMETRICS Performance Evaluation Review. 2004. Vol. 32, is. 1. Р. 410—411.
6. Galperin I., Rivest R. Scapegoat trees // 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. Randomized search trees // Algorithmica. 1996. Vol. 16. P. 464—497.
8. Cleary J., Teahan W. Experiments on the zero frequency problem // Proc. of the DCC '95 Data Compression Conf. 1995. Р. 480.
9. Boehm H., Atkinson R., Plass M. Ropes: an Alternative to Strings // Software—Practice and Experience. 1995. Vol. 25, N 12. Р. 1315—1330.
10. Hinze R., Paterson R. Finger Trees: A Simple General-purpose Data Structure // J. of Functional Programming. 2006. Vol. 16, N 2. Р. 197—217.
Рецензия
Для цитирования:
Аксенов А.В. Балансируемая структура данных с приоритетами элементов в задаче моделирования дискретных источников информации. Известия высших учебных заведений. Приборостроение. 2024;67(4):352-358. https://doi.org/10.17586/0021-3454-2024-67-4-352-358
For citation:
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
Просмотров:
21
Послать статью по эл. почте 