Що є найгіршим варіантом BST?
Найгірший сценарій, бінарне дерево має максимальний (або мінімальний) елемент у корені, а всі інші елементи сортуються з одного боку від кореня, фактично перетворюючи дерево на пов’язаний список.
У збалансованому BST часова складність для пошуку елемента становить O(log(n)), де n – кількість вузлів у дереві. Ця ефективність досягається за рахунок зменшення простору пошуку вдвічі на кожному рівні, коли ми порівнюємо цільове значення зі значенням поточного вузла та переходимо ліворуч або праворуч.
Можна сказати, що «найкращий випадок» для пошуку BST коли ми шукаємо кореневий елемент у BST; Зверніть увагу ще раз, що ми не обмежуємо цей опис одним розміром введення.
Двійковий пошук
| Візуалізація алгоритму бінарного пошуку, де 7 є цільовим значенням | |
|---|---|
| Клас | Алгоритм пошуку |
| Найгірша продуктивність | O(log n) |
| Найкраща продуктивність | О(1) |
| Середня продуктивність | O(log n) |
У середньому випадку (і в найкращому випадку) – припускаючи, що дерево досить добре збалансоване, тоді висота буде приблизно log₂ N . Отже, космічна складність буде O(log₂ N) або просто O(lg N) У найгіршому випадку, коли дерево є просто відсортованим пов’язаним списком, що розгалужується праворуч із збільшенням значень, тоді O(N) як найгірший випадок.
Отже, ми можемо сказати, що час виконання двійкового пошуку Big-O становить O(log n). Таким чином, двійковий пошук є набагато швидшим алгоритмом пошуку, ніж лінійний пошук, якщо масив відсортований. А його час виконання Big-O становить O(log n).