Алгоритми та структури даних · Senior · Запитання 13 з 75
Що таке skip list (список із пропусками)?
- ✓Правильна відповідь: Відсортований список із випадковими «експрес-смугами»
- 2Список, що пропускає дублікати під час кожної вставки
- 3Масив, у якому видалено кожен другий елемент
Пояснення
Кожен вузол отримує випадкову висоту; вищі рівні пропускають більше вузлів. Пошук, вставка й видалення в середньому O(log n), і цю структуру простіше зробити конкурентною, ніж збалансоване дерево. Відсортовані множини Redis використовують skip list.