Як працює алгоритм пошуку при роботі з бінарним деревом?

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

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

Якщо дерево - бінарне дерево пошуку (BST), то пошук іде згори вниз: порівнюємо ключ з поточним вузлом, при ключ < вузла йдемо вліво, при ключ > вузла - вправо; зупиняємось при рівності або при досягненні порожнього посилання. Час O(h), де h - висота дерева: O(log n) у збалансованому випадку і O(n) у гіршому (витягнутому) випадку. Якщо дерево просто бінарне (без властивості BST), то потрібен повний обхід (DFS або BFS) з часом O(n).

Детальний розбір

Визначення

Бінарне дерево: у кожного вузла не більше двох дітей (left, right). Жодних додаткових гарантій впорядкованості.
Бінарне дерево пошуку (BST): для кожного вузла вірно: усі ключі в лівому піддереві < ключ вузла, усі ключі в правому піддереві > ключ вузла (часто допускають рівність за домовленістю). Ця властивість дозволяє робити «спрямований» пошук.

Пошук у бінарному дереві пошуку (BST)

Почніть з кореня. Нехай ключ для пошуку - k, поточний вузол - x.
Якщо x == null, елемента немає (повернути null/undefined).
Якщо k == x.key - знайдено, повернути x.
Якщо k < x.key - перейти в ліве піддерево (x = x.left).
Інакше (k > x.key) - перейти в праве піддерево (x = x.right). Повторювати до завершення.

Складність за часом: O(h), де h - висота дерева. У збалансованому дереві h ≈ log2(n), отже O(log n). У гіршому випадку (витягнуте дерево) - O(n).
Пам'ять: ітеративно - O(1) додаткової пам'яті; рекурсивно - O(h) через стек викликів.

Код: пошук у BST (JavaScript)

class TreeNode {
  constructor(key, left = null, right = null) {
    this.key = key;
    this.left = left;
    this.right = right;
  }
}

// Рекурсивний пошук
function searchBSTRecursive(node, k) {
  if (node === null) return null;
  if (k === node.key) return node;
  if (k < node.key) return searchBSTRecursive(node.left, k);
  return searchBSTRecursive(node.right, k);
}

// Ітеративний пошук
function searchBSTIterative(root, k) {
  let curr = root;
  while (curr !== null) {
    if (k === curr.key) return curr;
    curr = k < curr.key ? curr.left : curr.right;
  }
  return null;
}

// Приклад
//        8
//      /   \
//     3     10
//    / \      \
//   1   6      14
//      / \     /
//     4   7   13
const root = new TreeNode(8,
  new TreeNode(3,
    new TreeNode(1),
    new TreeNode(6, new TreeNode(4), new TreeNode(7))
  ),
  new TreeNode(10, null, new TreeNode(14, new TreeNode(13)))
);

console.log(!!searchBSTIterative(root, 7));   // true
console.log(!!searchBSTIterative(root, 2));   // false

Дублікати в BST

Є кілька домовленостей, оберіть одну і дотримуйтесь її в усьому дереві:

Класти дублікати завжди вліво (≤) або завжди вправо (≥).
Зберігати лічильник частоти у вузлі (key, count).

Пошук у звичайному бінарному дереві (без властивості BST)

Якщо дерево не забезпечує впорядкованості, спрямованого пошуку немає - потрібно обійти всі вузли, поки не знайдете потрібний. Зазвичай використовують DFS або BFS.

BFS (у ширину) - через чергу

Покласти корінь у чергу.
Поки черга не порожня: витягти вузол, перевірити його, додати дітей у чергу.

function searchBinaryTreeBFS(root, predicate) {
  if (!root) return null;
  const q = [root];
  while (q.length) {
    const node = q.shift();
    if (predicate(node)) return node;
    if (node.left) q.push(node.left);
    if (node.right) q.push(node.right);
  }
  return null;
}

// Приклад: знайти вузол зі значенням 13
const foundBFS = searchBinaryTreeBFS(root, (n) => n.key === 13);
console.log(!!foundBFS); // true

DFS (у глибину) - рекурсивно (прямий/інфіксний/зворотний обхід)

Pre-order (NLR): обробити вузол, потім лівий, потім правий.
In-order (LNR): лівий, обробити вузол, правий (дає відсортовану послідовність для BST).
Post-order (LRN): лівий, правий, обробити вузол.

function searchBinaryTreeDFS(node, predicate) {
  if (!node) return null;
  if (predicate(node)) return node;            // pre-order перевірка
  const left = searchBinaryTreeDFS(node.left, predicate);
  if (left) return left;
  return searchBinaryTreeDFS(node.right, predicate);
}

const foundDFS = searchBinaryTreeDFS(root, (n) => n.key === 4);
console.log(!!foundDFS); // true

Складність для BFS/DFS: час O(n), пам'ять - O(w) для BFS (максимальна ширина рівня) і O(h) для рекурсивного DFS.

Порівняння підходів

Сценарій	Час	Пам'ять	Умови
Пошук у BST (ітеративно)	O(h) (часто O(log n))	O(1)	Дерево відповідає властивості BST
Звичайне бінарне дерево (BFS/DFS)	O(n)	O(w) для BFS, O(h) для DFS	Немає впорядкованості, потрібен повний обхід

Часті питання на співбесіді

Як обходитися з дублікатами? У який бік класти і як шукати всі входження?
Що станеться зі складністю в незбалансованому дереві і як допомагають структури AVL/Red-Black?
Ітеративний vs рекурсивний пошук: компроміси щодо стека і простоти.
Чи можна перервати DFS раніше? Так, якщо predicate спрацював - повертаємось вгору по стеку.
Як отримати відсортований результат? In-order обхід BST.

Підсумок

У BST пошук спирається на властивість впорядкованості і рухається вліво/вправо до збігу або порожнього посилання, забезпечуючи O(log n) у збалансованому випадку. У звичайному бінарному дереві для пошуку потрібен повний обхід (DFS/BFS) зі складністю O(n).

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

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

Premium

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