{
  "id": "trie-044893-a1d4c1f1efe7306a",
  "slug": "trie",
  "title": "trie",
  "qid": "Q387015",
  "lead": "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.",
  "body": "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. ==History, etymology, and pronunciation== The idea of a trie for representing a set of strings was first abstractly described by Axel Thue in 1912. Tries were first described in a computer context by René de la Briandais in 1959. The idea was independently described in 1960 by Edward Fredkin, who coined the term trie, pronouncing it (as \"tree\"), after the middle syllable of retrieval. However, other authors pronounce it (as \"try\"), in an attempt to distinguish it verbally from \"tree\". ==Implementation strategies== : vertical arrows are pointers, dotted horizontal arrows are pointers. The set of strings stored in this trie is . The lists are sorted to allow traversal in lexicographic order. Tries can be represented in several ways, corresponding to different trade-offs between memory use and speed of the operations. Using a vector of pointers for representing a trie consumes enormous space; however, memory space can be reduced at the expense of running time if a singly linked list is used for each node vector, as most entries of the vector contains \\text{nil} . Techniques such as alphabet reduction may reduce the large space requirements by reinterpreting the original string as a longer string over a smaller alphabet. For example, a string of bytes can alternatively be regarded as a string of four-bit units. This can reduce memory usage by a factor of eight; but lookups need to visit twice as many nodes in the worst case. Another technique includes storing a vector of 256 ASCII pointers as a bitmap of 256 bits representing ASCII alphabet, which reduces the size of individual nodes dramatically.",
  "categories": [
    "108503271",
    "23118434",
    "23396418",
    "23584436",
    "23603337",
    "25257581",
    "28269683",
    "28374593",
    "96369911"
  ],
  "license": "CC BY-SA 4.0",
  "source_uri": "https://en.wikipedia.org/w/index.php?oldid=1357162034",
  "content_hash": "a1d4c1f1efe7306a952af3e0bfeb1919369ac759ba95427f0705f06e0f873140",
  "created_at": 1792308650.3753343,
  "updated_at": 1780273665.0,
  "claims": [],
  "contradictions": [],
  "confidence": 0.6,
  "csl": {
    "id": "trie-044893-a1d4c1f1efe7306a",
    "type": "webpage",
    "title": "trie",
    "author": [
      {
        "family": "Anticloud FZ LLE",
        "literal": "Anticloud FZ LLE"
      }
    ],
    "container-title": "encyclopegia.org",
    "publisher": "Anticloud FZ LLE",
    "publisher-place": "Dubai, United Arab Emirates",
    "URL": "https://encyclopegia.org/a/trie",
    "issued": {
      "date-parts": [
        [
          2026,
          10,
          18
        ]
      ]
    },
    "accessed": {
      "date-parts": [
        [
          2026,
          11,
          21
        ]
      ]
    },
    "license": "CC BY-SA 4.0",
    "DOI": "eo1:trie-044893-a1d4c1f1efe7306a",
    "isBasedOn": "https://en.wikipedia.org/w/index.php?oldid=1357162034",
    "note": "Immutable snapshot trie-044893-a1d4c1f1efe7306a, content root a1d4c1f1efe7306a…"
  }
}