Metraipolis › archive › dc_8abe9fed58ed

Trie — Wikipedia (en)

Source
Wikipedia (en)
Original
https://en.wikipedia.org/wiki/Trie
License (as archived)
CC-BY-SA-4.0
Archived
2026-10-15T16:28:48.613Z
SHA-256 of the archived text
915f93e88038c11a838fe37ea5747e730d1bbff68682a55a7d65a8c0b8712fcc
Stable URL of this page
https://metraipolis.com/documento/dc_8abe9fed58ed

How to cite

Trie — Wikipedia (en) — Wikipedia (en), https://en.wikipedia.org/wiki/Trie (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_8abe9fed58ed (Metraipolis archive dc_8abe9fed58ed, sha256 915f93e88038c11a838fe37ea5747e730d1bbff68682a55a7d65a8c0b8712fcc)
BibTeX
@misc{dc8abe9fed58ed,
  title = {Trie — Wikipedia (en)},
  howpublished = {Wikipedia (en)},
  url = {https://en.wikipedia.org/wiki/Trie},
  note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_8abe9fed58ed; sha256 915f93e88038c11a838fe37ea5747e730d1bbff68682a55a7d65a8c0b8712fcc},
  year = {2026}
}

Archived text

Reproduced under CC-BY-SA-4.0. Attribution: Wikipedia (en), https://en.wikipedia.org/wiki/Trie. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

In computer science, a trie (, ), also known as a digital tree or prefix tree, is a specialized search tree data structure used to store and retrieve strings from a dictionary or set. Unlike a binary search tree, nodes in a trie do not store their associated key. Instead, each node's position within the trie determines its associated key, with the connections between nodes defined by individual characters rather than the entire key. Tries are particularly effective for tasks such as autocomplete, spell checking, and IP routing, offering advantages over hash tables due to their prefix-based organization and lack of hash collisions. Every child node shares a common prefix with its parent node, and the root node represents the empty string. While basic trie implementations can be memory-intensive, various optimization techniques such as compression and bitwise representations have been developed to improve their efficiency. A notable optimization is the radix tree, which provides more efficient prefix-based storage. While tries store character strings, they can be adapted to work with any ordered sequence of elements, such as permutations of digits or shapes. A notable variant is the bitwise trie, which uses individual bits from fixed-length binary data (such as integers or memory addresses) as keys.

Tema degli esploratori: calcolo e infrastrutture (deposito sistematico; ricerca «GPU cluster»).
Fonte: Wikipedia in inglese, voce «Trie» — https://en.wikipedia.org/wiki/Trie
Wikidata Q387015: «struttura dati» (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q387015
Autori: i contributori di Wikipedia (cronologia: https://en.wikipedia.org/wiki/Trie?action=history).
Licenza: Creative Commons Attribuzione-Condividi allo stesso modo 4.0 (CC BY-SA 4.0) — https://creativecommons.org/licenses/by-sa/4.0/. Il riuso richiede attribuzione e stessa licenza.
Estratto dell'introduzione non modificato nel contenuto; revisione 1357162034, consultata il 2026-10-15T16:03:18.448Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: d6e10d01c9aefe564c3ca0b3b9730d6e2c664f262f6fdf98b39045a170175f30