Apakah skip list dan bagaimana ia mencapai pencarian O(log n)?

Question

Accepted Answer

**Skip list** adalah senarai terpaut yang tersusun ditambah dengan berbilang peringkat **"lorong ekspres"**. Peringkat yang lebih tinggi melangkau banyak nod, jadi pencarian menurun dan bergerak ke kanan, mencapai masa **O(log n)** yang dijangkakan — ini adalah alternatif probabilistik yang lebih mudah daripada pokok bimbang. ## 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 nod dipromosikan ke peringkat yang lebih tinggi dengan kebarangkalian `p` (sering 0.5), jadi secara purata setiap peringkat mempunyai separuh daripada nod pada peringkat 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 ``` ## Kerumitan | Operasi | Dijangkakan | Ruang | |---|---|---| | search | O(log n) | O(n) | | insert / delete | O(log n) | — | ## Tukar-ganti berbanding pokok bimbang - **Kekuatan:** jauh lebih mudah dilaksanakan daripada red-black/AVL; tiada putaran; versi serentak mudah (digunakan dalam set tersusun Redis, Java `ConcurrentSkipListMap`). - **Kelemahan:** jaminan probabilistik (bukan kes terburuk); penuding tambahan setiap nod. ## Mengapa hal ini penting Skip list memberikan operasi tersusun seperti pokok O(log n) dengan kod yang jauh lebih sedikit dan keserempakan lock-free yang mudah, itulah sebabnya sistem sebenarnya seperti Redis memilihnya. Ini adalah contoh yang baik untuk menggunakan **keacakan** menggantikan logik penyeimbangan penentu yang rumit.