11 Бінарні дерева пошуку
•
0 likes•11,173 views
Слайди лекції з курсу "Розробка та аналіз алгоритмів. Частина 1". Тема лекції: "Бінарні дерева пошуку". http://edx.prometheus.org.ua/courses/KPI/Algorithms101/2015_Spring/about
11 Бінарні дерева пошуку
- 1. Розробка та аналіз алгоритмів 11. Бінарні дерева пошуку • Мотивація. Означення • Обхід дерева. Пошук елементів • Додавання/видалення елементів (с) Олексій Молчановський, Prometheus.org.ua 1
- 2. Динамічні структури (с) Олексій Молчановський, Prometheus.org.ua 2
- 3. Означення бінарного дерева пошуку (с) Олексій Молчановський, Prometheus.org.ua 3
- 4. Збалансоване бінарне дерево пошуку (с) Олексій Молчановський, Prometheus.org.ua 4
- 5. Пошук елементу в дереві (с) Олексій Молчановський, Prometheus.org.ua 5
- 6. Пошук елементу в дереві (с) Олексій Молчановський, Prometheus.org.ua 6
- 7. Пошук мінімального/максимального елементів (с) Олексій Молчановський, Prometheus.org.ua 7
- 8. Обхід дерева у відсортованому порядку (с) Олексій Молчановський, Prometheus.org.ua 8
- 9. Обхід дерева у відсортованому порядку (с) Олексій Молчановський, Prometheus.org.ua 9
- 10. Пошук попереднього/наступного елементів (с) Олексій Молчановський, Prometheus.org.ua 10
- 11. Додавання елементу (с) Олексій Молчановський, Prometheus.org.ua 11
- 12. Видалення елементу. Варіант 1 (с) Олексій Молчановський, Prometheus.org.ua 12
- 13. Видалення елементу. Варіант 2 (с) Олексій Молчановський, Prometheus.org.ua 13
- 14. Видалення елементу. Варіант 3 (с) Олексій Молчановський, Prometheus.org.ua 14
- 15. Бінарні дерева пошуку. Післямова • Використовуються у різних мовах програмування для реалізаціях багатьох вбудованих структур даних, які потребують активного видалення, додавання та пошуку елементів • Важко підтримувати збалансованість дерева після кількох операцій додавання/видалення • Існує кілька модифікацій бінарних дерев пошуку, які зберігають збалансованість дерев: AVL-дерева, червоно-чорні дерева (с) Олексій Молчановський, Prometheus.org.ua 15