Algoritmuselmélet gyakorlat (3)

Elemi alapfeladatok
1. Bizonyísuk be, hogy az inorder bejárás növekvő sorrendben adja vissza egy bináris fa elemeit!

2. Egy bináris keresőfa "valamely bejárásán" mindig a $\{pre,\;in,\;post\}$-order valamelyikét értjük.
(a) Mely bejárásoknál lehetséges az, hogy a tárolt elemek legnagyobbika megelőzi a legkisebbet?
(b) Tegyük fel, hogy egy bináris keresőfában az $1,2,\ldots,n$ számok vannak tárolva, továbbá hogy a fa valamely bejárásánal a számok az $n,n-1,\ldots,1$ sorrendben következnek. Határozzuk meg, melyik lehetett ez a bejárás és milyen lehetett ez a bináris keresőfa!

3. Illesszük be az alábbi 6 kulcsot egy kezdetben üres (2,3)-fába a megadott sorrendben: D,B,E,A,C,F. Rajzoljuk le az eredményül kapott fát!

4. Építsünk AVL-fát az alábbi input számsorozatból: 4,3,2,1,7,6,5.

Normális feladatok
5. Egy bináris keresőfa csúcsait egy, a gyökértől egy levélig menő út szerint három osztályba soroljuk: B az úttól balra levő, U az útra eső, J pedig az úttól jobbra levő csúcsok halmazát jelöli. Igaz-e mindig, hogy minden B-beli csúcs kulcsa kisebb tetszőleges U-beli csúcs kulcsánál, és minden U-beli csúcs kulcsa kisebb, mint tetszőleges J-beli csúcs kulcsa?

6. Egy rendezett univerzum n eleme egy A bináris keresőfában, k eleme pedig egy B bináris keresőfában van tárolva. Adjunk minél hatékonyabb módszert a két fában levő elemek nagyság szerinti sorrendben történő kilistázására! (Tehát egy olyan tömböt szeretnénk kapni, amiben az n+k elem rendezetten helyezkedik el.) Elemezzük a módszer költségét!

7. Az [1,178] intervallum összes egészei egy 2-3 fában helyezkednek el. Tudjuk, hogy a gyökérben két kulcs van, és az első kulcs a 17. Mi lehet a második? Miért?

8. Adott n pont a síkon, melyek páronként mindkét koordinátájukban különböznek. Bizonyítsuk be, hogy egy és csak egy bináris fa létezik, melynek szögpontjai az adott n pont, és az első koordináta szerint a keresőfa tulajdonsággal, a második szerint pedig a kupac tulajdonsággal rendelkezik. (Vigyázat: a kupac tulajdonságba nem értendő bele, hogy a fa teljes bináris fa legyen, mint amilyet a tanult "kupacépítő" algoritmus létrehoz.)

9. Adjunk példát olyan AVL fára, hogy egy alkalmas törlés esetén egyetlen forgatás ne legyen elegendő az AVL-tulajdonság helyreállítására.

10. Adott egy n pontú AVL-tulajdonágú bináris fa. Adjunk meg polinomidejű algoritmust az $1,\dots ,n$ számok egy olyan sorrendjének meghatározására, amely esetén az AVL-fa építő algoritmus a megadott fát hozza létre, mégpedig forgatás nélkül.

Gondolkozni való feladat
11. Adott n chip, melyek képesek egymás tesztelésére a következő módon: ha összekapcsolunk két chipet, mindkét chip nyilatkozik a másikról, hogy hibásnak találta-e. Egy hibátlan chip korrektül felismeri, hogy a másik hibás -e, míg egy hibás chip akármilyen választ adhat. Tegyük fel, hogy a chipek több, mint a fele korrekt. Adjunk algoritmust, mely n-nél kevesebb fenti tesztet használva kikeres egy jó chipet.