Ce este o skip list și cum realizează căutarea O(log n)?

Question

Accepted Answer

O **skip list** este o listă legată ordonată îmbogățită cu mai multe niveluri **"express lane"**. Nivelurile superioare sar peste mulți noduri, deci căutarea coboară și se mișcă la dreapta, realizând **O(log n)** timp așteptat — ca o alternativă probabilistică mai simplă la un copac echilibrat. ## Structură ```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) ``` Fiecare nod este promovat la niveluri superioare cu probabilitate `p` (adesea 0.5), deci în medie fiecare nivel are jumătate din nodurile celui de jos. ## Căutare ```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 ``` ## Complexitate | Operație | Așteptat | Spațiu | |---|---|---| | căutare | O(log n) | O(n) | | inserare / ștergere | O(log n) | — | ## De ce conteaza - **Puncte forte:** mult mai simplu de implementat decât red-black/AVL; fără rotații; versiuni concurente ușoare (folosite în Redis sorted sets, Java `ConcurrentSkipListMap`). - **Puncte slabe:** garantii probabilistice (nu worst-case); pointeri extra per nod. ## Compromisuri vs copaci echilibrați Skip lists oferă operații ordonate O(log n) asemănătoare copacilor cu mult mai puțin cod și concurență lock-free ușoară, motiv pentru care sisteme precum Redis le aleg. Sunt un exemplu grozav de utilizare a **randomization** pentru a înlocui logica de echilibrare deterministică complexă.