Алгоритми та структури даних · Junior · Запитання 51 з 75
Що станеться, якщо вставити 1, 2, 3, 4, 5 по черзі у простий BST без балансування?
- 1Дерево автоматично збалансується
- 2Вставка не вдасться, бо значення мають бути випадковими
- ✓Правильна відповідь: Дерево стане ланцюжком, і операції деградують до O(n)
Пояснення
Кожне нове значення більше за всі попередні й іде праворуч, тож дерево перетворюється на зв'язний список. Самобалансовані дерева (AVL, червоно-чорні) обертають вузли, щоб тримати висоту O(log n).