Ссылка для цитирования : Аксенов А. В. Балансируемая структура данных с приоритетами элементов в задаче моделирования дискретных источников информации // Изв. вузов. Приборостроение. 2024. Т. 67, № 4. С. 352—358. DOI: 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.