Запропонувати правку

Покращити цю статтю

Допрацюйте відповідь до «Навіщо потрібне балансування дерев?». Ваші зміни проходять модерацію перед публікацією.

Потрібне підтвердження

Контент

Що ви змінюєте

Заголовок (UA)

Коротка відповідь (UA)

Показується над повною відповіддю для швидкого нагадування.

Відповідь (UA)

## Коротка відповідь

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

## Детально

### Що таке балансування

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

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

- Гарантії асимптотики: пошук/вставка/видалення працюють за O(log n) замість O(n) у гіршому випадку для незбалансованих дерев.
- Передбачувана латентність: глибина викликів і кількість переходів по покажчиках обмежені, що важливо для SLA і real-time сценаріїв.
- Краще використання кешу: менше переходів по покажчиках і менш глибокі шляхи часто означають менше кеш-промахів (особливо актуально для B-дерев та їхніх варіантів).
- Зниження ризику переповнення стека при рекурсивних обходах, бо глибина дерева обмежена логарифмом від розміру.
- Ефективні діапазонні запити і операції порядку (k-й елемент, попередник/наступник): на відміну від хеш-таблиць, впорядковані дерева зберігають порядок ключів.

### Приклади збалансованих структур

- AVL-дерева: жорстко контролюють різницю висот піддерев (−1, 0, +1), мінімізуючи висоту. Дуже швидкий пошук.
- Червоно-чорні дерева: більш «м'яке» балансування, але дешеві вставки/видалення. Часто використовуються в стандартних бібліотеках.
- B-/B+-дерева: оптимізовані під диски/сторінки пам'яті; величезна розгалуженість -> дуже мала висота.
- Treap, Splay, Weight-balanced: імовірнісні або амортизовані гарантії, спрощують реалізацію або покращують середній випадок.

### Ціна балансування

- Додаткові операції обертань і оновлення метаданих (висоти/кольору) при вставці/видаленні. Амортизовано залишається O(log n), але з більшими константами.
- Складність реалізації і супроводу вища, ніж у простого BST.
- Невеликі накладні витрати пам'яті (дод. поля: висота, колір, пріоритет тощо).

### Коли можна не балансувати

- Малий обсяг даних, де навіть O(n) достатньо швидко, а важливіша простота коду.
- Пакетні вставки з подальшим одноразовим балансуванням/побудовою ідеально збалансованого дерева (наприклад, із відсортованого масиву).
- Якщо порядок не потрібен, а важлива лише амортизована швидкість точкових операцій - частіше обирають хеш-таблиці.

### Приклад: вставка в AVL-дерево з ребалансуванням

```
class Node {
  constructor(key) {
    this.key = key;
    this.left = null;
    this.right = null;
    this.h = 1; // висота вузла
  }
}

const h = (n) => (n ? n.h : 0);
const update = (n) => (n.h = Math.max(h(n.left), h(n.right)) + 1);
const bf = (n) => h(n.left) - h(n.right); // баланс-фактор

function rotateRight(y) {
  const x = y.left;
  const T2 = x.right;
  x.right = y;
  y.left = T2;
  update(y);
  update(x);
  return x;
}

function rotateLeft(x) {
  const y = x.right;
  const T2 = y.left;
  y.left = x;
  x.right = T2;
  update(x);
  update(y);
  return y;
}

function rebalance(n) {
  update(n);
  const balance = bf(n);

if (balance > 1) {
    if (bf(n.left) < 0) {
      n.left = rotateLeft(n.left); // випадок LR
    }
    return rotateRight(n); // випадок LL
  }
  if (balance < -1) {
    if (bf(n.right) > 0) {
      n.right = rotateRight(n.right); // випадок RL
    }
    return rotateLeft(n); // випадок RR
  }
  return n; // вже збалансовано
}

function insert(node, key) {
  if (!node) return new Node(key);
  if (key < node.key) node.left = insert(node.left, key);
  else if (key > node.key) node.right = insert(node.right, key);
  else return node; // дублікати ігноруємо

return rebalance(node);
}

// Приклад використання
let root = null;
[1, 2, 3, 4, 5, 6, 7].forEach((k) => (root = insert(root, k)));
// Висота залишається O(log n) завдяки ребалансуванню
```

Вставка проходить за O(log n), а ребалансування потребує O(1) обертань на кожен підйом рекурсії (у сумі - O(log n)).

### Ілюстрація ефекту висоти

- Незбалансований BST при вставці відсортованих ключів: h ≈ n -> пошук O(n).
- AVL: h ≤ ~1.44·log2(n). Для n = 1 000 000: log2(n) ≈ 19.9, висота ≈ 28-29.
- Червоно-чорне дерево: h ≤ 2·log2(n + 1). Для n = 1 000 000: висота ≤ ~40.
- B-дерево з великою валентністю (наприклад, порядку 100): для 1 000 000 ключів висота зазвичай 3-4 рівні.

Markdown · перетягуйте зображення · ⌘B / ⌘I шорткати643 слів

Для рев’юера

Примітка для модератора (необов’язково)

Бачить лише модератор. Прискорює рев’ю.