search

kzhereb / kpi-acts-ta2020

Materials for "Algorithm theory" course
MIT License
0 stars 0 forks source link

DO5.3.What are the algorithms you need for working with trees? #2

Open AlyonaHaiova opened 4 years ago

AlyonaHaiova commented 4 years ago

Які алгоритми для роботи з деревами потрібні?

AlyonaHaiova commented 4 years ago

These answers were discussed during lectures: Рекурсивні

Бінарний пошук, лінійний пошук (для b tree). Алгорими повороту, балансування, обхід дерева

Пошук, вставка, видалення, пошук в ширину, пошук в глибину (дфс, бфс)

представлення дерева у впорядкованому масиві,

Найменьший спільний предок

AlyonaHaiova commented 4 years ago

Discussion from previous years: Вставка Видалення Пошук Балансування, перебалансування

Порівняння піддерев

Обхід Знаходження висоти Вставка, пошук Балансування Видалення

Визначення (найпершого) спільного предка

Обхід Пошук наступного і попереднього Мінімальне / максимальне значення Сортування Повороти під-дерева

glbter commented 4 years ago

Також можуть знадобитися алгоритми об'єднання дерев (тут можливі різні варіанти, як і просте під'єднання кореня одного дерева до іншого дерева, так і послідовне включення вершин в нове дерево,) Із попереднього може знадобитися також якийсь цікавий алгоритм поєднання двох нестандартних дерев. Наприклад, дерева, що використовуються для вирішення проблеми об'єднання елементів ( типу людей у соц мережах, або у житті і тд).

AlyonaHaiova commented 4 years ago

Доступ до конкретного елемента, Подання дерева у вигляді польського запису, Перевірка, чи є дерево BST

khilchuk-ol commented 4 years ago

Знаходження всіх листочків дерева; знаходження загальної кількості елементів дерева (хоча швидше буде зберігати це значення окремо).

glbter commented 4 years ago

Знаходження всіх листочків дерева; знаходження загальної кількості елементів дерева (хоча швидше буде зберігати це значення окремо).

Справді це краще зберігати окремо, оскільки це займає лише декілька бітів пам'яті, але оскільки більшісті випадках така задача не стоїть, і лише в декількох випадках таке може трапитися, для таких випадків гіпотетично можна передати у функцію обходу дерева певний лічильник на основі функціонального програмування (або по типу tree.stream().count())

LavorM commented 4 years ago

Алгоритм знаходження наступного по значенню ключа елемента дерева (Цей алгоритм часто використовується в алгоритмі видалення обєкту з дерева, але також може бути корисним і в інших випадках)