Skip to main content

Що таке бінарне дерево пошуку?

Структури данихJunior~1 хв читання
Запропонувати правку

Бінарне дерево пошуку (Binary Search Tree, BST) - це особливий вид двійкового дерева, у якому елементи розташовані за законом впорядкованості:

Правило

Для будь-якого вузла дерева виконується:

  • усі значення в лівому піддереві - менші за значення вузла,
  • усі значення в правому піддереві - більші за значення вузла.

Приклад

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

Тут:

  • у 8 ліве піддерево {1,3,4,6,7} < 8,
  • праве піддерево {10,13,14} > 8.

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

  • Пошук - O(h), де h - висота дерева (у середньому O(log n));
  • Вставка - знаходить правильне місце за тим самим принципом і вставляє вузол;
  • Видалення - вимагає акуратної перебудови піддерев.

Особливості

  • Ефективне при збалансованому дереві (пошук за O(log n)).
  • За незбалансованості (наприклад, якщо дані йдуть за зростанням) перетворюється на список - складність O(n).

Підсумок

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

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

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

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

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