Запропонувати правкуПокращити цю статтюДопрацюйте відповідь до «Що таке бінарне дерево пошуку?». Ваші зміни проходять модерацію перед публікацією.Потрібне підтвердженняКонтентЩо ви змінюєте🇺🇸EN🇺🇦UAПереглядЗаголовок (UA)Коротка відповідь (UA)**Бінарне дерево пошуку (BST)** - це особливий вид двійкового дерева, у якому для кожного вузла всі значення в лівому піддереві менші за нього, а в правому - більші. **Ключове:** BST дає змогу швидко шукати, додавати й видаляти елементи порівняно з лінійними структурами.Показується над повною відповіддю для швидкого нагадування.Відповідь (UA)Зображення**Бінарне дерево пошуку (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). ## Підсумок **Бінарне дерево пошуку** - це структура, де дані зберігаються у вигляді дерева з чітким порядком, що дає змогу **швидко шукати, додавати й видаляти елементи** порівняно з лінійними структурами.Для рев’юераПримітка для модератора (необов’язково)Бачить лише модератор. Прискорює рев’ю.