}
==
Acest algoritm ne da nodul din fata elementului cautat, daca acesta exista, sau cel care are cel mai mare key mai mic decat cel cautat. De aici e simplu sa vedem daca elementul cautat exista in skiplist, ar trebui sa fie x->link[0] (urmatorul element, pe nivelul 0 structura este o lista simplu inlantuita). De asemenea ne mai ramane si temp, temp contine acum toate nodurile din fata elementului curent care indica catre elemente de la x in sus. Acest vector temp este o modalitate de a evita listele dublu-inlantuite, si a injumatati consumul de memorie.
Acest algoritm ne da nodul din fata elementului cautat, daca acesta exista, sau cel care are cel mai mare key mai mic decat cel cautat. De aici e simplu sa vedem daca elementul cautat exista in skiplist, ar trebui sa fie {$x->link{~0~}$ (urmatorul element, pe nivelul $0$ structura este o lista simplu inlantuita). De asemenea ne mai ramane si {$temp$}, $temp$ contine acum toate nodurile din fata elementului curent care indica catre elemente de la $x$ in sus. Acest vector $temp$ este o modalitate de a evita listele dublu-inlantuite, si a injumatati consumul de memorie.
OK, dar cum se fac celelalte operatii? Sa le luam pe rand...
* Cautare: am explicat deja
* Inserare: vrem sa inseram un nod cu cheia k. Mai intai cautam cheia k in skiplist-ul deja existent, apoi alocam un nou nod de grad g, pe care il adaugam la fiecare nivel mai mic decat g, exact ca intr-o lista simplu inlantuita.
* Stergere: vrem sa stergem nodul cu cheia k. Mai intai cautam cheia k, apoi stergem nodul la fiecare nivel, exact ca intr-o lista normala.
* Inserare: vrem sa inseram un nod cu cheia {$k$}. Mai intai cautam cheia $k$ in skiplist-ul deja existent, apoi alocam un nou nod de grad {$g$}, pe care il adaugam la fiecare nivel mai mic decat {$g$}, exact ca intr-o lista simplu inlantuita.
* Stergere: vrem sa stergem nodul cu cheia {$k$}. Mai intai cautam cheia {$k$}, apoi stergem nodul la fiecare nivel, exact ca intr-o lista normala.
* Interclasare: aici complexitatea mai depinde si de cat de separate sunt cele doua skip-uri. In principiu comparati primele elemente din fiecare lista iar pe cel mai mare il cautati in celalalt skiplist, luati elementele intre start si pozitia unde s-a oprit algoritmul de cautare si le adaugati in structura care va contine uniunea celor doua.
Complexitate
h2. Complexitate
Pana acum nu am dat nici o explicatie asupra presupusei complexitati O(log N) a operatiilor. Dupa cum puteti vedeam mai sus, operatiile de adaugare si stergere sunt de fapt variante ale operatiiei de cautare, la care se adauga O(grad maxim). Cea mai importanta operatie este cea de cautare.
Pana acum nu am dat nici o explicatie asupra presupusei complexitati $O(log N)$ a operatiilor. Dupa cum puteti vedeam mai sus, operatiile de adaugare si stergere sunt de fapt variante ale operatiiei de cautare, la care se adauga {$O(grad maxim)$}. Cea mai importanta operatie este cea de cautare.
Operatia de cautare va merge prin toate nivele, deci are complexitate minima O(grad maxim). Ne putem imagina un skip-list ideal, in care grad-maxim este O(log N), iar gradele sunt o secventa de genul (max, 1, 2, 1, 4, 1, 2, 1, 8, 1, 2, 1, 4, 1, 2, 1, 16, 1, 2, 1, 4, 1...). In acest skip-list, cautarea este echivalenta cu o cautare binara, la fiecare pas vom "sari" peste fix jumatate din ce a ramas, pentru o complexitate finala de O(log N). Bineinteles, un skip-list real este destul de departe de acest ideal. In cel mai rau caz este posibil ca toate elementele sa aiba acelasi grad, si totul se reduce la o lista inlantuita cu consum mare de memorie, dar este putin probabil. Pe cazul mediu va avea insa complexitatea de O(log N).
Operatia de cautare va merge prin toate nivele, deci are complexitate minima {$O(grad maxim)$}. Ne putem imagina un skip-list ideal, in care grad-maxim este {$O(log N)$}, iar gradele sunt o secventa de genul ({$max, 1, 2, 1, 4, 1, 2, 1, 8, 1, 2, 1, 4, 1, 2, 1, 16, 1, 2, 1, 4, 1$}...). In acest skip-list, cautarea este echivalenta cu o cautare binara, la fiecare pas vom "sari" peste fix jumatate din ce a ramas, pentru o complexitate finala de [$O(log N)$}. Bineinteles, un skip-list real este destul de departe de acest ideal. In cel mai rau caz este posibil ca toate elementele sa aiba acelasi grad, si totul se reduce la o lista inlantuita cu consum mare de memorie, dar este putin probabil. Pe cazul mediu va avea insa complexitatea de {$O(log N)$}.
Pentru a aduce insa la complexitatea de O(log N), este nevoie ca gradele sa aiba o distrubutie logaritmica: fiecare nod are gradul >= 1, N/2 au gradul >= 2, N/4 au gradul >= 3, n/8 au gradul >= 4, etc. Pentru asta avem nevoie de o functie de alegere a gradului aleatoare cu probabilitate logaritmica. Putem face ceva simplu de genul:
Pentru a aduce insa la complexitatea de {$O(log N)$}, este nevoie ca gradele sa aiba o distrubutie logaritmica: fiecare nod are gradul {$≥1$}, {$N/2$} au gradul {$≥ 2$}, $N/4$ au gradul {$≥ 3$}, $n/8$ au gradul {$≥ 4$}, etc. Pentru asta avem nevoie de o functie de alegere a gradului aleatoare cu probabilitate logaritmica. Putem face ceva simplu de genul:
rang = 1
== code(cpp) |rang = 1
while (rand() % 2 == 0) {
++rang;
++rang;
}
==
Functia de mai sus merge satisfacator. Eventual putem sa memoram cate nod-uri de fiecare grad sunt in lista (modificand adaugarea si stergerea), si sa returnam nivelul la care suntem cel mai departe de ideal, dar nu este necesar.
Memorie este oarecum evident O(N). Daca skiplist-ul ar fi complet echilibrat atunci vor exista N link-uri de nivel 0, N/2 de nivel 1, N/4 de nivel 2, etc. Cu putina matematica N + N/2 + N/4 + N/8.. = 2 * N, adica O(n). Pentru cei care programeaza in pascal si nu vor sa se complice cu alocare de array-uri dinamice, memoria va fi evident O(N log N)
Memorie este oarecum evident {$O(N)$}. Daca skiplist-ul ar fi complet echilibrat atunci vor exista $N$ link-uri de nivel {$0$}, {$N/2$} de nivel {$1$}, {$N/4$} de nivel {$2$}, etc. Cu putina matematica {$N + N/2 + N/4 + N/8.. = 2 * N$}, adica {$O(n)$}. Pentru cei care programeaza in pascal si nu vor sa se complice cu alocare de array-uri dinamice, memoria va fi evident $O(N log N)$
Extinderi
h2. Extinderi
Pe langa algoritmii de baza skip list permite imbogatiri care va permit multe alte lucruri cu timp minim de implementare si complexitate O(log N). Cam toate imbogatirile structurii se bazeaza pe memorarea in paralel a unor informatii ajutatoare pt fiecare link (ATENTIE in pascal)
Pe langa algoritmii de baza skip list permite imbogatiri care va permit multe alte lucruri cu timp minim de implementare si complexitate {$O(log N)$}. Cam toate imbogatirile structurii se bazeaza pe memorarea in paralel a unor informatii ajutatoare pt fiecare link (ATENTIE in pascal)
Acces secvential: vrem sa accesam elementul pe pozitia i. Pentru aceasta vom memora pe fiecare link cate noduri "acopera", cu alte cuvinte cate noduri sare. Cautarea se modifica prin introducerea unei noi variabile care memoreaza indicele nodului curent, si prin comparare pozitie la care se sare in loc de cheia la care se sare. La inserare si stergere, trebuiesc actualizate toate linkurile din temp, deoarece si cele care indica peste codul curent contin informatii referitoare la el (il numara).
Acces secvential: vrem sa accesam elementul pe pozitia {$i$}. Pentru aceasta vom memora pe fiecare link cate noduri "acopera", cu alte cuvinte cate noduri sare. Cautarea se modifica prin introducerea unei noi variabile care memoreaza indicele nodului curent, si prin comparare pozitie la care se sare in loc de cheia la care se sare. La inserare si stergere, trebuiesc actualizate toate linkurile din {$temp$}, deoarece si cele care indica peste codul curent contin informatii referitoare la el (il numara).
Intervale: Tot ce trebuie sa adaugam, ca implementare, este o cautare in mod invers, care porneste de la nodul curent (START) si grad = 0, si "urca" pana cand grad > grad_max, sau link[grad] > END (nu exista un nod mai inalt intre inceputul si sfarsitul intervalului, dupa care trebuie sa coboare, ca la cautarea obisnuita... (eventual START si END necesita inserare in skiplist). Daca ati fost un pic atenti am parcurs toate link-urile care contin informatii despre intervalul curent. Pentru stabbing querys (avem un punct si ne intereseaza intervalele care le taie punctul respectiv) tot ce trebuie sa face este sa cautam in skiplist punctul respectiv si sa luam din temp informatiile de la fiecare link.
Intervale: Tot ce trebuie sa adaugam, ca implementare, este o cautare in mod invers, care porneste de la nodul curent ({$START$}) si {$grad = 0$}, si "urca" pana cand {$grad > grad_max$}, sau {$link{~grad~} > END$} (nu exista un nod mai inalt intre inceputul si sfarsitul intervalului, dupa care trebuie sa coboare, ca la cautarea obisnuita... (eventual $START$ si $END$ necesita inserare in skiplist). Daca ati fost un pic atenti am parcurs toate link-urile care contin informatii despre intervalul curent. Pentru stabbing querys (avem un punct si ne intereseaza intervalele care le taie punctul respectiv) tot ce trebuie sa face este sa cautam in skiplist punctul respectiv si sa luam din $temp$ informatiile de la fiecare link.
