For faster navigation, this Iframe is preloading the Wikiwand page for Arbre multicamí.

Arbre multicamí

De Viquipèdia

Els arbres multicamí o arbres multibranca són estructures de dades de tipus arbre usades en computació.

Definició

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

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

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.

Vegeu també

{{bottomLinkPreText}} {{bottomLinkText}}
Arbre multicamí
Listen to this article

This browser is not supported by Wikiwand :(
Wikiwand requires a browser with modern capabilities in order to provide you with the best reading experience.
Please download and use one of the following browsers:

This article was just edited, click to reload
This article has been deleted on Wikipedia (Why?)

Back to homepage

Please click Add in the dialog above
Please click Allow in the top-left corner,
then click Install Now in the dialog
Please click Open in the download dialog,
then click Install
Please click the "Downloads" icon in the Safari toolbar, open the first download in the list,
then click Install
{{::$root.activation.text}}

Install Wikiwand

Install on Chrome Install on Firefox
Don't forget to rate us

Tell your friends about Wikiwand!

Gmail Facebook Twitter Link

Enjoying Wikiwand?

Tell your friends and spread the love:
Share on Gmail Share on Facebook Share on Twitter Share on Buffer

Our magic isn't perfect

You can help our automatic cover photo selection by reporting an unsuitable photo.

This photo is visually disturbing This photo is not a good choice

Thank you for helping!


Your input will affect cover photo selection, along with input from other users.