Arbre multicamí
Els arbres multicamí o arbres multibranca són estructures de dades de tipus arbre usades en computació.
Definició
[modifica]Un arbre multicamí té un grau g més gran a dos, on cada node d'informació de l'arbre té un màxim de g fills.
Sigui un arbre de m-camins A , és un arbre m-camins si i només si:
- A està buit
- Cada node de A mostra la següent estructura:
[nclaus, Enllaç 0 , Clau 1 ,..., Clau nclaus , Enllaç nclaus ]
- Nclaus és el nombre de valors de clau d'un node, podent ser:
0 <= nclaus <= g-1 - Enllaç i , són els enllaços als subarbre de A , podent ser:
0 <= i <= nclaus - Clau i , són els valors de clau, i poden ser:
1 <= i <= nclaus
Clau i <Clau i+1- Cada valor de clau en el subarbre Enllaç i és menor que el valor de Clau i+1
- Els subarbre Enllaç i , on
0 <= i <= nclaus, són també arbres m-camins.
Hi ha moltes aplicacions en què el volum de la informació és tal, que les dades no caben a la memòria principal i cal emmagatzemar-los, organitzats en fitxers, en dispositius de almacenaminento secundari. Aquesta organització de fitxers ha de ser prou adequada com per recuperar les dades del mateix en forma eficient.
Avantatges i inconvenients
[modifica]El principal avantatge d'aquest tipus d'arbres és que hi ha més nodes en un mateix nivell que en els arbres binaris amb el que s'aconsegueix que, si l'arbre és de recerca, els accessos als nodes siguin més ràpids.
L'inconvenient més important que tenen és la major ocupació de memòria, pot passar que a vegades la majoria dels nodes no tinguin descendents o almenys no tots els que podrien tenir desaprofitant, per tant, gran quantitat de memòria. Quan això passa el més freqüent és transformar l'arbre multicamí en el seu binari de cerca equivalent.
Nota
[modifica]Un tipus especial d'arbres multicamí utilitzat per solucionar el problema de l'ocupació de memòria són els arbres B o arbres Bayer.