Apa itu skip list dan bagaimana cara mencapai pencarian O(log n)?

Question

Accepted Answer

A **skip list** adalah daftar tertaut yang terurut ditambah dengan beberapa tingkat **"jalur cepat"**. Tingkat yang lebih tinggi melewati banyak node, sehingga pencarian turun dan bergerak ke kanan, mencapai waktu **O(log n)** yang diharapkan — alternatif probabilistik yang lebih sederhana daripada pohon yang seimbang. ## Struktur ```text L3: head ------------------------> 30 -------> NIL L2: head ----------> 17 ---------> 30 -------> NIL L1: head ----> 9 --> 17 --> 25 --> 30 --> 42 -> NIL L0: head -> 3->9->12->17->25->30->39->42 ----> NIL (full list) ``` Setiap node dipromosikan ke tingkat yang lebih tinggi dengan probabilitas `p` (sering 0.5), jadi secara rata-rata setiap tingkat memiliki setengah dari jumlah node di bawahnya. ## Pencarian ```text search(25): start top-left, move RIGHT while next <= target, else drop DOWN a level. Repeat to level 0. ``` ```python import random def random_level(p=0.5, max_level=16): lvl = 1 while random.random() < p and lvl < max_level: lvl += 1 # coin flips decide a node's height return lvl ``` ## Kompleksitas | Operasi | Diharapkan | Ruang | |---|---|---| | search | O(log n) | O(n) | | insert / delete | O(log n) | — | ## Trade-off vs pohon yang seimbang - **Kekuatan:** jauh lebih sederhana untuk diimplementasikan daripada red-black/AVL; tidak ada rotasi; versi bersamaan yang mudah (digunakan dalam set terurut Redis, `ConcurrentSkipListMap` Java). - **Kelemahan:** jaminan probabilistik (bukan kasus terburuk); penunjuk tambahan per node. ## Mengapa ini penting Skip list memberikan operasi terurut mirip pohon dalam O(log n) dengan jauh lebih sedikit kode dan konkurensi tanpa kunci yang mudah, itulah sebabnya sistem nyata seperti Redis memilihnya. Mereka adalah contoh yang bagus dari penggunaan **randomisasi** untuk menggantikan logika penyeimbangan deterministik yang kompleks.