Содержание
- Введение
- 1. Теоретические основы бинарных деревьев поиска
- 1.1. Структура и свойство упорядоченности бинарного дерева поиска
- 1.2. Высота дерева и сложность основных операций
- 2. Алгоритмы балансировки бинарных деревьев поиска
- 2.1. Балансировка AVL-дерева и контроль высоты поддеревьев
- 2.2. Повороты и изменение структуры дерева при обновлении
- 3. Анализ алгоритмических свойств и методов балансировки
- 3.1. Гарантии высоты и оценка сложности операций
- 3.2. Сравнительные критерии для поиска, вставки и удаления
- 4. Применение деревьев поиска и подходы к их реализации
- 4.1. Поисковые деревья для упорядоченного хранения данных
- 4.2. Представление и реализация динамических структур данных
- 5. Экспериментальная оценка реализаций и рекомендации по выбору
- 5.1. Методика проверки реализаций на последовательностях операций
- 5.2. Показатели эффективности и представление результатов
- Заключение
- Список литературы
Введение
Бинарные деревья поиска позволяют хранить ключи в упорядоченной структуре и выполнять поиск, вставку и удаление с учётом связей между узлами. Эффективность этих операций зависит от высоты дерева: если оно становится вытянутым, путь от корня к искомому элементу может увеличиваться. Балансировка ограничивает такой рост и тем самым поддерживает предсказуемые характеристики операций. Поэтому изучение методов балансировки важно не только для понимания алгоритмов, но и для выбора подходящей структуры данных при решении прикладных задач.
Список литературы
- Сартаева, Г. К. Об оптимизации процедур поиска на основе поисковых деревьев / Г. К. Сартаева, И. А. Бессмертный // Инновации в науке. — 2016. — № 3-1 (52). — URL: https://cyberleninka.ru/article/n/ob-optimizatsii-protsedur-poiska-na-osnove-poiskovyh-dereviev.
- Окасаки, К. Чисто функциональные структуры данных / К. Окасаки. — [Б. м.] : [б. и.], 2022. — 254 с. — ISBN 9785041965686.
- ЭУМК "Программирование". Структуры данных / П. А. Мандрик, Е. В. Пазюра, А. П. Побегайло [и др.]. — 2008. — URL: http://elib.bsu.by/handle/123456789/8003.
- Аксенов, А. В. Разработка электронного учебника по динамическим структурам данных в языке c++ / А. В. Аксенов // Актуальные проблемы авиации и космонавтики. — 2019. — Т. 3. — URL: https://cyberleninka.ru/article/n/razrabotka-elektronnogo-uchebnika-po-dinamicheskim-strukturam-dannyh-v-yazyke-c.
- Горяинов, С. И. Перестройка бинарных деревьев в алгоритме Хаффмана / С. И. Горяинов // Программные системы и вычислительные методы. — 2014. — Т. 4, № 4. — С. 464–471. — DOI: 10.7256/2305-6061.2014.4.13755.
