Навіщо потрібне балансування дерев?

АлгоритмиJunior~2 хв читання

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

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

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

Для співбесіди

Premium

Коротка відповідь допоможе вам впевнено відповідати на цю тему під час співбесіди.

Навіщо потрібне балансування дерев?

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

Детально

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

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

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

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

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

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

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

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