Похожие презентации:
Дерева бінарного пошуку
1. Дерева бінарного пошуку
24.02.2020Всякая вещь есть форма проявления
беспредельного разнообразия.
Козьма Прутков
2. Задача
Множина S, дії:вставляти та вилучати елементи;
перевіряти належність елемента множині S;
знаходити найменший (найбільший) елемент S.
Вважаємо, що S є підмножиною лінійно
впорядкованої великої універсальної множини.
Способи представлення множини S ?
Переваги та недоліки розглянутих раніше
способів?
3. Дерева бінарного пошуку
Дерево бінарного пошуку - бінарне дерево,кожний вузол якого v відмічений значенням l(v)
так що:
l(u) < l(v) для кожного вузла u з лівого
піддерева вузла v;
l(u) > l(v) для кожного вузла u з правого
піддерева вузла v.
Властивість: відмітки вузлів бінарного
дерева, що взяті в симетричному порядку
утворюють впорядковану послідовність.
4. Дерево бінарного пошуку
hc
a
d
b
g
e
<a, b, c, d, e, f, g, h>
f
5. Дерево бінарного пошуку
Розглянемо основні дії з деревом бінарногопошуку:
пошук вузла за ключовим значенням;
вставка вузла у дерево бінарного пошуку;
вилучення вузла з дерева бінарного пошуку;
пошук найменшого значення;
побудова дерева бінарного пошуку (повністю
збалансованого) за множиною значень;
перевірка дерева, чи є воно деревом бінарного
пошуку.
Pr_1
6. Пошук у дереві бінарного пошуку
Вхід: дерево Т и ключ K.Задача: якщо є вузол зі значенням K в дереві Т, то
повернути покажчик на цей вузол.
Алгоритм:
Для порожнього дерева повернути покажчик NULL
Інакше порівняти K зі значенням кореня X:
Якщо K=X, видати покажчик на цей вузол.
Якщо K>X, шукати ключ K в правому піддереві Т.
Якщо K<X, шукати ключ K в лівому піддереві Т.
7. Пошук у дереві бінарного пошуку
//пошук у ДБП рекурсивнийBINTRP find(BINTRP p, int key) {
if (p && p->dat != key)
return(p->dat>key ? find(p->lt, key) :
find(p->rt, key));
return p;
}
8. Пошук у дереві бінарного пошуку
//пошук у ДБП нерекурсивнийBINTRP fnd(BINTRP p, int key) {
while (p) {
if (p->dat > key) p = p->lt;
else if (p->dat < key) p = p->rt;
else break;
}
return p;
}
9. Пошук найменшого значення
//пошук найменшого значення рекурсивнийint fmin(BINTRP p) {
if (p->lt) return (fmin(p->lt));
return (p->dat);
}
10. Пошук найменшого значення
//пошук найменшого значення нерекурсивнийint vmin(BINTRP p) {
while (p->lt) p = p->lt;
return (p->dat);
}
11. Побудова дерева бінарного пошуку
//за даними впорядкованого масивуBINTRP build(int a[], int n) {
int m;
if (n) {
m = n/2;
return(nwnode(a[m], build(&a[0], m),
build(&a[m+1], n-m-1)));
} return NULL;
}
12. Побудова дерева бінарного пошуку
//формування вузла бінарного дереваBINTRP nwnode(int v, BINTRP pl, BINTRP pr) {
BINTRP p = new BINTRN;
p->dat = v; p->lt = pl; p->rt = pr;
return p;
}
13. Перевірка дерева бінарного пошуку
//перевірка ДБП, vv зовнішня змінна з малим значеннямbool test(BINTRP p) {
if (!p) return 1;
if (!test(p->lt)) return 0;
if (p->dat < vv) return 0;
vv = p->dat;
return (test(p->rt));
}
14. Вставка в дерево бінарного пошуку
Вхід: дерево Т й значення v.Задача: додати вузол із значенням v в дерево Т
(якщо такий вузол відсутній).
Алгоритм:
Якщо дерево порожньо, замінити його на дерево з
одним кореневим вузлом (v, NULL, NULL).
Інакше порівняти v із значенням вузла x.
Якщо v<x, рекурсивно додати v в ліве піддерево Т.
Якщо v>x, рекурсивно додати v в праве піддерево Т.
15. Вставка в дерево бінарного пошуку
//вставка нового вузла у ДБПBINTRP insert(BINTRP p, int v) {
if (!p) return (nwnode(v, NULL, NULL));
if (p->dat > v) p->lt = insert(p->lt, v);
else if (p->dat <v) p->rt = insert(p->rt, v);
return p;
}
16. Вилучення з дерева бінарного пошуку
a)T0
T0
v
T1
T1
17. Вилучення з дерева бінарного пошуку
b)T0
T0
y
v
T2
T1
T2
T1
y
T3
???
T3
18. Вилучення з дерева бінарного пошуку
Вхід: дерево Т й ключ v.Задача: вилучити з дерева Т вузол із значенням v.
Алгоритм:
Якщо дерево T порожнє, зупинитись;
Інакше порівняти v з значенням x кореневого вузла.
Якщо v>x, рекурсивно вилучити v з правого піддерева Т;
Якщо v<x, рекурсивно вилучити v з лівого піддерева Т;
Якщо v=x, то необхідно розглянути два випадки.
Якщо вузол має не більше одного сина його вилучаємо;
Якщо вузол має двох синів, то
Знайдемо вузол із значенням y, що йому безпосередньо
передує у симетричному обході, здійснюємо заміну v←y й
вилучаємо вузол зі значенням y.
19. Вилучення з дерева бінарного пошуку
//вилучення вузла з ДБПBINTRP ndel(BINTRP p, int v) {
BINTRP q;
if (p)
{if (p->dat > v) p->lt = ndel(p->lt, v);
else if (p->dat < v) p->rt = ndel(p->rt, v);
else if (p->lt) p->lt = delmax(p->lt, p);
else {q = p; p = p->rt; delete q;}
} return p;
}
20. Вилучення з дерева бінарного пошуку
//пошук вузла з максимальним значенням у ДБП й//вилучення, після пересилання його значення у вузол t
BINTRP delmax(BINTRP p, BINTRP t) {
BINTRP q;
if (p->rt) p->rt = delmax(p->rt, t);
else {t->dat = p->dat; q = p; p = p->lt; delete q;}
return p;
}
21. Складність основних дій з деревами бінарного пошуку
Витрати пам`яті – O(n).Часова складність для всіх дій - O(h):
“в середньому” - O(log n);
“в найгіршому” - O(n) (h може дорівнювати n).
Де n – кількість вершин, а h – висота дерева.
22. Зауваження
Не складно, за час O(n), побудувати ідеальне –повністю збалансоване дерево бінарного пошуку
з висотою O(log n), що представляє впорядковану
сукупність даних.
Але дії з деревом: додавання та вилучення
можуть
порушувати
“збалансованість”,
поступово перетворюючи його на дерево з
висотою O(n). При цьому структура стає схожою
на список й втрачає основні свої привабливі
риси.
23. Підсумки
Дерева бінарного пошуку виступають у ролідосить привабливої структури даних для
представлення
різноманітної
інформації,
наприклад, таблиць з ключовими полями (за
якими
здійснюється
впорядкування)
й
підтримують ефективне виконання основних
операцій: пошуку, додавання, вилучення.
Часова складність основних дій з деревами
бінарного пошуку визначається висотою дерева.
24. Поради
Розібратисяз розглянутими можливостями
обробки інформації, представленої деревами
бінарного пошуку.
Не зловживати рекурсією.
Самостійно реалізувати інші дії з інформацією,
що представлена деревами бінарного пошуку.
25. Задачі
Написати функції для визначення найбільшогозначення у вузлах непорожнього дерева
бінарного пошуку (рек., нерек.).
Задана послідовність цілих чисел a1, a2, …, an .
Написати програму модифікації дерева бінарного
пошуку B, спочатку порожнього, за умовами:
– якщо ai>0 , то додати ai в B;
– якщо ai<0 , то вилучити -ai з B (при відсутності
видається повідомлення);
– якщо ai=0 , то закінчити виконання програми.
26. Задачі
Написати нерекурсивні функції для вставки тавилучення елементів.
Записати у файл відмітки вузлів дерева
бінарного пошуку у порядку їх зростання.
У текстовому файлі PROG – “Сі-програма”, з
ідентифікаторами довжиною не більше 9.
Надрукувати в алфавітному порядку всі
ідентифікатори, вказавши кількість входжень
(великі й маленькі літери розрізняються).
27. Задачі
Розв`язати попередню задачу, але разом зідентифікатором друкувати у зростаючому
порядку номери всіх рядків тексту програми, де
він зустрічається.
Розв`язати попередні задачі, якщо максимальна
довжина ідентифікаторів заздалегідь не відома.
Написати функцію для розбиття дерева
двійкового пошуку на два зі значеннями у
деревах відповідно <K та ≥K.
28. Задачі
Написатифункцію для об`єднання двох
множин представлених деревами двійкового
пошуку. Результатом є дерево двійкового
пошуку.
Написати функцію для об`єднання двох дерев
двійкового пошуку зі значеннями у деревах
відповідно <K та ≥K.
Як на вашу думку можна виправляти
“незбалансованість” дерев двійкового пошуку?