Salvarea listei - o structură de căutare a datelor care implementează interfața unui set ordonat, vă permite să efectuați căutări, adăugiri și ștergeri dintr-un articol din listă într-un timp relativ scurt.
Se caută un articol din listă; Adăugarea și eliminarea unui element are loc în același timp cu căutarea, însă aceste operații pot încetini căutarea în structură.
[edit] Construirea
Lista de sărituri este construită pe baza listei existente dintr-o singură legătură.
Prin adăugarea de niveluri suplimentare, fiecare reprezentând nivelul anterior fără elemente ciudate, vom putea căuta, insera și șterge elemente similare cu operațiile cu arborele binar de căutare. În consecință, asimptotica acestor operațiuni va fi.
[edit] Structură Operații
[edit] Găsirea unui element
Să presupunem că există niveluri pe lista noastră de insigne, primul nivel () fiind lista originală.
În acest caz, algoritmul de căutare din această structură va consta din următoarele operații:
- Începem căutarea pentru elementul din lista de sus (), luăm în considerare primul element
- Mergeți la următorul element din listă până când valoarea din celula următoare este mai mică sau egală cu cheia
- Deplasați-vă un nivel și treceți la pasul 2. Dacă elementul în cauză se află la nivelul inferior - ieșiți din căutare
Un exemplu de găsire a unui număr din listă din descriere:
Luați în considerare timpul de lucru pentru o listă cu două nivele. Apoi timpul de funcționare al algoritmului de căutare va depinde de numărul de elemente de la nivel. Imaginați-vă că la acest nivel am obținut întâmplător câteva elemente. Prin urmare, în cel mai rău caz al unei căutări, obținem următoarea estimare a timpului de lucru:
Minimizând, înțelegem asta
Ca rezultat, timpul pentru care găsim un element în listă cu pași cu două niveluri va fi egal cu:
De asemenea, puteți să vă asigurați că o listă cu sărituri care are nivele va funcționa cel mai bine cu elementele de la nivel; Timpul de funcționare al unei astfel de liste va fi egal. Cu toate acestea, pentru niveluri, timpul de lucru va fi
[edit] Introducerea unui element
Pentru a introduce un element în listă cu sărituri, trebuie să efectuăm următorii pași:
- Găsiți cu ajutorul algoritmului de căutare poziția în care trebuie să inserăm acest element
- Introduceți elementul nostru în nivelul inferior al listei cu ecusoane
- "Aruncați o monedă" și, în funcție de rezultat, împingeți elementul la un nivel mai înalt
- Repetați pasul anterior până când avem o "aruncare a monedei" dă un rezultat pozitiv
Astfel, dacă folosiți o monedă onestă, atunci așteptarea matematică a numărului de elemente de pe al doilea nivel este egală, la nivelul al treilea, etc. La nivel, vom avea un element. Ei bine, probabilitatea de a ajunge la elementul de pe al doilea nivel este, în al treilea rând, etc. Probabilitatea de a ajunge la nivel este.
Folosind o monedă cu o distribuție diferită de ,, puteți afecta numărul de elemente din nivelele superioare. De exemplu, atunci când se utilizează o monedă cu o distribuție>, așteptarea matematică a numărului de elemente la nivel este egală, fiecare nivel va fi de la cel precedent; timpul de căutare va fi egal cu. În consecință, cu o monedă cinstit și niveluri, obținem estimarea obținută mai devreme. Pentru distribuții extreme:
- -
- - (dacă permiteți adăugarea de noi niveluri atunci când împingeți elementul după ce ați aruncat o monedă, altfel)
[edit] Ștergerea unui element
Algoritmul de ștergere este suficient de trivial.
- Găsiți elementul de eliminat
- Eliminați-l de la toate nivelurile
[edit] Pseudocod
Visual, dar nu foarte eficient din versiunea de memorie a listei cu insigne.
Nodurile magazinelor de pe listă:
- - următorul nod
- - același nod la nivelul următor
- - date de tipul T
- - tipul cheie K
Căutarea elementului după cheie:
[edit] Aplicație
- Baze de date
- Calculul distribuit și p2p
- Cozi și dictionare paralele prioritare scalabile
În geometria computațională, structurile bazate pe o listă cu omisiuni sunt utilizate pe scară largă.
[edit] Vezi, de asemenea
Structuri bazate pe o listă cu insigne:
[edit] Surse de informare
Articole similare
Trimiteți-le prietenilor: