Večsmerna drevesa

Iz MaFiRaWiki

Vsebina

Definicija

Večsmerna drevesa so tista drevesa, pri katerih želimo poudariti njihove otroke. V tem primeru moramo namreč najti rešitev ob dejstvu, da imajo nekateri ljudje več kot dva otroka in da bo ustrezno drevo imelo več povezav.

Seveda ne predstavljajo take strukture nič posebnega in pri dvojiških drevesih smo že srečali vsa programerska sredstva in sredstva za definicijo podatkov, ki jih v tej situaciji potrebujemo. Če je na primer podana absolutna zgornja meja za število otrok, potem bi v zapisu, ki ustreza osebi, otroke lahko ponazorili s komponento tipa polja. Vendar pa to lahko povzroči slab izkoristek pomnilnika, zato je bolje postaviti otroke v linearen seznam in prirediti staršu kazalec na najmlajšega (ali najstarejšega).

Vizualizacija

Večsmerno drevo ponazorimo z diagramom, kjer povezave potekajo v več smeri. Po navadi ne moremo z bratom ali sestro nekaznovano ravnati, kot da bi bila naša otroka in je torej podobno ravnanje nepriporočljivo tudi pri definicijah podatkov. Primera, ki jih ne moremo izpeljati iz relacij bratovstva (ali sestrstva) pa sta relaciji zakonske zveze in celo nasprotna relacija očetovstva ali materinstva. Podobne strukture se kaj hitro spremenijo v zapletene relacijske podatkovne baze in v take strukture je možno preslikati nekaj dreves na enkrat. Algoritmi, ki ravnajo s takimi strukturami so tesno povezani z njihovimi definicijami in zato zanje splošna pravila ali široko uporabne tehnike nimajo posebnega pomena.

Uporaba večsmernih dreves

Področje uporabe večsmernih dreves postaja zelo pomembno. To je gradnja in vzdrževenje velikih iskalnih dreves, kjer sta pomembna vstavljanje in izločanje, vendar je hitri pomnilnik računalnika premajhen ali predrag za želeni obseg podatkov. Večsmerno drevo pa je idealna rešitev problema. Če smo namreč že našli nek element v zunanjem pomnilniku, potem lahko dosežemo še neko skupino elementov brez posebnih dodatnih stroškov. To nas pripelje do delitve drevesa na poddrevesa, pri čemer so poddrevesa celote, ki jih dosegamo naenkrat. Takim poddrevesom rečemo strani (angl. pages). S tem je prihranek v številu dosegov diska kar precejšen.

Primeri večsmernih dreves

Najbolj znana so B-drevesa in dvojiška B-drevesa.

image:12bdrevo.JPG

Glej tudi

Osebna orodja