Стратегія балансування

📌 Про що ця тема

Стратегія балансування — це підхід у проєктуванні алгоритмів і структур даних, коли дані свідомо розподіляють рівномірно, щоб жодна «гілка» чи частина не ставала надто великою. Мета — утримати складність операцій на рівні O(log n) замість O(n). Ключове поняття: збалансована структура (найчастіше збалансоване дерево) та рівномірний поділ у методі «розділяй і володарюй».

📖 Головне

• Збалансованість означає, що висоти частин структури відрізняються мало (в ідеалі — не більше ніж на 1). Для дерева з n вузлів збалансована висота ≈ log₂n.

• У незбалансованому дереві елементи можуть вишикуватись у «ланцюжок» — тоді пошук деградує до O(n), як у списку.

• У збалансованому дереві пошук, вставка й видалення виконуються за O(log n), бо на кожному кроці відкидається половина елементів.

• Балансування буває структурне (перебудова дерева при вставці/видаленні) і алгоритмічне (рівний поділ задачі на підзадачі).

• Приклади збалансованих структур: АВЛ-дерева, червоно-чорні дерева. Вони автоматично відновлюють баланс поворотами вузлів.

• У «розділяй і володарюй» баланс = ділити задачу на рівні половини. Саме тому сортування злиттям дає O(n·log n), а не O(n²).

• Балансування навантаження (load balancing) — рівномірний розподіл роботи між процесорами/серверами, щоб скоротити загальний час.

• Головний принцип: рівномірний поділ → логарифмічна глибина → швидкі операції.

🔢 Як це працює на прикладі

Приклад 1. Вставляємо числа 1,2,3,4,5 у звичайне дерево пошуку по порядку. Кожне більше за попереднє → дерево витягнеться в лінію глибиною 5. Пошук числа 5 вимагає 5 кроків — це O(n).

Якщо дерево балансувати, коренем стане 3, зліва 1–2, справа 4–5. Глибина ≈ 2, пошук будь-якого елемента — максимум 3 кроки, тобто ≈ log₂5.

Приклад 2. Масив із 8 елементів сортуємо злиттям. Ділимо навпіл: 8 → 4+4 → 2+2+2+2 → по 1. Кількість рівнів поділу = log₂8 = 3, на кожному рівні обробляємо всі n елементів → загалом n·log n = 8·3 = 24 операції. Нерівний поділ (7+1) зруйнував би цю оцінку.

⚠️ Типові помилки

• Плутають «відсортоване дерево» зі «збалансованим»: дерево може бути коректним за правилами пошуку, але повністю розбалансованим.

• Вважають, що будь-яке бінарне дерево дає O(log n). Логарифм гарантує лише баланс — інакше O(n).

• Думають, що балансування безкоштовне: повороти й перебудова теж витрачають час, але окупаються швидшим пошуком.

• Забувають, що в «розділяй і володарюй» важлива саме рівність частин, а не сам факт поділу.

• Змішують балансування структур даних і балансування навантаження — це різні застосування однієї ідеї.

🎯 Що завчити напамʼять

• Збалансоване дерево: висота ≈ log₂n, операції O(log n).

• Незбалансоване («лінія»): O(n).

• Сортування злиттям / розділяй-і-володарюй при рівному поділі: O(n·log n).

• Принцип: рівномірний поділ зменшує глибину з n до log n.

🧠 Перевір себе

1) Яка складність пошуку у збалансованому дереві з n вузлів?

2) Чому вставка впорядкованих чисел у просте дерево пошуку небезпечна?

3) Як пов'язаний рівний поділ із складністю O(n·log n)?

4) Чим балансування навантаження відрізняється від балансування дерева?

Відповіді: 1 — O(log n); 2 — дерево вироджується в ланцюжок, пошук стає O(n); 3 — рівний поділ дає log n рівнів, на кожному обробляється n елементів; 4 — перше розподіляє роботу між виконавцями, друге — дані в межах однієї структури, але ідея рівномірності спільна.