Бінарне дерево пошуку (BST)

Повне пояснення

Коротке пояснення

Бінарне дерево пошуку (BST) зберігає елементи так, що для будь‑якого вузла всі значення у лівому піддереві менші, а в правому — більші. Це дозволяє швидко вставляти нові елементи і знаходити потрібне значення, порівнюючи його з вузлом за один крок.

Аналогія

Уявіть бібліотеку, де книги розташовані по алфавіту: щоб знайти книгу «Книга», треба спочатку перевірити, чи вона в лівому підрозділі (менша), правому (більша) або саме в поточному розділі.

Коли застосовувати

• Пошук, вставка або видалення елементів у колекції з унікальними ключами.
• Дані, що поступово додаються і не потребують частих перестроювань.
• Коли потрібна швидка (логарифмічна) доступність, а не повний порядок.
• При створенні індексів у базах даних або в реалізації словників.
• Якщо можна прийняти ризик, що дерево може стати незбалансованим.

Кроки алгоритму

1. Починаємо з кореня дерева.
2. Якщо шукане значення менше поточного вузла, переходимо до лівого піддерева.
3. Якщо більше — переходимо до правого піддерева.
4. Повторюємо кроки 2–3, доки не знайдемо вузол з потрібним значенням або досягнемо листа.
5. Якщо елемент не знайдено, повертаємо «не існує».

Візуальна інтуїція (текстова)

          8
        /   \
       3     10
      / \      \
     1   6      14
        / \    /
       4   7  13

Пошук числа 7: 8 → 3 (меньше) → 6 (більше) → 7 (знайдено).

Складність

• Час: у найкращому випадку O(log n), коли дерево збалансоване; у гіршому — O(n) при повному розтягуванні.
• Пам’ять: O(n), бо кожен елемент зберігається у вузлі.

Код (js)

// Клас для вузла BST
class TreeNode {
  constructor(value) { // створюємо новий вузол з заданим значенням
    this.value = value; // значення вузла
    this.left = null;   // ліве піддерево
    this.right = null;  // праве піддерево
  }
}

// Клас BST з методами вставки та пошуку
class BinarySearchTree {
  constructor() { // ініціалізуємо порожнє дерево
    this.root = null;
  }

  // Вставка нового значення у дерево
  insert(value) {
    const newNode = new TreeNode(value);
    if (this.root === null) { // якщо дерево порожнє, новий вузол стає коренем
      this.root = newNode;
      return;
    }
    let current = this.root; // починаємо з кореня
    while (true) {
      if (value < current.value) { // шукаємо місце у лівому піддереві
        if (current.left === null) {
          current.left = newNode; // вставляємо
          return;
        }
        current = current.left; // переходимо ліворуч
      } else if (value > current.value) { // шукаємо у правому піддереві
        if (current.right === null) {
          current.right = newNode;
          return;
        }
        current = current.right; // переходимо праворуч
      } else {
        return; // значення вже існує, не вставляємо дублікати
      }
    }
  }

  // Пошук значення у дереві, повертає вузол або null
  search(value) {
    let current = this.root; // починаємо з кореня
    while (current !== null) {
      if (value === current.value) return current; // знайдено
      if (value < current.value) current = current.left; // ліворуч
      else current = current.right; // праворуч
    }
    return null; // не знайдено
  }
}

// Тестовий приклад
const bst = new BinarySearchTree();
[8, 3, 10, 1, 6, 14, 4, 7, 13].forEach(v => bst.insert(v));
console.log(bst.search(7).value); // очікуваний результат: 7
console.log(bst.search(5));       // очікуваний результат: null

Типові помилки і поради

1. Вставка дубліката – не перевіряти, чи вже існує значення; це призведе до зайвих вузлів.
2. Неправильне порівняння – використовувати === для чисел, а не ==, щоб уникнути типових помилок.
3. Відсутність обробки порожнього дерева – не перевіряти root === null перед пошуком, що викликає помилку.
4. Необґрунтоване балансування – якщо дані вставляються впорядковано, дерево стане лінійним; варто розглянути AVL або Red‑Black дерева.
5. Використання рекурсії без обмеження глибини – у великих деревах може викликати переповнення стеку; краще використовувати ітеративний підхід.

Перевір себе

1. Яка складність пошуку у BST, коли дерево збалансоване?
2. Що відбувається, якщо вставляти значення у вже повністю заповнене дерево без балансування?