Що робить бінарне дерево пошуку (BST)?

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

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

Бінарне дерево пошуку (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) у найгіршому випадку.

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

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

Лист: просто видаляємо.
Один нащадок: підтягуємо нащадка на місце вузла.
Два нащадки: замінюємо ключ (і значення) вузла на ключ його in-order наступника (мінімум у правому піддереві) і видаляємо наступника з правого піддерева.

Обходи: симетричний (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).
Визначте і дотримуйтесь політики дублікатів (заборона, лічильник, направлення праворуч/ліворуч).
Функція порівняння має задавати строгий слабкий порядок (транзитивність, антирефлексивність) - інакше дерево зламається.
Рекурсивні реалізації простіші, але можуть впертися в ліміт стека на дуже глибоких деревах; за потреби використовуйте ітеративні версії.

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

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

Premium

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