Toteutukset hakurakenteille C++:ssa

No Thumbnail Available

Files

URL

Journal Title

Journal ISSN

Volume Title

Perustieteiden korkeakoulu | Bachelor's thesis
Electronic archive copy is available locally at the Harald Herlin Learning Centre. The staff of Aalto University has access to the electronic bachelor's theses by logging into Aaltodoc with their personal Aalto user ID. Read more about the availability of the bachelor's theses.
Unless otherwise stated, all rights belong to the author. You may download, display and print this publication for Your own personal use. Commercial use is prohibited.

Authors

Date

2024-05-08

Department

Major/Subject

Tietotekniikka

Mcode

SCI3027

Degree programme

Teknistieteellinen kandidaattiohjelma

Language

fi

Pages

22

Series

Abstract

Tietokoneita on mahdollista nopeuttaa käyttämällä tehokkaita tietorakenteita, jotka on luotu tietokoneen vaatimaan käyttötarkoitukseen. Tehokkaiden tietorakenteiden käyttö tuo useita etuja, sillä se vapauttaa tietokoneen resursseja muuhun käyttöön ja kasvattaa energiatehokkuutta. Työssä tarkastellaan hakurakenteiden neljää eri toteutusta, ja verrataan niiden eroavaisuuksia sekä teoreettisesta että käytännönläheisestä näkökulmasta. Kyseiset neljä hakurakennetta ovat punamusta puu, AVL-puu, Splay-puu ja hajautustaulu, ja niiden vertailu on toteutettu kirjallisuuskatsauksena. Työssä vertailtiin ensin neljän eri hakurakennetoteutuksen välisiä eroja teoreettisesta näkökulmasta. Tämän jälkeen työssä selvitettiin, näkyivätkö nämä erot todellisissa työkuormissa ja algoritmien suorituskyvyissä. Yhteenvetona tuloksista voidaan sanoa, että yksittäistä hakurakennetta, joka toimi parhaiten kaikissa tilanteissa ei ollut. Sen sijaan työssä havaittiin algoritmien ominaisuuksia, jotka synnyttivät eroja hakurakenteiden suorituskyvyssä. Tällaisia algoritmin ominaisuuksia ovat paikallisuus, alkioiden hakujärjestys, lisäys- ja hakuoperaatioiden suhde, datajoukon koko, käytettävissä oleva muistinmäärä ja tietokoneen arkkitehtuuri.

Description

Supervisor

Savioja, Lauri

Thesis advisor

Korhonen, Ari

Keywords

tietorakenne, hakurakenne, punamusta puu, AVL-puu, splay-puu, hajautustaulu

Other note

Citation

Permanent link to this item

https://urn.fi/URN:NBN:fi:aalto-202406044020

Collections

[kand] Perustieteiden korkeakoulu / SCI