Algoritmien teoria, kevät 1999
Harjoitus 3, 8.2. klo 10-12 sali MaD380

1. 1. Suunnittele splay-puurakenteelle tehokkaat, alkion juureennosto-operaatioon perustuvat päivitysalgoritmit. (Ohje: Kunkin operaation aluksi nostetaan käsiteltävä alkio puun juureen.)
   2. Esitä splay-puun päivitysalgoritmien toiminta, kun aluksi tyhjään puuhun ensin lisätään alkiot 6, 2, 7, 0, 4, 5, 9, 8, ja näin saadusta puusta sitten poistetaan alkiot 2 ja 9.
2. Täydennä luennolla (muistiinpanojen ss. 164.12-13) esitetty splay-puiden tasatun vaativuuden analyysi osoittamalla, että myös alkion x siksik-kierron tasattu kustannus on enintään 3(R'(x)-R(x)), missä R(x) on alkion x ranki ennen kiertoa ja R'(x) sen ranki kierroksen jälkeen.
3. Simuloi kekotietorakenteen heapify-operaation (luennot, s. 166) toimintaa sen muodostaessa lukujonoa 4, 11, 9, 10, 5, 6, 8, 1, 2, 16 vastaavaa kekoa. (Pienin alkio keon juureen.)
4. Muodosta joukkoja {5, 2, 7} ja {0, 3, 4, 6, 1, 8, 9} vastaavat binomimetsät ja simuloi niiden yhdistämistä luennolla (muistiinpanojen ss. 167-169) esitetyillä algoritmeilla.
5. Todista seuraavat binomipuiden rakenneominaisuudet:
   1. Binomipuun , , juuren alipuut ovat täsmälleen binomipuut , ..., .
   2. Binomipuussa , , on syvyydellä k, , täsmälleen solmua