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

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

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

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

Контент

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

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

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

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

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

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

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

## Розгорнута відповідь

### Що таке BST і навіщо воно потрібне

BST організує динамічний набір порівнюваних ключів так, щоб швидко виконувати операції пошуку, вставки, видалення та отримувати елементи у відсортованому порядку без додаткового сортування. Застосовується для реалізацій множин і словників з упорядкуванням, діапазонних запитів, пошуку найближчих значень, попередника/наступника тощо.

### Інваріанти BST

- Для кожної вершини: усі ключі в лівому піддереві < ключ вершини, усі ключі в правому піддереві > ключ вершини.
- Інваріант рекурсивний: він виконується для кожної вершини дерева.
- Політика дублікатів - на вибір: заборона, лічильник частоти, зберігання колекції або направлення рівних ключів в один із боків (у прикладі - праворуч).

### Складність операцій

- Пошук/вставка/видалення: середнє O(log n), найгірше O(n) за виродження (якщо дерево стає «ланцюжком»).
- Обхід (in-order, pre-order, post-order): O(n).
- Пам'ять: O(n). Висота h впливає на операції: чим менша h, тим швидше.
- Збалансовані варіанти (AVL, червоно-чорні дерева тощо) гарантують O(log n) у найгіршому випадку.

### Основні операції

1. Пошук: починаємо з кореня і йдемо ліворуч або праворуч залежно від порівняння ключа з ключем поточної вершини, поки не знайдемо або не впремося в порожнечу.
2. Вставка: шукаємо місце, як при пошуку, і вставляємо новий вузол у знайдену порожню позицію, зберігаючи інваріант.
3. Видалення: три випадки щодо вузла, який видаляється.
  - Лист: просто видаляємо.
  - Один нащадок: підтягуємо нащадка на місце вузла.
  - Два нащадки: замінюємо ключ (і значення) вузла на ключ його in-order наступника (мінімум у правому піддереві) і видаляємо наступника з правого піддерева.
4. Обходи: симетричний (in-order) повертає відсортовану послідовність ключів.
  - Pre-order (корінь, ліве, праве) - серіалізація структури.
  - In-order (ліве, корінь, праве) - відсортований вивід.
  - Post-order (ліве, праве, корінь) - видалення/звільнення.

### Приклад коду (JavaScript)

Політика дублікатів: рівні ключі направляємо праворуч. Можна передати свою функцію порівняння.

```
class Node {
  constructor(key, value = null) {
    this.key = key;
    this.value = value;
    this.left = null;
    this.right = null;
  }
}

class BST {
  constructor(compareFn) {
    this.root = null;
    this.compare = compareFn || ((a, b) => (a < b ? -1 : a > b ? 1 : 0));
  }

contains(key) {
    let cur = this.root;
    while (cur) {
      const c = this.compare(key, cur.key);
      if (c === 0) return true;
      cur = c < 0 ? cur.left : cur.right;
    }
    return false;
  }

search(key) {
    let cur = this.root;
    while (cur) {
      const c = this.compare(key, cur.key);
      if (c === 0) return cur.value ?? cur.key;
      cur = c < 0 ? cur.left : cur.right;
    }
    return undefined;
  }

insert(key, value = null) {
    const node = new Node(key, value);
    if (!this.root) {
      this.root = node;
      return this;
    }
    let cur = this.root;
    while (true) {
      const c = this.compare(key, cur.key);
      if (c < 0) {
        if (!cur.left) { cur.left = node; break; }
        cur = cur.left;
      } else { // c >= 0 - дублікати направляємо праворуч
        if (!cur.right) { cur.right = node; break; }
        cur = cur.right;
      }
    }
    return this;
  }

min(node = this.root) {
    if (!node) return undefined;
    while (node.left) node = node.left;
    return node.key;
  }

max(node = this.root) {
    if (!node) return undefined;
    while (node.right) node = node.right;
    return node.key;
  }

remove(key) {
    this.root = this.#removeNode(this.root, key);
    return this;
  }

#removeNode(node, key) {
    if (!node) return null;
    const c = this.compare(key, node.key);
    if (c < 0) {
      node.left = this.#removeNode(node.left, key);
      return node;
    } else if (c > 0) {
      node.right = this.#removeNode(node.right, key);
      return node;
    } else {
      // Випадок 1: лист
      if (!node.left && !node.right) return null;
      // Випадок 2: один нащадок
      if (!node.left) return node.right;
      if (!node.right) return node.left;
      // Випадок 3: два нащадки - беремо наступника (мінімум у правому піддереві)
      let succ = node.right;
      while (succ.left) succ = succ.left;
      node.key = succ.key;
      node.value = succ.value;
      node.right = this.#removeNode(node.right, succ.key);
      return node;
    }
  }

traverseInOrder(cb, node = this.root) {
    if (!node) return;
    this.traverseInOrder(cb, node.left);
    cb(node);
    this.traverseInOrder(cb, node.right);
  }

traversePreOrder(cb, node = this.root) {
    if (!node) return;
    cb(node);
    this.traversePreOrder(cb, node.left);
    this.traversePreOrder(cb, node.right);
  }

traversePostOrder(cb, node = this.root) {
    if (!node) return;
    this.traversePostOrder(cb, node.left);
    this.traversePostOrder(cb, node.right);
    cb(node);
  }

height(node = this.root) {
    if (!node) return -1; // висота порожнього дерева
    return 1 + Math.max(this.height(node.left), this.height(node.right));
  }
}
```

### Приклади використання

```
const bst = new BST();
[8, 3, 10, 1, 6, 14, 4, 7, 13].forEach(k => bst.insert(k));

console.log('contains 7?', bst.contains(7)); // true
console.log('min/max:', bst.min(), bst.max()); // 1 14

const sorted = [];
bst.traverseInOrder(n => sorted.push(n.key));
console.log('sorted:', sorted.join(', ')); // 1, 3, 4, 6, 7, 8, 10, 13, 14

bst.remove(3);
const after = [];
bst.traverseInOrder(n => after.push(n.key));
console.log('after delete 3:', after.join(', '));

console.log('height:', bst.height());

// Діапазонний запит [4, 10]
const range = [];
bst.traverseInOrder(n => {
  if (n.key >= 4 && n.key <= 10) range.push(n.key);
});
console.log('range [4..10]:', range.join(', '));
```

### Коли BST - хороший вибір

- Потрібен упорядкований набір із частими вставками/видаленнями та швидким пошуком.
- Діапазонні запити (усі ключі між L і R), пошук попередника/наступника.
- Потрібно отримувати елементи у відсортованому порядку «на льоту» (in-order обхід).

### Підводні камені та поради

- Вироджування в найгіршому випадку: обирайте випадкові вставки або використовуйте самобалансувальні дерева для гарантій O(log n).
- Визначте і дотримуйтесь політики дублікатів (заборона, лічильник, направлення праворуч/ліворуч).
- Функція порівняння має задавати строгий слабкий порядок (транзитивність, антирефлексивність) - інакше дерево зламається.
- Рекурсивні реалізації простіші, але можуть впертися в ліміт стека на дуже глибоких деревах; за потреби використовуйте ітеративні версії.

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

Для рев’юера

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

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