Що таке балансування дерева?

Балансування дерева - це процес, під час якого структура дерева перебудовується так, щоб його висота залишалася мінімальною, а елементи були розподілені рівномірно.

#Навіщо це потрібно

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

#Мета балансування

Зробити так, щоб для кожного вузла різниця висот лівого і правого піддерева була невеликою (зазвичай ≤ 1). Тоді дерево залишається «щільним», і пошук знову працює швидко.

#Приклад

Незбалансоване дерево (усе вправо):

Після балансування:

#Типи збалансованих дерев

• AVL-дерево - суворе рівноважіння за висотою (різниця ≤ 1).
• Червоно-чорне дерево - гнучкіше рівноважіння за правилами розфарбовування вузлів.
• B-дерево, B+ дерево - балансування для зберігання даних на дисках (наприклад, у базах даних).

#Підсумок

Балансування дерева - це підтримання такої форми дерева, за якої операції пошуку, вставки та видалення виконуються максимально швидко (≈ O(log n)), незалежно від порядку додавання елементів.