Group insertion in AVL trees

dc.contributorAalto-yliopistofi
dc.contributorAalto Universityen
dc.contributor.advisorSoisalon-Soininen, Eljas
dc.contributor.authorSaikkonen, Riku
dc.contributor.departmentTietotekniikan osastofi
dc.contributor.schoolTeknillinen korkeakoulufi
dc.contributor.schoolHelsinki University of Technologyen
dc.contributor.supervisorSoisalon-Soininen, Eljas
dc.date.accessioned2020-12-04T18:24:49Z
dc.date.available2020-12-04T18:24:49Z
dc.date.issued2004
dc.description.abstractTyössä tutkitaan useita algoritmeja AVL-puun ryhmälisäysoperaatiolle. Tutkitut algoritmit kuvataan yksityiskohtaisesti, mutta työn pääasiallinen sisältö on ryhmälisäyksen tehokkuuden kokeellinen tutkiminen. Tasapainotusoperaatioiden määrän lisäksi mitattiin välimuistin käytön tehokkuutta simuloidun välimuistin avulla. Työssä kuvataan myös kokeissa käytetyn ohjelmiston arkkitehtuuri. Ryhmälisäysalgoritmi lisää joukon avaimia tietorakenteeseen yhdellä operaatiolla. Ryhmälisäyksessä tarvitaan vähemmän tasapainotusoperaatioita kuin jos avaimet lisättäisiin yksi kerrallaan yksittäislisäyksellä, koska tasapainotus voidaan tehdä sen jälkeen, kun kaikki avaimet on lisätty. AVL-puut ovat tasapainoisia binäärisiä hakupuita, joiden sovelluksia ovat esimerkiksi keskusmuistitietokannat ja kokotekstihaku. AVL-puilla on pienet solmut ja tasapainotusoperaatiot ovat paikallisia, mikä tekee niistä tehokkaita rinnakkaisessa käytössä. Työn kokeissa ryhmälisäysalgoritmeja verrattiin toisiinsa ja tavalliseen yksittäislisäysalgoritmiin eri tilanteissa. Välimuistikäyttäytymistä mitattiin laskemalla työjoukon koko sekä eri kokoisilla simuloiduilla välimuisteilla. Kokeissa käytettiin kolmea ryhmälisäysalgoritmia: niin sanottua yksinkertaista ryhmälisäystä (avaimet lisätään yksi aliryhmä kerrallaan) käyttäviä O(log m)- ja O(log<sup>2</sup> m)-algoritmeja sekä monen aliryhmän lisäystä käyttävää O(log<sup>2</sup> m)-algoritmia (m on aliryhmän koko). Aliryhmä muodostuu saman lehtisolmun alle päätyvistä avaimista. Kokeissa mitatut rotaatioiden määrät sopivat hyvin analyyttisiin kompleksisuustuloksiin: O(log m)-algoritmi teki paljon vähemmän rotaatioita kuin kaksi O(log<sup>2</sup> m)-algoritmia, myös pienillä m:n arvoilla. Ryhmälisäysalgoritmit toimivat myös selvästi yksittäislisäystä paremmin yli kahden kokoisilla aliryhmillä. O(log m)-algoritmin välimuistin käyttö oli kuitenkin tehottomampaa kuin O(log<sup>2</sup> m)-algoritmilla. Nähtävästi O(log m)-algoritmilla on suurempi työjoukko, koska se tarvitsee enemmän tietoa valitessaan suoritettavia rotaatioita. Tämä ja muut päätulokset näkyivät sekä satunnaisesti muodostetulla syötteellä että simuloidusta kokotekstihakusovelluksesta tuotetusta syötteestä.fi
dc.format.extent85
dc.identifier.urihttps://aaltodoc.aalto.fi/handle/123456789/91498
dc.identifier.urnURN:NBN:fi:aalto-2020120450333
dc.language.isoenen
dc.programme.majorOhjelmistotekniikkafi
dc.programme.mcodeT-106fi
dc.rights.accesslevelclosedAccess
dc.subject.keyworddata structuresen
dc.subject.keywordtietorakenteetfi
dc.subject.keywordalgorithmsen
dc.subject.keywordalgoritmitfi
dc.subject.keywordexperimental algorithmicsen
dc.subject.keywordkokeellinen algoritmitutkimusfi
dc.subject.keywordsearch treesen
dc.subject.keywordhakupuutfi
dc.subject.keywordAVL treeen
dc.subject.keywordAVL-puufi
dc.subject.keywordgroup updateen
dc.subject.keywordryhmäpäivitysfi
dc.subject.keywordbulk updateen
dc.subject.keywordryhmälisäysfi
dc.subject.keywordgroup insertionen
dc.subject.keywordbulk insertionen
dc.titleGroup insertion in AVL treesen
dc.titleRyhmälisäykset AVL-puissa (Group insertion in AVL trees)fi
dc.type.okmG2 Pro gradu, diplomityö
dc.type.ontasotMaster's thesisen
dc.type.ontasotPro gradu -tutkielmafi
dc.type.publicationmasterThesis
local.aalto.digiauthask
local.aalto.digifolderAalto_90515
local.aalto.idinssi25059
local.aalto.openaccessno
Files