Što je Splay Tree?

Stablo prikaza je optimizirano binarno stablo pretraživanja ili stablo podataka temeljeno na čvoru, koje se samopodešava i bolje za pristup nedavno pretraživanim elementima i čvorovima. Pet funkcija može se izvesti na stablu prikaza, dopuštajući korisniku da manipulira čvorovima. Ovo stablo ima vrlo mali otisak, tako da je za pohranu podataka potrebno malo memorije. Nedostatak ovog stabla je što je izgrađeno linearno, tako da će čvorovima pohranjenim prema dnu trebati duže za pristup.

Splay stabla su binarna stabla koja pohranjuju čvorove podataka; to su obično binarni podaci, iako oni također mogu sadržavati datoteke. Za razliku od običnog binarnog stabla pretraživanja, koje korisnicima omogućuje pretraživanje kroz čvorove, stablo s prikazom se samo pomiče kako bi pretraživanje bilo mnogo brže. Svi nedavno otvoreni čvorovi bit će raspoređeni blizu vrha stabla, tako da je potrebno manje vremena za pronalaženje i otvaranje čvora. Ovo preuređivanje znači da su stabla prikaza korisna za predmemoriju – memoriju računala koja sadrži podatke kojima se nedavno pristupilo – i za algoritme napravljene za uklanjanje neiskorištenih podataka.

Na stablu se može koristiti pet funkcija. Operacija razlaganja je poput operacije spajanja, jer pristup jednom čvoru postaje povezan s drugim čvorom. Funkcija split uzima jedan čvor i dijeli ga na dva ili više čvorova. Sa spajanjem, dva čvora se pretvaraju u jedan. Insert uzima dio čvora i umeće ga u drugi, dok funkcija delete briše dio čvora iz stabla prikaza.

Splay stablo koristi vrlo malo memorije, što korisnicima omogućuje izradu velikih stabala bez zauzimanja ogromne količine prostora na tvrdom disku. Splay stabla su jednostavna i ne zahtijevaju puno koda za izgradnju, tako da ne zahtijevaju istu količinu memorije koju zahtijevaju složenija stabla. Knjigovodstvene informacije, koje su obično potrebne drugim stablima za praćenje pozicioniranja podataka, nepotrebne su zbog prirode stabla koje se samopreuređuje.

Iako stablo razmjene zauzima malo memorije i može lako pristupiti nedavnim čvorovima, brzina može biti problem. Čvorovi se mogu rasporediti samo linearno, što znači da će neki čvorovi biti nisko na stablu, dok su nedavni čvorovi na vrhu. Do ovih donjih čvorova bit će teško doći, jer stablo mora tražiti od vrha do dna dok se ne pronađu donji čvorovi. To je zato što nema knjigovodstvenih podataka, što rezultira sporim traženjem niskih čvorova.