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

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

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

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

Контент

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

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

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

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

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

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

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

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

### Визначення

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

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

1. Почніть з кореня. Нехай ключ для пошуку - k, поточний вузол - x.
2. Якщо x == null, елемента немає (повернути null/undefined).
3. Якщо k == x.key - знайдено, повернути x.
4. Якщо k < x.key - перейти в ліве піддерево (x = x.left).
5. Інакше (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 (у ширину) - через чергу

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

```
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).

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

Для рев’юера

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

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