However, other authors pronounce it / ˈ t r aɪ/ (as "try"), in an attempt to distinguish it verbally from "tree". The idea was independently described in 1960 by Edward Fredkin, who coined the term trie, pronouncing it / ˈ t r iː/ (as "tree"), after the middle syllable of retrieval. Tries were first described in a computer context by René de la Briandais in 1959. The idea of a trie for representing a set of strings was first abstractly described by Axel Thue in 1912. Specialized trie implementations such as compressed tries are used to deal with the enormous space requirement of a trie in naive implementations. The key lookup complexity of a trie remains proportional to the key size. In particular, a bitwise trie is keyed on the individual bits making up a piece of fixed-length binary data, such as an integer or memory address. The same algorithms can be adapted for ordered lists of any underlying type, e.g. Though tries can be keyed by character strings, they need not be. This task of storing data accessible by its prefix can be accomplished in a memory-optimized way by employing a radix tree. This distributes the value of each key across the data structure, and means that not every node necessarily has an associated value.Īll the children of a node have a common prefix of the string associated with that parent node, and the root is associated with the empty string.
Instead, a node's position in the trie defines the key with which it is associated. Unlike a binary search tree, nodes in the trie do not store their associated key. In order to access a key (to recover its value, change it, or remove it), the trie is traversed depth-first, following the links between nodes, which represent each character in the key. These keys are most often strings, with links between nodes defined not by the entire key, but by individual characters. In computer science, a trie, also called digital tree or prefix tree, is a type of k-ary search tree, a tree data structure used for locating specific keys from within a set. Each complete English word has an arbitrary integer value associated with it.
0 kommentar(er)
