Содержание
- 2. Задача Множина S, дії: вставляти та вилучати елементи; перевіряти належність елемента множині S; знаходити найменший (найбільший)
- 3. Дерева бінарного пошуку Дерево бінарного пошуку - бінарне дерево, кожний вузол якого v відмічений значенням l(v)
- 4. Дерево бінарного пошуку h c a d b g e f
- 5. Дерево бінарного пошуку Розглянемо основні дії з деревом бінарного пошуку: пошук вузла за ключовим значенням; вставка
- 6. Пошук у дереві бінарного пошуку Вхід: дерево Т и ключ K. Задача: якщо є вузол зі
- 7. Пошук у дереві бінарного пошуку //пошук у ДБП рекурсивний BINTRP find(BINTRP p, int key) { if
- 8. Пошук у дереві бінарного пошуку //пошук у ДБП нерекурсивний BINTRP fnd(BINTRP p, int key) { while
- 9. Пошук найменшого значення //пошук найменшого значення рекурсивний int fmin(BINTRP p) { if (p->lt) return (fmin(p->lt)); return
- 10. Пошук найменшого значення //пошук найменшого значення нерекурсивний int vmin(BINTRP p) { while (p->lt) p = p->lt;
- 11. Побудова дерева бінарного пошуку //за даними впорядкованого масиву BINTRP build(int a[], int n) { int m;
- 12. Побудова дерева бінарного пошуку //формування вузла бінарного дерева BINTRP nwnode(int v, BINTRP pl, BINTRP pr) {
- 13. Перевірка дерева бінарного пошуку //перевірка ДБП, vv зовнішня змінна з малим значенням bool test(BINTRP p) {
- 14. Вставка в дерево бінарного пошуку Вхід: дерево Т й значення v. Задача: додати вузол із значенням
- 15. Вставка в дерево бінарного пошуку //вставка нового вузла у ДБП BINTRP insert(BINTRP p, int v) {
- 16. Вилучення з дерева бінарного пошуку a) T0 v T1 T0 T1
- 17. Вилучення з дерева бінарного пошуку b) T0 v T1 T2 y T3 T0 y T1 T2
- 18. Вилучення з дерева бінарного пошуку Вхід: дерево Т й ключ v. Задача: вилучити з дерева Т
- 19. Вилучення з дерева бінарного пошуку //вилучення вузла з ДБП BINTRP ndel(BINTRP p, int v) { BINTRP
- 20. Вилучення з дерева бінарного пошуку //пошук вузла з максимальним значенням у ДБП й //вилучення, після пересилання
- 21. Складність основних дій з деревами бінарного пошуку Витрати пам`яті – O(n). Часова складність для всіх дій
- 22. Зауваження Не складно, за час O(n), побудувати ідеальне – повністю збалансоване дерево бінарного пошуку з висотою
- 23. Підсумки Дерева бінарного пошуку виступають у ролі досить привабливої структури даних для представлення різноманітної інформації, наприклад,
- 24. Поради Розібратися з розглянутими можливостями обробки інформації, представленої деревами бінарного пошуку. Не зловживати рекурсією. Самостійно реалізувати
- 25. Задачі Написати функції для визначення найбільшого значення у вузлах непорожнього дерева бінарного пошуку (рек., нерек.). Задана
- 26. Задачі Написати нерекурсивні функції для вставки та вилучення елементів. Записати у файл відмітки вузлів дерева бінарного
- 27. Задачі Розв`язати попередню задачу, але разом з ідентифікатором друкувати у зростаючому порядку номери всіх рядків тексту
- 29. Скачать презентацию