Algoritmuselmélet pótgyakorlat a harmadik gyakorlathoz

1. A következőket tudjuk egy fa m,n elemeiről: m megelőzi n-t a fa X-order szerinti bejárásában, viszont m az n után jön a fa Y-order szerinti bejárásában (X,Y $=\{ pre, post,in\}$). Melyik eset(ek)ben tudjuk eldönteni, hogy m őse-e n-nek?

2. Az S₁ és S₂ kulcshalmazokat kiegészített 2-3-fákban tároljuk. Ezek az eredeti 2-3-fától abban különböznek csak, hogy minden csúcsban fel van jegyezve az onnan induló részfa magassága (szintjeinek száma). Tegyük még fel, hogy az S₁-beli kulcsok mind kisebbek az S₂-belieknél. Javasoljunk hatékony algoritmust a két fa egyesítésére. A cél tehát egy olyan kiegészített 2-3-fa, amelyben a kulcsok $S_1\cup S_2$ elemei.

3. Egy AVL-fába egy új elemet illesztettünk be az előadáson tanult módszerrel. Az eredményképpen kapott AVL-fa magassága nagyobb, mint az eredetié. Milyen forgatást alkalmazhattunk?

4. Adott egy n=2^k-1 pontú teljes bináris keresőfa. A fában tárolt elemek egészek az I=[1,2^k] intervallumból és egy szám legfeljebb egyszer fodul elő a fában. Utóbbi feltétel szerint pontosan egy olyan $i\in I$ egész van, amely nincs a fában. Adjunk egy hatékony módszert i meghatározására.

5. Adottak a sík egész koordinátájú $P_1=(x_1,y_1),P_2=(x_2,y_2),\ldots , P_n=(x_n,y_n)$ pontjai. Javasoljunk $O(n\log n)$ költségű módszert annak eldöntésére, hogy vannak-e olyan P_i,P_j pontok ($i\not= j$), melyek távolsága nem több mint 2.

6. Egy rendezett halmaz adott n eleméből kupacot szeretnénk építeni, melyre (a kupac tulajdonság mellett) teljesül, hogy minden x csúcs bal részfájának az elemei kisebbek mint az x jobb részfájának az elemei.
Igazoljuk, hogy ehhez legalább $\Omega (n\log n)$ összehasonlítás szükséges!

Algoritmuselmélet pótgyakorlat a harmadik gyakorlathoz

1. A következőket tudjuk egy fa m,n elemeiről: m megelőzi n-t a fa X-order szerinti bejárásában, viszont m az n után jön a fa Y-order szerinti bejárásában (X,Y $=\{ pre, post,in\}$). Melyik eset(ek)ben tudjuk eldönteni, hogy m őse-e n-nek?

2. Az S₁ és S₂ kulcshalmazokat kiegészített 2-3-fákban tároljuk. Ezek az eredeti 2-3-fától abban különböznek csak, hogy minden csúcsban fel van jegyezve az onnan induló részfa magassága (szintjeinek száma). Tegyük még fel, hogy az S₁-beli kulcsok mind kisebbek az S₂-belieknél. Javasoljunk hatékony algoritmust a két fa egyesítésére. A cél tehát egy olyan kiegészített 2-3-fa, amelyben a kulcsok $S_1\cup S_2$ elemei.

3. Egy AVL-fába egy új elemet illesztettünk be az előadáson tanult módszerrel. Az eredményképpen kapott AVL-fa magassága nagyobb, mint az eredetié. Milyen forgatást alkalmazhattunk?

4. Adott egy n=2^k-1 pontú teljes bináris keresőfa. A fában tárolt elemek egészek az I=[1,2^k] intervallumból és egy szám legfeljebb egyszer fodul elő a fában. Utóbbi feltétel szerint pontosan egy olyan $i\in I$ egész van, amely nincs a fában. Adjunk egy hatékony módszert i meghatározására.

5. Adottak a sík egész koordinátájú $P_1=(x_1,y_1),P_2=(x_2,y_2),\ldots , P_n=(x_n,y_n)$ pontjai. Javasoljunk $O(n\log n)$ költségű módszert annak eldöntésére, hogy vannak-e olyan P_i,P_j pontok ($i\not= j$), melyek távolsága nem több mint 2.

6. Egy rendezett halmaz adott n eleméből kupacot szeretnénk építeni, melyre (a kupac tulajdonság mellett) teljesül, hogy minden x csúcs bal részfájának az elemei kisebbek mint az x jobb részfájának az elemei.
Igazoljuk, hogy ehhez legalább $\Omega (n\log n)$ összehasonlítás szükséges!