Splay-puu

Wikipedia
Loikkaa: valikkoon, hakuun

Tietojenkäsittelytieteessä splay-puu (mukautuva puu, viistopuu, engl. splay tree) on tasapainotettu binäärihakupuu, jonka erityisominaisuus on mukautuminen: peräkkäin samoihin avaimiin kohdistuvat operaatiot ovat erityisen nopeita. Splay-puun kehittivät Daniel Sleator ja Robert Tarjan vuonna 1985.

Tehokkuus[muokkaa | muokkaa wikitekstiä]

Splay-puun operaatiot toimivat tasoitetussa suoritusajassa O(log n). Koska avainkysely nostaa kysytyn solmun juureksi, peräkkäiset kyselyt toimivat vakioajassa.

Käytännön tehokkuus verrattuna muihin hakupuihin riippuu käyttötavasta. Esimerkiksi treap saattaa olla nopeampi vaihtoehto. Splay-puu ei kuitenkaan vaadi lainkaan ylimääräistä tilaa linkkien lisäksi.

Katso myös[muokkaa | muokkaa wikitekstiä]

Esitietoja[muokkaa | muokkaa wikitekstiä]

Vaihtoehtoja[muokkaa | muokkaa wikitekstiä]

Lähteet[muokkaa | muokkaa wikitekstiä]

  • Daniel Sleator ja Robert Tarjan: Self-Adjusting Binary Search Trees. Journal of the ACM, 1985, 32. vsk, nro 3, s. 652–686. Artikkelin verkkoversio (PDF) Viitattu 5.2.2008. (englanniksi)
Tämä tietotekniikkaan liittyvä artikkeli on tynkä. Voit auttaa Wikipediaa laajentamalla artikkelia.