N6

6.

Ugrólista (Skiplist)

Definíció. Olyan adatszerkezet, amelyre teljesül az alábbi három feltétel: 1. Minden cellának az 1. szomszéd kapcsolatát tekintve rendezett lánc. ˝ a láncban a k + 1-edik szomszédját. 2. Minden cella k-adik szomszédja megelozi 3. Bármely x cellára ha y szomszédja x-nek, akkor minden olyan z cellának, amely a láncban x és y között van, bármely szomszédja ˝ nem y után van a láncban. A keresztezés mentesség tulajdonság biztosítható úgy, hogy minden cellából a k-adik szintrol

1. ábra. Az 1. rendezett lánc tulajdonság.

4 3

2 1

˝ 2. ábra. A 2. eloremutató rendezési tulajdonság.

x

z

y

3. ábra. A 3. keresztezés mentesség tulajdonság.

˝ jobbra az elso˝ legalább k magas cella. Adott cellából eloremutató ˝ induló él arra a cellára mutasson, amelyik tole élek számát véletlen válasszuk meg, úgy hogy "jó" eloszlású legyen! n elemet (cellát) tartalmazó ugrólista esetén jelölje N(k) a k magas cellák N(k)

számát és Lk = n

és Lk = p Lk−1 teljesüljön adott 1 < p < 1 valós számra. Ekkor ∞

1 = ∑ Li i=1

azaz

∞

L1 = 1 − ∑ Li i=2

Mivel

∞

∑ Li = L2 + L3 + · · · = L2 + pL2 + p2 L2 + · · ·

i=2

így L1 kifejezheto˝ L2 -vel

∞

L1 = 1 − L2 ∑ pi i=0

Továbbá

∞

1

∑ pi = 1 − p

i=0

Így L1 = 1 −

L2 1−p .

Mivel L2 = pL1 , azt kapjuk, hogy

L1 = 1 −

pL1 ⇒ L1 = 1 − p 1− p

A maximális toronymagasság: L(n)? Az a legkisebb k, amelyre pk n ≤ 1, azaz n ≤ ( 1p )k , tehát

L(n) = log1/p n Hogyan biztosítható ilyen eloszlás? 1

Fej

4 3 2 1

Lab

b

e

c

f

g

j

h

l

k

m

n

o

p

4. ábra. Példa ugrólista.

private byte randomLevel() { //új toronymagasság véletlen generálása byte i=0; while (i<=magas && Math.random()<prob ) i++; return i; } 11 10 9 8 7 6 5 4 3 2 1 ...

...

U[11] U[10] U[6] U[9] U[8] U[7]

...

...

U[5] U[4]

... x

U[3]

y

P

...

...

...

...

Q

U[2] U[1]

˝ 5. ábra. Ugrólista bovítése.

public class ULista<E extends Comparable<E>> implements Iterable<E>{ private static final int MaxSzint=32; public UListaPont<E> fej, lab; // protected byte magas; //a legmagasabb torony magassága private double prob=0.5;//küszöb a véletlen toronymagasság generálásához private boolean multi=true;//többszösös elem megengedett-e public static class UListaPont<E extends Comparable<E>>{ private E elem; public UListaPont<E>[] csat; UListaPont(E x, int m){ csat=new UListaPont[m+1]; this.elem=x; 2

q

r

x

11 10 9 8 7 6 5 4 3 2 1 ...

...

U[11] U[10] U[6] U[9] U[8] U[7]

...

...

U[5] U[4]

... x

U[3]

y

P

...

...

Q

U[2] U[1]

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

} } public UListaPont<E> PKeres(E x) { // UListaPont<E> p = fej; // lab.elem=x; for (int i=magas; i>=0; i--) // while (p.csat[i].elem.compareTo(x)<0 ) p = p.csat[i]; // p = p.csat[0]; // if ((p != lab) && p.elem.equals(x)) return p; // else return null; // } public E Keres(E x){ UListaPont<E> p = PKeres(x); if (p != null) return p.elem; else return null; }

// // // //

public boolean Bovit(E x) { // byte ujSzint = randomLevel(); // UListaPont<E> p = fej; // UListaPont<E> q = fej; // lab.elem=x; for (int i=magas; i>=0; i--) {// q=p.csat[i]; while ( q.elem.compareTo(x)<0 ){ p = q; q = p.csat[i]; } lab.csat[i] = p; } if (!multi && q!=lab && q.elem.equals(x)){ return false; }else{ 3

...

...

UListaPont<E> ujp = new UListaPont<E>(x, ujSzint); if (ujSzint > magas) { magas=ujSzint; lab.csat[ujSzint]=fej; } for (int i=0; i<=ujSzint; i++) { // p=lab.csat[i]; ujp.csat[i]=p.csat[i]; p.csat[i] = ujp; // } return true; } } public boolean Torol(E x){ UListaPont<E> p = fej; UListaPont<E> q = null; lab.elem=x; for (int i=magas; i>=0; i--) {// q=p.csat[i]; while ( q.elem.compareTo(x)<0 ){ p = q; q = p.csat[i]; } lab.csat[i] = p; } if (q==lab || q.elem.compareTo(x)!=0 ) return false; int i=0; while (true){ lab.csat[i].csat[i]=q.csat[i]; i++; if (i>magas || lab.csat[i].csat[i]!=q) break; } q=null; while (magas>=0 && fej.csat[magas]==lab) magas--; return true; }//Torol public ULista<E> Vag(E x){ UListaPont<E> ujfej=new UListaPont<E>(null, MaxSzint); UListaPont<E> ujlab=new UListaPont<E>(null, MaxSzint); ULista<E> UL2=new ULista<E>(); for (int i=0; i<=MaxSzint; i++) ujfej.csat[i]=fej.csat[i]; UListaPont<E> p = fej; // UListaPont<E> q = fej; // lab.elem=x; byte magas1=0; for (byte i=magas; i>=0; i--) {// q=p.csat[i]; while ( q.elem.compareTo(x)<0 ){ p = q; 4

q = p.csat[i]; } ujfej.csat[i]=q; p.csat[i]=ujlab; if (p!=fej && magas1==0) magas1=i; } for (int i=magas1+1; i<=MaxSzint; i++) fej.csat[i]=ujlab; magas=magas1; UL2.lab=lab; UL2.fej=ujfej; magas1=MaxSzint; while (magas1>0 && ujfej.csat[magas1]==lab) magas1--; UL2.magas=magas1; this.lab=ujlab; return UL2; } public void Egyesit(ULista<E> U2){ if (U2.Min()==null) return; if (Min()==null){ fej=U2.fej; lab=U2.lab; magas=U2.magas; multi=U2.multi; U2.Uresit(); return; } if ( Max().compareTo(U2.Min())>=0 ) throw new RuntimeException("A két halmaz nem er˝ osen diszjunkt"); byte ujmagas= (magasmagas; i--) fej.csat[i]=U2.fej.csat[i]; UListaPont<E> p = fej; for (byte i=magas; i>=0; i--){ while (p.csat[i]!=lab) p=p.csat[i]; p.csat[i]=U2.fej.csat[i]; } magas=ujmagas; lab=U2.lab; U2.Uresit(); return; }

A K ERES B OVIT TOROL algoritmusok futási idejének várható értéke:

≤

log1/p n L(n) 1 1 + = + = O(lg n) p (1 − p) p (1 − p)

5