Revisió del 00:51, 25 des 2008 modifica EVA (bot) (discussió \| contribucions) Bots 851.856 edits m Robot substituint el text: (-[[Imatge +[[Fitxer) ← Edició anterior		Revisió del 17:34, 29 març 2009 modifica desfés Lohen11 (discussió \| contribucions) Administradors 190.460 edits orto i altres, Replaced: pre- → pre (2) AWB Edició següent →
Línia 1: [[Fitxer:trie.png\|thumb\|right\|250px\|Un '''trie''' representant les entrades "as", "pi", "pom", "por" i "poma".]] Un '''trie''' és un cas especial d'[[autòmat finit#Autòmats_finits_deterministes \| autòmat finit determinista]] <math>(S, \Sigma, T, s, A)</math>, que serveix per a emmagatzemar un conjunt de cadenes <math>E</math> en el qual: * <math>\Sigma</math> és l'[[alfabet]] sobre el qual estan definides les cadenes; * <math>S</math>, el conjunt d'estats, cadascun dels quals representa un prefix de E; Línia 14: * necessita menys espai per emmagatzemar una gran quantitat de cadenes petites, ja que les claus no s'emmagatzemen explícitament * té un millor funcionament per a l'algorisme de cerca del prefixe més llarg == Aplicacions == Linha 20 ⟶ 19: === Substituint taules de dispersió === Un Trie es pot utilitzar per substituir una [[~~taula de dispersió\|~~Taula de dispersió]], sobre la qual presenta els següents avantatges: * el temps de cerca en una taula de dispersió imperfecta és de l'ordre de <math>O(n)</math>, i en un ''trie'' es de l'ordre de <math>O(l)</math>. Açò és degut a les colisions de claus * en un ''trie'' no es produeixen colisions de claus Linha 61 ⟶ 60: L'ordre lexicogràfic d'un conjunt de claus es pot realitzar com un algorisme simple basat en '''tries''' de la següent forma: * inserir totes les claus en el ''trie'' * obtenir totes les claus mitjançant un recorregut en ~~pre-ordre~~preordre, per obtenir un ordenament lexicogràfic en ordre ascendent, o mitjançant un recorregut en post-ordre, per obtenir un ordenament lexicogràfic en ordre descendent. El recorregut en ~~pre-ordre~~preordre i en post-ordre són [[algorisme]]s de [[cerca en profunditat]] d'[[arbres]]. [[Categoria:Gestió de dades]]

Trie: diferència entre les revisions