h1. Skiplists

(Categoria _Liste_, autor(i) _Stancu Mara Sorin_)

(Categoria _Liste_, autor(i) _Stancu Mara Sorin_, _Giurgea Mihnea_)

Vreau sa va fac cunostinta cu o noua structura randomizata de stocare a datelor. Ea se numeste skiplist si permite majoritatea operatiilor in timp logaritmic si e foarte usor de implementat. Structura ocupa $O(N)$ memorie si efectueaza majoritatea operatiilor (adaugare, cautare, stergere) in {$O(log N)$}. Bineinteles ca exista STL, dar de cele mai multe ori nimic nu bate o structura "home-brewed". Skiplist-urile sunt foarte similare cu arborii AVL, insa sunt un pic mai rapide si mai usor de implementat.

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.

 
h2. Implementare completa
 
Nodul de baza, continand in cazul de fata un integer pe post de informatie, puteti pune aici orice (info), array-ul de dimensiune variabila de pointeri (link), o legatura catre elementul "din spate" (prev), si un array de dimensiune variabila de integeri (jump), in care tin minte pentru fiecare pointer din link "cate elemente sare" - folositor pentru a accesul secvential.
 
== code(cpp)|
struct _node
{
	int info;
	struct _node **link, *prev;
	int *jump;
};
typedef struct _node Node;
==
 
Procedura de a afla inaltimea unui nod, cu un singur apel la funtia rand(). In H se tine minte nivelul curent maxim al listei, si o buna optimizare este sa nu introducem nivele mai mari decat H + 1, pentru o mai buna distributie a nodurilor pe nivele.
 
== code(cpp)|
int GetH()
{
	int h, r;
	for (h = 0, r = rand(); r % 2; r >>= 1, h++);
	if (h > H) h = H + 1;
}
==
 
Si restul functiilor:
 
== code(cpp)|
int Lookup(int key)
{
	Node *node;
	int i;
 
	memset(jumped, 0, sizeof(jumped));
	for (i = H+1; i < MAX_H; i++) path[i] = head;
	for (node = head, i = H; i >= 0; i--)
	{
		for (; node->link[i] != NULL && node->link[i]->info < key; node = node->link[i])
			jumped[i] += node->jump[i];
		path[i] = node;
	}
	if (path[0]->link[0] != NULL && path[0]->link[0]->info == key) return 1;
	else return 0;
}
 
Node* LookupByIndex(int index)
{
	Node *node;
	int lvl;
 
	node = head;
	for (lvl = H; lvl >= 0; lvl--)
		if (node->link[lvl] != NULL && node->jump[lvl] <= index)
		{
			index -= node->jump[lvl];
			node = node->link[lvl];
		}
	if (index > 0) return NULL;
	else return node;
}
 
void Insert(int key)
{
	if (Lookup(key)) return;
 
	Node *node = MakeNode(key, 0);
	int J, i;
 
	if (path[0]->link[0] != NULL)
		path[0]->link[0]->prev = node;
	node->prev = path[0]->link[0];
	for (J = i = 0; i <= nodeH; i++)
	{
		node->link[i] = path[i]->link[i];
		path[i]->link[i] = node;
 
		node->jump[i] = path[i]->jump[i] - J;
		path[i]->jump[i] = J + 1;
 
		J += jumped[i];
	}
 
	for (i = nodeH + 1; i <= MAX_H; i++)
		path[i]->jump[i]++;
 
	if (nodeH > H) H = nodeH;
}
 
void Remove(int key)
{
	if (!Lookup(key)) return;
 
	Node *node = path[0]->link[0];
	int i;
 
	if (node->link[0] != NULL)
		node->link[0]->prev = path[0];
	for (i = 0; i < MAX_H; i++)
		if (path[i]->link[i] == node)
		{
			path[i]->link[i] = node->link[i];
			path[i]->jump[i] += (node->jump[i] - 1);
		}
		else
			path[i]->jump[i]--;
	delete node;
}
==