UK 
EnglishТипова
Polski⏭️ Список з пропусками — імовірнісний збалансований пошук
Список з пропусками надбудовує «швидкі смуги» над відсортованим зв'язним списком: кожен вузол підвищується з імовірністю ½, даючи очікуваний O(log n) пошук — пропуски на верхніх рівнях, тоді спуск униз.
Схожі симуляції
Про список з пропусками
Список з пропусками, запроваджений Вільямом Пагом 1990 року, — це імовірнісна структура даних, що підтримує відсортовану послідовність елементів у кількох шарах зв'язних списків. Нижній шар — це повний відсортований список; кожен вищий шар діє як «швидка смуга», зберігаючи лише випадкову підмножину нижчого шару, причому кожен елемент незалежно підвищується з імовірністю p (зазвичай 0,5). Пошук, вставка та видалення досягають очікуваного часу O(log n) — так само, як і збалансоване ДДП — без накладних витрат на детерміноване перебалансування, властивих AVL- чи червоно-чорним деревам.
Ця симуляція дозволяє вставляти й видаляти цілочисельні ключі, спостерігаючи, як «вежа» кожного вузла зростає до випадкової висоти. Підсвічений шлях обходу під час пошуку показує, як алгоритм спускається через швидкі смуги, перш ніж перейти на наступний шар, ілюструючи, чому середня кількість порівнянь становить приблизно log1/p n.
Часті запитання
Як список з пропусками досягає пошуку O(log n) без детермінованого балансування?
Висота кожного вузла обирається незалежно з геометричного розподілу з імовірністю успіху p, тож очікувана кількість вузлів на рівні k становить n·pk. Пошук починається на найвищому рівні, просувається настільки далеко, наскільки можливо, а потім спускається — очікувана загальна кількість порівнянь становить log1/p n + 1/p, що є O(log n). Випадковість фактично балансує структуру в очікуванні без будь-яких явних поворотів.
Яка складність списку з пропусками у найгіршому випадку?
Час у найгіршому випадку становить O(n) — наприклад, якщо кожен вузол випадково підвищується до кожного рівня — але це відбувається з експоненційно малою імовірністю. На практиці списки з пропусками використовують там, де прийнятні імовірнісні гарантії (наприклад, впорядковані множини Redis внутрішньо використовують список з пропусками), оскільки гарантії найгіршого випадку від збалансованих дерев рідко потрібні в таких контекстах.
Скільки пам'яті використовує список з пропусками порівняно зі збалансованим ДДП?
За імовірності підвищення p = 0,5 очікувана загальна кількість вказівників на всіх рівнях становить 2n (кожен вузол дає один вказівник на рівень, очікувана висота 1/(1−p) = 2). Стандартний вузол червоно-чорного дерева також зберігає два вказівники на нащадків плюс вказівник на батька та біт кольору, тож споживання пам'яті порівнянне; списки з пропусками часто мають дещо вищі константні коефіцієнти через виділення веж змінної довжини.
Як вставка в список з пропусками підтримує відсортований порядок?
Вставка спершу шукає позицію, куди має потрапити новий ключ (записуючи найправіший відвіданий вузол на кожному рівні в масиві оновлень), потім генерує випадкову висоту h для нового вузла, і нарешті вставляє його в кожен рівень від 0 до h−1, оновлюючи вказівники вперед, записані під час пошуку. Це аналогічно вставці у зв'язний список, але повторюється для кожного активного рівня.
Яке значення імовірності підвищення p дає найкращу продуктивність?
p = 0,5 балансує очікуваний час пошуку й простір: зменшення p зменшує пам'ять, але збільшує очікувану кількість порівнянь на рівень; збільшення p збільшує пам'ять. Оригінальний аналіз Пага показав, що p = 0,25 дає майже такий самий очікуваний час із 25% меншою кількістю вказівників, і Redis використовує p = 0,25 у своїй реалізації списку з пропусками. Оптимальний вибір залежить від співвідношення читання/запису та обмежень пам'яті застосунку.
Як список з пропусками порівнюється з двійковим деревом пошуку для конкурентного використання?
Спискам з пропусками часто надають перевагу в конкурентних середовищах, оскільки безблокувальні (lock-free) та неочікувальні (wait-free) варіанти набагато простіше реалізувати, ніж конкурентні збалансовані ДДП. Безблокувальні списки з пропусками (наприклад, алгоритм Харріса-Фрейзера-Шавіта) вимагають лише атомарного порівняння-й-обміну на окремих вказівниках, тоді як конкурентним AVL- чи червоно-чорним деревам доводиться блокувати або ретельно версіонувати цілі ланцюги поворотів. ConcurrentSkipListMap у Java використовує саме такий підхід.
Чи існує детермінована версія списку з пропусками?
Так. Детерміновані списки з пропусками (також звані 1–2 списками з пропусками або B-списками з пропусками) застосовують точні структурні правила замість покладання на випадковість, гарантуючи O(log n) у найгіршому випадку. Однак вони вимагають складнішої логіки вставки й видалення, ближчої до B-дерева, ніж елегантна простота підкидання монети, яка робить імовірнісні списки з пропусками популярними.
Які реальні системи використовують списки з пропусками?
Redis використовує список з пропусками для реалізації типу даних Sorted Set, забезпечуючи запити рангу за O(log n) та сканування діапазонів за оцінкою. Apache Cassandra раніше використовувала списки з пропусками для свого сховища Memtable в пам'яті. LevelDB та RocksDB використовують варіант для свого буфера запису в пам'яті. ConcurrentSkipListMap і ConcurrentSkipListSet зі стандартної бібліотеки Java також реалізовані на основі списку з пропусками.
Як відбувається видалення зі списку з пропусками?
Видалення знаходить вузол і для кожного рівня, на якому він присутній, оновлює вказівник вперед попередника, щоб пропустити його. Після відв'язування вежу видаленого вузла можна звільнити. Якщо видалення зменшує ефективну висоту списку (тобто верхні рівні стають порожніми), лічильник максимального рівня зменшується. Очікуваний час становить O(log n), як і для пошуку.
Чи може список з пропусками ефективно підтримувати запити діапазону?
Так — це одна з практичних переваг списків з пропусками над хеш-таблицями. Після пошуку за O(log n), щоб знайти початок діапазону, зв'язний список нижнього рівня забезпечує обхід за O(k) для збору всіх k елементів у діапазоні. Redis використовує це для команд ZRANGEBYSCORE та ZRANGEBYLEX, які є ключовими для сценаріїв таблиць лідерів та часових рядів.