6.8. Ugrólisták

Az n-elemű láncolt listákban legfeljebb n elemet kell megvizsgálni ahhoz, hogy eldöntsük, hogy egy adott kulcs szerepel-e a listában, vagy sem.

6.56. ábra - 6.8.1. ábra Láncolt lista

6.8.1. ábra Láncolt lista


Ha minden második listaelem tartalmaz egy plusz mutatót a nála kettővel későbbi listaelemre, akkor legfeljebb n 2 + 1 elemet kell megvizsgálni. Újabb és újabb mutatók beszúrásával (minden negyedik elemhez a nála néggyel későbbire mutató, stb.) a vizsgálatok száma ln(n)-nel arányosra csökkenthető.

6.57. ábra - 6.8.2. ábra Láncolt lista extra mutatókkal

6.8.2. ábra Láncolt lista extra mutatókkal


Ebben az adatstruktúrában gyorsan kereshetünk, de a beszúrás és törlés az adatstuktúra átszervezését igényelné. A listaelemet, ha k mutató tartozik hozzá, k-adrendűnek nevezzük. Az előbbi adatszerkezetben 1-szintű az elemek 50 százaléka, 2-szintű az elemek 25 százaléka, stb. Az ugrólistáknál megtartjuk ezeket a valószínűségeket, a beszúrandó elem szintjét véletlenszerűen adjuk meg, a többi elem szintjét nem változtatjuk meg a beszúrás és törlés során, azaz csak lokális változások történnek. Ennek megfelelően az i-dik mutató sem a 2i−1-dik következő elemre mutat, hanem a sorban következő legalább i-szintű elemre. Miután a magasabb szint ű mutatókat használva kihagyunk, átugrunk bizonyos elemeket, ezt az adatszerkezetet ugrólistának nevezzük. (W. Pugh 1990-es cikkében a skip-list elnevezést használta.)

6.8.1. Keresés ugrólistában

Keresésnél a magasabb szintű mutatóknál kell elkezdeni a keresést. Ha a soron következő mutató követésével túllépnénk a keresett elemen, akkor eggyel alacsonyabb szintű mutatókat vizsgálunk. Így végül a keresett elem előtt állunk meg, feltéve ha az az ugrólistában szerepel.

6.58. ábra - 6.8.3. ábra Az eredeti ugrólista

6.8.3. ábra Az eredeti ugrólista


Ha a 16-ot keressük a 6.8.2. a 6.8.3. ábrán látható ugrólistában, akkor a fej harmadszintű mutatójánál kell kezdeni. Ez a 7-et tartalmazó elemre mutat, s mivel a 7 kisebb, mint a 16, így ennél folytatjuk. A 7 harmadrendű mutatója a 19-re mutat, ami már nagyobb a keresett elemnél, ezért egy szintet visszalépünk. A 7 másodszintű mutatója a 13-ra mutat, ez kisebb a keresett elemnél, így ezzel folytatjuk. A 13 másodszintű mutatója a 19-re mutat, ez nagyobb a keresett elemnél, ezért egy szinttel vissza kell lépni. A 13 elsőszintű mutatója a 17-re mutat, de mivel nincs hova visszalépni, így kilépünk a for-ciklusból. A 13-at követő elem kulcsa nem 16, így a rutin Nil értéket ad vissza, jelezve azt, hogy a keresett kulcs nincs benne az ugrólistában.

Function UGRÓLISTA-KERES(L,k) 
Input: L ugrólista, k keresett kulcs 
Output: A kulcsot tartalmazó listaelem címe, illetve Nil 
1  x = L.fej 
2  for i = L.szint downto 1 do 
3     while x.köv[i].kulcs ≤ k do 
4        x = x.köv[i]
5     endw 
6  endfor 
7  x = x.köv[1] 
8  if x.kulcs = k then 
9     return x 
10 else 
11    return Nil
12 endif

6.8.2. Beszúrás ugrólistába

Procedure UGRÓLISTA-BESZÚR(L,z) 
Input: L ugrólista, z beszúrandó elem 
Eredmény: Az ugrólistába beszúrja az adott elemet 
1  x = L.fej 
2  for i = L.szint downto 1 do 
3     while x.köv[i].kulcs ≤ z.kulcs do 
4        x = x.köv[i] 
5        segéd[i] = x 
6     endw
7  endfor 
8  x = x.köv[1] 
9  if x.kulcs == z.kulcs then 
10    x.érték = z.érték 
11 else 
12    for i = 1 to z.szint do 
13       z.köv[i] = segéd[i].köv[i] 
14       segéd[i].köv[i] = z 
15    endfor 
16 endif 

Beszúrásnál először is megkeressük a beszúrandó elem helyét. Ez ugyanúgy megy mint a keresésnél, csupán a beszúrandó elemet a különböző szinteken megelőző elemeket feljegyezzük egy segéd mutatótömben. Miután megtaláltuk az adott elem helyét, a következő fejezetben szereplő láncolt listás beszúráshoz hasonlóan járunk el az adott elem minden szintje esetén, azaz ha a z elem egy adott szinten az x és y közé esik, ahol az y az x követője, akkor mostantól az x-et a z követi, míg a z-t az y. Esetünkben a 6.8.4. ábrán látható ugrólistába szeretnénk beszúrni az 5 kulcsú egyszintű elemet. Ezért bennünket csak az érdekel, hogy az első szinten mit követ az 5 kulcsú elem. Ez a 3 kulcsú elem, melynek a követője a 7 kulcsú, így mostantól 3-at az 5, az 5-öt a 7 követi.

6.59. ábra - 6.8.4. ábra Az 5 beszúrása az ugrólistába

6.8.4. ábra Az 5 beszúrása az ugrólistába


6.8.3. Törlés ugrólistából

Procedure UGRÓLISTA-TÖRÖL(L,k) 
Input: L ugrólista, k kulcs 
Eredmény: A listából törli a megadott kulcsú elemet, ha az szerepel benne 
1  x = L.fej 
2  for i = L.szint downto 1 do 
3     while x.köv[i].kulcs ≤ k do 
4        x = x.köv[i]
5     endw 
6     segéd[i] = x 
7  endfor 
8  x = x.köv[1] 
9  if x.kulcs == k then 
10    for i = 1 to z.szint do 
11       segéd[i].köv[i] = x.köv[i] 
12    endfor 
13 endif 

Törlésnél nem a törlendő elem címét adjuk meg mint korábban, hanem a kulcsát. Ennek megfelelően a beszúráshoz hasonlóan itt is meg kell keresni az adott elemet, s itt is feljegyezzük a törlendő elemet a különböző szinteken megelőző elemeket. Ha a z elem kulcsa a k, és egy adott szinten az x előzi meg a z-t, és y követi, akkor a törlésnél az x következője y lesz. A 6.8.5. és 6.8.6. ábrákon az látható, hogy a példánkban szereplő ugrólistából hogyan törölhető a 7 kulcsú elem. Az első ciklus végrehajtása során az derül ki, hogy ezt az elemet sorra a fej, a 3 és 5 kulcsú elem előzi meg. A 7 törléséhez a következőket kell beállítani: a fejet harmadszinten a 19, a 3 kulcsú elemet a másodszinten a 13 kulcsú, az 5 kulcsú elemet az elsőszinten a 11 kulcsú elem követi.

6.60. ábra - 6.8.5. ábra A 7 törléséhez feljegyezzük az őt megelőző elemeket

6.8.5. ábra A 7 törléséhez feljegyezzük az őt megelőző elemeket


6.61. ábra - 6.8.6. ábra A 7 tényleges törlése

6.8.6. ábra A 7 tényleges törlése