Mis on Splay Tree?

Splay-puu on optimeeritud binaarne otsingupuu ehk sõlmepõhine andmepuu, mis on isereguleeruv ja parem hiljuti otsitud elementidele ja sõlmedele juurdepääsuks. Esituspuul saab täita viit funktsiooni, mis võimaldavad kasutajal sõlmedega manipuleerida. Sellel puul on väga väike jalajälg, seega on andmete salvestamiseks vaja vähe mälu. Selle puu puuduseks on see, et see on ehitatud lineaarselt, nii et põhja poole salvestatud sõlmedele juurdepääsemiseks kulub kauem aega.

Splay-puud on kahendpuud, mis salvestavad andmesõlmed; need on tavaliselt binaarandmed, kuigi need võivad sisaldada ka faile. Erinevalt tavalisest binaarsest otsingupuust, mis võimaldab kasutajatel sõlmede kaudu otsida, liigub esituspuu ise ringi, et muuta otsimine palju kiiremaks. Kõik hiljuti avatud sõlmed paigutatakse puu ülaosa lähedale, nii et sõlme leidmiseks ja avamiseks kulub vähem aega. See ümberkorraldamine tähendab, et esituspuud on kasulikud vahemälude jaoks – arvutimälu, mis hoiab hiljuti juurde pääsetud andmeid – ja kasutamata andmete kõrvaldamiseks loodud algoritmide jaoks.

Puul saab kasutada viit funktsiooni. Mänguoperatsioon on nagu liitumisoperatsioon, kuna ühe sõlme juurdepääs seotakse teise sõlmega. Jagamisfunktsioon võtab ühe sõlme ja jagab selle kaheks või enamaks sõlmeks. Ühenduse abil muudetakse kaks sõlme üheks. Insert võtab osa sõlmest ja lisab selle teise, samas kui kustutamisfunktsioon kustutab esituspuust sõlme osa.

Esituspuu kasutab väga vähe mälu, mis võimaldab kasutajatel teha suuri puid ilma tohutult kõvakettaruumi hõivamata. Splay-puud on lihtsad ja nende loomiseks ei ole vaja palju koodi, seega ei vaja nad sama palju mälu kui keerukamad puud. Raamatupidamisteave, mis on tavaliselt vajalik teistele puudele andmete positsioneerimise jälgimiseks, on puu isereorganiseeruva iseloomu tõttu tarbetu.

Kuigi esituspuu võtab vähe mälu ja pääseb hõlpsasti juurde hiljutistele sõlmedele, võib probleem olla kiirus. Sõlme saab korraldada ainult lineaarselt, mis tähendab, et mõned sõlmed asuvad puus madalal, samas kui hiljutised sõlmed on ülaosas. Nende alumiste sõlmedeni on raske jõuda, sest puu peab otsima ülalt alla, kuni alumised sõlmed on leitud. Selle põhjuseks on asjaolu, et puuduvad raamatupidamisandmed, mille tulemuseks on madalate sõlmede otsimine aeglane.