Алгоритми та структури даних · Senior · Запитання 74 з 75
Чого не вміє ефективно прийом «дві купи» порівняно зі збалансованим BST?
- ✓Правильна відповідь: Видаляти довільний елемент із середини
- 2Читати поточну медіану за O(1)
- 3Вставляти новий елемент за O(log n)
Пояснення
Купи дешево видаляють лише корінь. Для медіани в ковзному вікні потрібне ліниве видалення (позначати видалені значення й пропускати їх пізніше) або впорядкована мультимножина, як-от збалансоване дерево, що видаляє будь-яке значення за O(log n).